堆疊與佇列

堆疊

概念

堆疊：是限定僅在表尾進行插入和洗掉操作的線性表，

堆疊頂(top)：允許插入和洗掉的一端，即表尾稱為堆疊頂

堆疊底(bottom):表頭稱為堆疊底

堆疊是LIFO結構，后進先出，

與線性表相比，特殊之處在于

限制了線性表的插入和洗掉位置，始終在堆疊頂進行，

所以堆疊底是固定的，最先進堆疊的只能在堆疊底

抽象資料型別

堆疊的順序存盤結構

用陣列實作

ArrayStack.java

package com.stack;

/**
 * 用陣列實作的順序表
 * 限制操作端，使其成為堆疊
 */
public class ArrayStack {

    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStackDemo(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }


    public void push(int value) {
        // 入堆疊
        if (isFull()) {
            System.out.println("堆疊滿了");
            return;
        }

        stack[++top] = value;
    }

    public int pop() {
        // 出堆疊
        if (isEmpty()) {
            throw new RuntimeException("堆疊空");
        }
        return stack[top--];
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("沒有資料");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }
}

堆疊的鏈式存盤結構

簡稱鏈堆疊

LinkStack.java

package com.stack;

/**
 * 因為頭結點是必須的，堆疊頂指標也是必須的，
 * 所以合二為一！即初始化的時候不需要頭結點
 */
public class LinkStack {
    private Node top;

    public boolean isFull() {
        return false;
    }

    public boolean isEmpty() {
        return top == null;
    }


    public void push(int num) {
        // 很少滿堆疊，直接創建結點頭插
        Node node = new Node(num);
        node.next = top;
        top = node;
    }

    public int pop() {
        // 出堆疊
        if (isEmpty()) {
            throw new RuntimeException("堆疊空");
        }
        int value = https://www.cnblogs.com/1101-/p/top.data;
        top = top.next;
        return value;
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("沒有資料");
            return;
        }
        Node temp = top;
        while (temp != null) {
            System.out.print(temp.data+"/t");
            temp = temp.next;
        }
    }

}

class Node{
    public int data;
    public Node next;

    public Node() {
    }

    Node(int data) {
        this.data = data;
    }
}

Java中自帶封裝好的Stack類，可以直接使用，

底層繼承關系 class Stack<E> extends Vector<E>

用陣列存盤，如果堆疊滿會自動擴容，

對比

順序堆疊與鏈堆疊，它們在時間復雜度上是一樣的，均為0（1），

對于空間性能，順序堆疊需要事先確定一個固定的長度，可能會存在記憶體空間浪費的問題，

但它的優勢是存取時定位很方便，

而鏈堆疊則要求每個元素都有指標域，這同時也增加了一些記憶體開銷，但對于堆疊的長度無限制，

所以它們的區別和線性表中討論的一樣，如果堆疊的使用程序中元素變化不可預料，有時很小，

有時非常大，那么最好是用鏈堆疊，反之，如果它的變化在可控范圍內，建議使用順序堆疊會更好一些，

堆疊的作用

遞回
逆波蘭式
中綴轉后綴

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27713.html

標籤：其他

上一篇：空間直線與球面相交演算法

下一篇：0461. Hamming Distance (E)

資料結構-堆疊

堆疊與佇列

堆疊

概念

相關操作

抽象資料型別

堆疊的順序存盤結構

堆疊的鏈式存盤結構

對比

堆疊的作用