如何使用Java數(shù)組和鏈表實現(xiàn)棧

小編給大家分享一下如何使用Java數(shù)組和鏈表實現(xiàn)棧，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、何為棧？

棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進(jìn)行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

?？梢灶惐瘸涩F(xiàn)實生活中的彈夾或者羽毛球桶

二、用數(shù)組實現(xiàn)棧

用數(shù)組模擬棧的思路分析如圖：

1.定義一個top變量（指針）表示棧頂初始化為-1.
2.定義一個變量來記錄棧的大小。
3.入棧操作有數(shù)據(jù)加入到棧中：top++; arr[top]=value;
4.出棧操作： int value=arr[top]; top–; return value;

下面看完整代碼示例：

class Stack{
    public int maxsize;//棧的大小
    public int top=-1;//棧頂
    public int[] arr;

    public Stack(int maxsize) {
        this.maxsize = maxsize;
        arr=new int[maxsize];
    }

    //判斷棧是否為空
    public boolean isEmpty(){
        return top==-1;
    }
    //判斷棧是否滿
    public boolean isFull(){
        return top==maxsize-1;
    }

    //添加一個元素
    public void push(int value){
        if(isFull()){
            throw new RuntimeException("棧滿");
        }
        top++;
        arr[top]=value;
    }
    //彈出一個元素
    public int pop(){
        if(isEmpty())
            throw new RuntimeException("棧空");
        int value=arr[top];
        top--;
        return value;
    }
    //遍歷棧中的元素
    public void traverse(){
        if (isEmpty()){
            return;
        }
        //需要從棧頂開始顯示數(shù)據(jù)
        for(int i = top; i >= 0 ; i--) {
            System.out.printf("stack[%d]=%d\n", i, arr[i]);
        }
        }
    }

入棧操作 top++;arr[top]=value;其實可以直接改寫為arr[++top]=value;
出棧操作可以將 int value=arr[top]; top–;return value;改為return arr[top–];

三、鏈表實現(xiàn)棧

思路分析：

入棧操作：用一個臨時節(jié)點保存當(dāng)前棧頂節(jié)點，將入棧的新節(jié)點作為棧頂元素，并將next域指向原來的舊節(jié)點。 Node temp=top; top.setNext(temp);

出棧操作：先判斷棧是否為空，不為空則將top節(jié)點的數(shù)據(jù)返回，并將top指向top的下一個next域：top=top.getNext();

public class LinkedListStack<V> {
      static class Node<V>{
        private V data;
        private Node<V> next;

        public V getData() {
            return data;
        }

        public void setData(V data) {
            this.data = data;
        }

        public Node<V> getNext() {
            return next;
        }

        public void setNext(Node<V> next) {
            this.next = next;
        }
    }
    public int stackSize;//棧內(nèi)元素的個數(shù)
    public Node<V> top;//棧頂元素

    public LinkedListStack() {
        stackSize = 0;
        top = null;
    }

    //入棧
    public void push(V element){
        Node<V> temp=top;
        top=new Node<>();
        top.setData(element);
        top.setNext(temp);
        stackSize++;
    }
    //出棧
    public V pop(){
        if (isEmpty())
            throw new RuntimeException("empty stack");
        V value=top.getData();
        //棧頂指向下一個元素
        top=top.getNext();
        stackSize--;
        return value;
    }
    //查看棧頂元素
    public V peek(){
        return top.getData();
    }
    //判斷是否為空
    public boolean isEmpty(){
        return stackSize==0;
    }
    //查看棧內(nèi)元素個數(shù)
    public int getStackSize(){
        return stackSize;
    }
    }

四、測試

public class Test {
    public static void main(String[] args) {
        LinkedListStack<String> stack = new LinkedListStack<>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        System.out.println(stack.pop());
        System.out.println(stack.peek());
        System.out.println(stack.getStackSize());
    }
}
測試結(jié)果:
c
b
2

Java有哪些集合類

Java中的集合主要分為四類：1、List列表：有序的，可重復(fù)的；2、Queue隊列：有序，可重復(fù)的；3、Set集合：不可重復(fù)；4、Map映射：無序，鍵唯一，值不唯一。

以上是“如何使用Java數(shù)組和鏈表實現(xiàn)棧”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！