??棧是存放對象的一種特殊容器毛甲，在插入與刪除對象時候醒，這種結(jié)構(gòu)遵循后進先出（Last-in-first-out沼侣，LIFO）的原則??也就是說蚕断，對象可以任意插入棧中，但每次取出的都是此前插入的最后一個對象旦棉。

Java棧的通用接口

package com.stack;

public interface Stack {

    public int getSize();//返回棧中元素個數(shù)
    
    public boolean isEmpty();//判斷棧是否為空
    
    public Object top();//獲取棧頂元素潮尝，但不刪除
    
    public void push(Object elem);//入棧
    
    public Object pop();//出棧
}

基于數(shù)組實現(xiàn)棧

package com.stack;

public class MyStack implements Stack{

    public static final int CAPACITRY = 1024;
    public int capacity;
    public Object[] s;
    public int top = -1;
    
    public MyStack()
    {
        this(CAPACITRY);
    }
    
    
    public MyStack(int cap) {
        capacity = cap;
        s = new Object[capacity];
    }


    @Override
    public int getSize() {
        
        return top+1;
    }

    @Override
    public boolean isEmpty() {
        
        return (top < 0);
    }

    @Override
    public Object top() {
        
        if(isEmpty())
        {
            System.out.println("棧為空");
            return null;
        }
        return s[top];
    }

    @Override
    public void push(Object elem) {
        if(getSize() == capacity)
        {
            System.out.println("棧滿");       
            return;
        }
        s[++top] = elem;
    }

    @Override
    public Object pop() {
        if(isEmpty())
        {
            System.out.println("棧為空");
            return null;
        }
        
        Object elem = s[top];
        s[top--] = null;
        return elem;
    }

}

基于單鏈表實現(xiàn)棧

??節(jié)點的java實現(xiàn)

package com.node;

public class Node {

    private Object elem;
    private Node next;
    
    public Node()
    {
        this(null,null);
    }
    
    public Node(Object e,Node n)
    {
        elem = e;
        next = n;
    }
    
    public Object getElem() {       
        return elem;
    }

    public void setElem(Object elem) {
        this.elem = elem;
    }
    
    public Node getNext()
    {
        return this.next;
    }
    
    public void setNext(Node next)
    {
        this.next = next;
    }

}

??棧的實現(xiàn)

package com.stack;

import com.node.Node;

//單鏈表實現(xiàn)棧
public class Stack_list implements Stack{

    protected Node top;//棧頂元素
    protected int size;//棧中元素個數(shù)
    
    //初始化時創(chuàng)建頭結(jié)點
    public Stack_list()
    {
        top = null;
        size = 0;
    }
    
    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {
        return (top == null)?true:false;
    }

    @Override
    public Object top() {
        if(isEmpty())
        {
            System.out.println("棧為空");
        }
        return top.getElem();
    }

    @Override
    public void push(Object elem) {
        //元素壓棧
        Node newNode = new Node(elem,top);
        top = newNode;//修改棧頂指針
        size++;//修改棧中元素個數(shù)
    }

    @Override
    public Object pop() {
        if(isEmpty())
        {
            System.out.println("棧為空");
            return null;            
        }
        Object elem = top.getElem();
        top = top.getNext();
        size--;
        return elem;
    }

}