這篇文章主要講解了“如何正確實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)棧”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何正確實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)棧”吧！

公司主營業(yè)務(wù)：成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出撫州免費(fèi)做網(wǎng)站回饋大家。

棧簡介

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

棧常用一維數(shù)組或鏈表來實(shí)現(xiàn)，用數(shù)組實(shí)現(xiàn)的棧叫作 順序棧，用鏈表實(shí)現(xiàn)的棧叫作 鏈?zhǔn)綏?/strong>。

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

數(shù)組實(shí)現(xiàn)

• 對(duì)于數(shù)組來說，我們模擬棧的過程很簡單，因?yàn)闂Ｊ呛筮M(jìn)先出，我們很容易在數(shù)組的末尾進(jìn)行插入和刪除。所以我們選定末尾為棧頂。

/**
 * 棧 數(shù)組實(shí)現(xiàn)
 *
 * @author ervin
 * @Date 2021/4/20
 */
public class ArrayStack {
    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()) {
            //擴(kuò)容
            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();
    }
}

鏈表實(shí)現(xiàn)

• 我們采用帶頭節(jié)點(diǎn)的單鏈表在頭部插入刪除，把頭部當(dāng)中棧頂。插入直接在頭節(jié)點(diǎn)后插入。而刪除也直接刪除頭節(jié)點(diǎn)后第一個(gè)元素即可。

/**
 * 棧 鏈表實(shí)現(xiàn)
 * @author ervin
 * @Date 2021/4/20
 */
public class ListStack {

    private static class Node{
        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;
    }
}

棧的常見應(yīng)用場景

• 實(shí)現(xiàn)瀏覽器的回退和前進(jìn)功能

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

• 檢查符號(hào)是否成對(duì)出現(xiàn)

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

1. 左括號(hào)必須用相同類型的右括號(hào)閉合。

2. 左括號(hào)必須以正確的順序閉合。

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

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

1. 首先我們將括號(hào)間的對(duì)應(yīng)規(guī)則存放在 Map 中，這一點(diǎn)應(yīng)該毋容置疑；

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

• 反轉(zhuǎn)字符串

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

• 維護(hù)函數(shù)調(diào)用

最后一個(gè)被調(diào)用的函數(shù)必須先完成執(zhí)行，符合棧的 后進(jìn)先出（LIFO, Last In First Out） 特性。

感謝各位的閱讀，以上就是“如何正確實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)?！钡膬?nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)如何正確實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)棧這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！