欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链式栈——Java实现

程序员文章站 2022-06-05 18:58:05
...
package struct;

//接口
interface ILinkStack{
	//栈中元素个数(栈大小)
	int size();
	//取栈顶元素
	Object top();
	//判断栈是否为空
	boolean isEmpty();
	//入栈
	Object pop();
	//出栈
	Object push(Object value);
	//清空栈
	void clear();
}

//工厂类
class Factory2{
	private Factory2(){}
	public static ILinkStack getILinkStackInstance(){
		return new LinkStackImpl();
	}
}

class LinkStackImpl implements ILinkStack {
	//栈顶元素
	Node top;
	//链表长度记录入栈元素
	private int count;
	class Node{
		Node prev;
		Node next;
		Object data;
		public Node(Object data) {
			this.data = data;
		}
	}
	
	public int size() {
		return count;
	}

	public Object top() {
		return top.data;
	}
	//判栈空
	public boolean isEmpty() {
		return (size()==0);
	}
	//入栈
	public Object push(Object value) {
		Node node = new Node(value);
		if(top == null){
			top = node;
		}else{
			top.next = node;
			node.prev = top;
			top = top.next;
		}
		count++;
		return top;
	}
	public void print(){
		System.out.println("从栈顶到栈底打印栈中元素:");
		myPrint(top);
		return;
	}
	//栈顶->栈底打印链表
	private void myPrint(Node top){
		for(Node node = top;node!=null;node=node.prev){
			System.out.print(node.data+" ");
		}
	}
	//出栈
	public Object pop() {
		Node node = top;
		if(top == null){
			System.out.println("空栈无要出栈元素");
			return -1;
		}else{
			top = top.prev;
			node.prev = null;
			node.data = null;
		}
		count--;
		return top();
	}
	//清空栈
	public void clear(){
		Node node1 = top;
		for(Node node = top;node!=null;){
			node = node.prev;
			node1.data = null;
			node1.prev = null;
			count--;
		} 
	}
}
public class LinkStack {
	public static void main(String[] args) {
		ILinkStack linkStack = Factory2.getILinkStackInstance();
		//向下转型
		LinkStackImpl linkStack1 = (LinkStackImpl)linkStack;
		System.out.println("============测试isEmpty函数(空栈)=================");
		System.out.println(linkStack.isEmpty());
		System.out.println("============测试push和print函数=================");
		linkStack.push(5);
		linkStack.push(9);
		linkStack.push(10);
		linkStack.push(1);
		linkStack.push(8);
		linkStack.push(12);
		linkStack.push(6);
		linkStack.push(3);
		linkStack1.print();
		System.out.println();
		System.out.println("============入栈后测试top函数=================");
		System.out.println(linkStack.top());
		System.out.println("============入栈后测试size函数=================");
		System.out.println(linkStack.size());
		System.out.println("============测试pop和print函数=================");
		linkStack.pop();
		linkStack.pop();
		linkStack.pop();
		linkStack1.print();
		System.out.println();
		System.out.println("============出站后测试top函数=================");
		System.out.println(linkStack.top());
		System.out.println("============出栈后测试size函数=================");
		System.out.println(linkStack.size());
		System.out.println("============测试clear后size函数=================");
		linkStack.clear();
		System.out.println(linkStack.size());
	}
}

链式栈——Java实现