在上一篇博客中,博主与大家学习了一个新的数据结构——。它是一个只被允许在栈顶进行插入与删除元素的特殊线性表,是一种典型的LIFO的数据结构。在我们用数组的方式实现了顺序存储的顺序栈之后,本章博客中我们就一起来尝试实现一个链式存储的栈吧。

    和普通的线性表一样,我们可以选择用单链或者是双链来实现这个数据结构。由于栈只能够在栈顶进行入栈和出栈操作,因此一个只含有栈顶节点的单链表就可以轻松实现它了。

    下面我们就来一起实现这个链式存储的链栈吧:

    	//栈顶节点,不存储元素,只用来指向栈顶的元素
    	private Node stackTop;
    	private int size;
    	
    	public MyLinkedStack () {
    		stackTop = new Node(null,null);
    		size = 0;
    	}
    	
    	class Node{
    		E data;
    		Node nextNode;
    		Node(E data, Node nextNode) {
    			this.data = data;
    			this.nextNode = nextNode;
    		}
    		
    	}
    

    然后是进栈和出栈的操作:

    	@Override
    	public E push(E item) {
    		// TODO Auto-generated method stub
    		Node newNode = new Node(item,stackTop.nextNode);
    		stackTop.nextNode = newNode;
    		this.size++;
    		return item;
    	}
    
    	@Override
    	public E pop() {
    		// TODO Auto-generated method stub
    		Node n = stackTop.nextNode;
    		E data = n.data;
    		stackTop.nextNode = n.nextNode;
    		n.data = null;
    		n.nextNode = null;
    		n = null;
    		this.size--;
    		return data;
    	}
    

    接下来是,返回栈中顶部元素以及返回栈中某个元素的位置的实现:

    	@Override
    	public E peek() {
    		// TODO Auto-generated method stub
    		return stackTop.nextNode.data;
    	}
    	@Override
    	public int search(Object o) {
    		// TODO Auto-generated method stub
    		if(empty()) return -1;
    		int index =1;
    		if(o == null) {
    			for(Node n=stackTop.nextNode; n!=null; n=n.nextNode, index++) {
    				if(n.data == null) {
    					return index;
    				}
    			}
    			return -1;
    		}else {
    			for(Node n=stackTop.nextNode; n!=null; n=n.nextNode, index++) {
    				if(o.equals(n.data)) {
    					return index;
    				}
    			}
    			return -1;
    		}
    	}
    

    最后,是检查栈是否为空以及清空整个栈的操作:

    	@Override
    	public boolean empty() {
    		// TODO Auto-generated method stub
    		return size==0;
    	}
    	@Override
    	public void clear() {
    		// TODO Auto-generated method stub
    		if(empty()) return;
    		for(Node n=stackTop.nextNode; n!=null ;) {
    			Node next = n.nextNode;
    			n.data = null;
    			n.nextNode = null;
    			n = next;
    		}
    		this.size = 0;
    	}
    

    对比一下我们完成的顺序栈与链栈,它们在时间复杂度上都是O(1)。对于空间性能来说,顺序栈基于数组实现,会有一个数组的固定长度(如果没有放满元素,存在空间浪费);而链栈并没有长度的限制,却在每个节点上耗费指针域的空间。因此如果栈的使用过程中元素变化不可预料,我们应该选择链栈;如果元素数量的变化在一个可控的范围呢,那么我们可以选择顺序栈。