如何正確實現數據結構棧

這篇文章主要講解了“如何正確實現數據結構棧”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何正確實現數據結構棧”吧！

棧簡介

棧 (stack)只允許在有序的線性數據集合的一端（稱為棧頂 top）進行加入數據（push）和移除數據（pop）。因而按照 后進先出（LIFO, Last In First Out） 的原理運作。在棧中，push 和 pop 的操作都發生在棧頂。

棧常用一維數組或鏈表來實現，用數組實現的棧叫作 順序棧 ，用鏈表實現的棧叫作 鏈式棧 。

• 舉個例子：就像疊盤子 一樣，后放的盤子總是在上面，拿盤子時是從上面拿，也就是先拿后來放上面的盤子，最后的盤子是最早放的。

數組實現

• 對于數組來說，我們模擬棧的過程很簡單，因為棧是后進先出，我們很容易在數組的末尾進行插入和刪除。所以我們選定末尾為棧頂。

/**
 * 棧 數組實現
 *
 * @author ervin
 * @Date 2021/4/20
 */
public class ArrayStack<T> {
    private Object[] data;
    //棧頂
    private int top;

    public ArrayStack(int size) {
        this.data = new Object[size];
        this.top = -1;
    }

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

    public boolean isFull() {
        return this.top == data.length - 1;
    }

    public void push(T t) throws Exception {
        if (isFull()) {
            //擴容
            Object[] newDate = new Object[top * 2];
            for (int i = 0; i <= top; i++) {
                newDate[i] = this.data[i];
            }
            data = newDate;
        }
        data[++top] = t;
    }

    public T pop() throws Exception {
        if (isEmpty()) {
            throw new Exception("stack empty");
        }
        return (T) data[top--];
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < data.length; i++) {
            builder.append("index:" + i + "value:" + data[i]).append("\n");
        }
        return builder.toString();
    }
}

鏈表實現

• 我們采用帶頭節點的單鏈表在頭部插入刪除，把頭部當中棧頂。插入直接在頭節點后插入。而刪除也直接刪除頭節點后第一個元素即可。

/**
 * 棧 鏈表實現
 * @author ervin
 * @Date 2021/4/20
 */
public class ListStack<T> {

    private static class Node<T>{
        T item;
        Node next;
        Node(T ele,Node next){
            this.item = ele;
            this.next = next;
        }
    }

    private Node header;
    private int size;

    ListStack() {
        this.header = new Node(null,null);
        this.size = 0;
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void push(T data){
        Node n = null;
        if (header.next != null){
            n = new Node(data,header.next);
        } else{
            n = new Node(data,null);
        }
        this.header.next = n;
        size++;
    }

    public T pop() throws Exception {
        if (this.header.next == null){
            throw new Exception("stack empty");
        }
        Node n = this.header.next;
        if (n.next != null){
            this.header.next = n.next;
        } else {
            this.header.next = null;
        }
        size--;
        return (T)n.item;
    }
}

棧的常見應用場景

• 實現瀏覽器的回退和前進功能

我們只需要使用兩個棧(Stack1 和 Stack2)和就能實現這個功能。比如你按順序查看了 1,2,3,4 這四個頁面，我們依次把 1,2,3,4 這四個頁面壓入 Stack1 中。當你想回頭看 2 這個頁面的時候，你點擊回退按鈕，我們依次把 4,3 這兩個頁面從 Stack1 彈出，然后壓入 Stack2 中。假如你又想回到頁面 3，你點擊前進按鈕，我們將 3 頁面從 Stack2 彈出，然后壓入到 Stack1 中。

• 檢查符號是否成對出現

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串， 判斷該字符串是否有效。 有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。

2. 左括號必須以正確的順序閉合。

比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]" 、"([)]" 則不是。

這個問題實際是 Leetcode 的一道題目，我們可以利用棧 Stack 來解決這個問題。

1. 首先我們將括號間的對應規則存放在 Map 中，這一點應該毋容置疑；

2. 創建一個棧。遍歷字符串，如果字符是左括號就直接加入stack中，否則將stack 的棧頂元素與這個括號做比較，如果不相等就直接返回 false。遍歷結束，如果stack為空，返回 true。

• 反轉字符串

將字符串中的每個字符先入棧再出棧就可以了。

• 維護函數調用

最后一個被調用的函數必須先完成執行，符合棧的 后進先出（LIFO, Last In First Out） 特性。

感謝各位的閱讀，以上就是“如何正確實現數據結構棧”的內容了，經過本文的學習后，相信大家對如何正確實現數據結構棧這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！