🎈 作者：Linux猿

🎈 簡介：CSDN博客專家🏆，華為云享專家🏆，C/C++、面試、刷題、演算法盡管咨詢我，關注我，有問題私聊！

🎈 關注專欄：C/C++面試通關集錦 （優質好文持續更新中……）🚀

🎈 歡迎小伙伴們點贊👍、收藏?、留言💬

一、堆疊

1.1 什么是堆疊

1.2 實作方式

1.3 陣列實作堆疊

1.3.0 類封裝

1.3.1 push 操作

1.3.2 pop 操作

1.3.3 empty 操作

1.3.4 top 操作

1.3.5 size 操作

1.3.6 陣列堆疊測驗

1.4 鏈表實作堆疊

1.4.0 類封裝

1.4.1 push 操作

1.4.2 pop 操作

1.4.3 empty 操作

1.4.4 top 操作

1.4.5 size 操作

1.4.6 鏈表堆疊測驗

1.5 實戰分析

1.6 復雜度分析

1.6.1 時間復雜度

1.6.2 空間復雜度

1.7 堆疊的應用

二、佇列

2.1 什么是佇列

2.2 實作方式

2.3 陣列實作佇列

2.3.0 類封裝

2.3.1 push 操作

2.3.2 pop 操作

2.3.3 front 操作

2.3.4 empty 操作

2.3.5 size 操作

2.3.6 back 操作

2.3.7 陣列佇列測驗

2.4 鏈表實作佇列

2.4.0 類封裝

2.4.1 push 操作

2.4.2 pop 操作

2.4.3 front 操作

2.4.4 empty 操作

2.4.5 size 操作

2.4.6 鏈表佇列測驗

2.5 實戰分析

2.6 復雜度分析

2.6.1 時間復雜度

2.6.2 空間復雜度

2.7 佇列的應用

三、總結

在日常的學習以及求職面試中，堆疊和佇列是一塊非常重要的內容，經常被提及，本篇文章總結了堆疊和佇列基本概念及常用操作，并且分別使用陣列和鏈表實作了堆疊和佇列，簡單易懂，想不會都難！趕緊來看下吧！

一、堆疊

1.1 什么是堆疊

堆疊是一種抽象資料結構，也是一種線性資料結構，具有后進先出（LIFO，Last In First Out）的特性，即：后進入堆疊中的元素在先進入元素的上面，故后進入堆疊中的元素先出堆疊，當然也可以說是先進后出，即：先進入的元素后出堆疊，一樣的原理，只是說法不同，如下圖所示：

從上圖可以看到，堆疊只有一個口，即是入口也是出口，后進入堆疊的元素 C，比先進入堆疊的 B 和 A 先出堆疊，這就是所謂的后進先出，如上圖所示，堆疊有堆疊頂和堆疊底，

來看一下動圖，如下所示：

1.2 實作方式

堆疊的實作可以通過陣列或鏈表來實作，如下圖所示：

下面分別來看一下陣列和鏈表來實作堆疊，

1.3 陣列實作堆疊

1.3.0 類封裝

下面用類封裝了堆疊的常用操作，如下所示：

#define NUM 100000 // 堆疊的大小
class Stack {
    int data[NUM];  // 陣列模擬堆疊
    int num;    // 堆疊指標，指向堆疊頂元素
public:
    Stack() {   // 初始化
        num = -1;
        memset(data, 0, sizeof(data));
    }
    void push(int val); // 添加元素
    int pop();          // 洗掉堆疊頂元素
    int top();          // 回傳堆疊頂元素
    bool empty();       // 判斷是否為空
    int size();         // 堆疊大小
};

上面是以 int 為例子，更好的封裝是使用 C++ 的模板，這里為了便于理解采用了更簡單的方式，

另一方面，陣列還可以改成動態分配的形式，即：先分配一個初始陣列，如果堆疊溢位了，則重新分配，將原先的內容拷貝到新分配的陣列中，分配的方式可以參考 STL 的遞增策略，

1.3.1 push 操作

向堆疊中添加元素，如下所示：

void Stack::push(int val) {
    if(num >= NUM) {
        cout<<"Stack Overflow!"<<endl;
        return;
    }
    data[++num] = val;
}

如上所示，先判斷堆疊是否已滿，未滿則添加元素，可以將上面的 if 陳述句里的內容修改為增加堆疊容量，

1.3.2 pop 操作

洗掉堆疊頂元素，因為堆疊是后進先出的，如下所示：

int Stack::pop() {
    if(empty()) {
        cout<<"Stack Empty!"<<endl;
        return -1;
    }
    return data[num--];
}

如上所示，先判斷堆疊是否為空，不空則洗掉堆疊頂元素，只要堆疊頂指標移動即可，

1.3.3 empty 操作

判斷堆疊是否為空，慷訓傳 true，否則回傳 false ，如下所示：

bool Stack::empty() {
    return num == -1;
}

這里也許有人會說“為啥不用 int 型別，回傳 0 和 1 呢？用 true 和 false 更好是因為 bool 型別占一個位元組，而 int 通常占 4 個位元組，

1.3.4 top 操作

回傳堆疊頂元素，如下所示：

int Stack::top() {
    if(empty()) {
        cout<<"Stack Empty!"<<endl;
        return -1;
    }
    return data[num];
}

先判斷堆疊是否為空，如果非空則回傳堆疊頂元素，

注意：這里不是洗掉，僅僅是回傳堆疊頂元素的值，

1.3.5 size 操作

回傳堆疊大小，如下所示：

int Stack::size() {
    return num + 1;
}

堆疊指標 num 是從 0 開始的，故回傳 num+1，

1.3.6 陣列堆疊測驗

下面是測驗上面的陣列堆疊實作，如下所示：

int main()
{
    Stack st;

    st.push(10);
    st.push(20);
    cout<<"The size of stack is "<<st.size()<<endl;
    cout<<"The top of stack is "<<st.top()<<endl;
    cout<<"The stack empty is "<<st.empty()<<endl;
    cout<<"----------------------------------------"<<endl;

    st.pop();
    cout<<"The size of stack is "<<st.size()<<endl;
    cout<<"The top of stack is "<<st.top()<<endl;
    cout<<"----------------------------------------"<<endl;
    return 0;
}

輸出為：

The size of stack is 2
The top of stack is 20
The stack empty is 0
----------------------------------------
The size of stack is 1
The top of stack is 10
----------------------------------------

1.4 鏈表實作堆疊

1.4.0 類封裝

使用類封裝堆疊，如下所示：

struct node { // 鏈表單個節點
    int val;  // 存盤堆疊元素值
    struct node* next;// 指向下一個元素的指標
    node(int value) { // 賦初值
        val = value;
    }
};

class Stack {
    struct node *index; // 指向堆疊頂元素
    int s_size; // 記錄堆疊容量
public:
    Stack() { // 初始化
        index = nullptr;
        s_size = 0;
    }
    ~Stack() ;
    void push(int val); // 添加元素
    int pop();          // 洗掉堆疊頂元素
    int top();          // 回傳堆疊頂元素
    bool empty();       // 判斷是否為空
    int size();         // 堆疊大小
};

struce node 是鏈表中的單個元素， class Stack 包含堆疊的各種操作，這里使用 s_size 記錄堆疊的容量，便于操作，當然，這里是以 int 為例，可以將其修改為 C++ 的模板形式，

1.4.1 push 操作

向堆疊中添加元素，如下所示：

void Stack::push(int val) {
    struct node* tmp = new node(val);
    if(tmp == nullptr) {
        cout<<"Failed to allocate space!"<<endl;
        return;
    }
    tmp->next = index;
    index = tmp;
    s_size++;
}

如上所示，這里不用判斷堆疊是否已滿，需要判斷一個是否分配成功，

1.4.2 pop 操作

洗掉堆疊頂元素，因為堆疊是后進先出的，如下所示：

int Stack::pop() {
    if(empty()) {
        cout<<"Stack Empty!"<<endl;
        return -1;
    }
    int tmpVal = index->val; // 暫存堆疊頂元素
    index = index->next; // 洗掉堆疊頂元素
    s_size--;            // 堆疊元素個數減一
    return tmpVal; // 這個回傳下堆疊頂元素
}

如上所示，先判斷堆疊是否為空，不空則洗掉堆疊頂元素，只要堆疊頂指標移動即可，

1.4.3 empty 操作

判斷堆疊是否為空，慷訓傳 true，否則回傳 false ，如下所示：

bool Stack::empty() {
    return index == nullptr;
}

1.4.4 top 操作

回傳堆疊頂元素，如下所示：

int Stack::top() {
    if(empty()) {
        cout<<"Stack Empty!"<<endl;
        return -1;
    }
    return index->val; // 僅僅回傳堆疊頂元素
}

因為 index 一直指向堆疊頂元素，所以直接回傳 index->val，

1.4.5 size 操作

回傳堆疊大小，如下所示：

int Stack::size() {
    return s_size;
}

這里使用 s_size 記錄堆疊大小，不然每次都要遍歷鏈表，

1.4.6 鏈表堆疊測驗

下面是測驗上面的鏈表堆疊實作，如下所示：

int main()
{
    Stack st;

    st.push(10);
    st.push(20);
    cout<<"The size of stack is "<<st.size()<<endl;
    cout<<"The top of stack is "<<st.top()<<endl;
    cout<<"The stack empty is "<<st.empty()<<endl;
    cout<<"----------------------------------------"<<endl;

    st.pop();
    cout<<"The size of stack is "<<st.size()<<endl;
    cout<<"The top of stack is "<<st.top()<<endl;
    cout<<"----------------------------------------"<<endl;
    return 0;
}

輸出為：

linuxy@linuxy:~/Stack$ g++ -o main Stack.cpp 
linuxy@linuxy:~/Stack$ ./main 
The size of stack is 2
The top of stack is 20
The stack empty is 0
----------------------------------------
The size of stack is 1
The top of stack is 10
----------------------------------------
linuxy@linuxy:~/Stack$

1.5 實戰分析

模擬元素堆疊操作，如何實作從下面的入堆疊順序到出堆疊順序，

入堆疊順序：A B C D

出堆疊順序：C B D A

如上所示，需要找到一種方法，實作從入站次序到出站次序，這是堆疊經常考的題目，步驟如下：

（1）因為第一個出站的是 C，所以 A，B ，C依次入堆疊；

（2）這時，C 在堆疊頂，C 出堆疊；

（3）因為第二個出堆疊的是 B，當前堆疊頂為 B，所以直接讓 B 出堆疊；

（4）B 出堆疊后，當前堆疊頂為 A，但是，應該是 D 出堆疊，所以先讓 D 進堆疊；

（5）當前堆疊頂為 D，下一個出堆疊元素為 D，讓 D 出堆疊；

（6）當前堆疊頂元素為 A，下一個出堆疊元素對應 A，所以 A 出堆疊；

下面來看下動圖：

1.6 復雜度分析

1.6.1 時間復雜度

不管是鏈表實作的堆疊，還是陣列實作的堆疊，push 和 pop 操作的時間復雜度都是O(1)的，鏈表實作的堆疊中 clear 操作是O(n)的，因為需要釋放所有的鏈表空間，其它操作都是O(1)的，

1.6.2 空間復雜度

鏈表相對于陣列更節省空間，因為鏈表使用到才會分配，陣列是提前分配好，而且如果堆疊滿時，陣列還需要重新分配，

1.7 堆疊的應用

（1）深度優先搜索

深度優先搜索的非遞回實作通常使用堆疊作為輔助的陣列結構，

（2）軟體中的回退和前進功能

（3）拓撲排序

二、佇列

2.1 什么是佇列

佇列是一種線性結構的抽象資料型別，可以實作先進先出（FIFO，First In，First Out），即：先進入的元素，先出佇列，可以比喻為日常排隊買東西，

如下圖所示：

從上圖可以看到，佇列和堆疊不同，佇列有兩個口，而且是一個只允許進入元素，一個只允許出元素，后進入堆疊的元素C，比先進入堆疊的 B 和 A 先出堆疊，這就是所謂的后進先出，如上圖所示，堆疊有堆疊頂和堆疊底，

來看一下動圖，如下所示：

2.2 實作方式

佇列的實作可以通過陣列或鏈表來實作，如下圖所示：

2.3 陣列實作佇列

2.3.0 類封裝

下面是使用類封裝了佇列，如下所示：

#define NUM 100000 // 佇列大小
class Queue {
    int data[NUM];  // 陣列模擬佇列
    int first;      // 頭指標，指向佇列頂部
    int last;       // 尾指標，指向佇列尾部
public:
    Queue() {   // 初始化
        first = 0;
        last = 0;
        memset(data, 0, sizeof(data));
    }
    void push(int val); // 添加元素
    int pop();          // 洗掉佇列頭元素
    int front();        // 回傳佇列頭元素
    bool empty();       // 判斷是否為空
    int size();         // 佇列大小
    int back();         // 回傳佇列尾元素
};

data 存盤佇列資料，first 和 last 分別指向佇列頭部和尾部，

2.3.1 push 操作

向佇列中添加元素，如下所示：

void Queue::push(int val) {
    if(last >= NUM) {
        cout<<"Queue Overflow!"<<endl;
        return;
    }
    data[last++] = val;
}

先判斷佇列是否已滿，未滿則添加元素，添加元素只需要移動尾指標即可，

2.3.2 pop 操作

洗掉佇列頭元素，如下所示：

int Queue::pop() {
    if(empty()) {
        cout<<"Queue Empty!"<<endl;
        return -1;
    }
    return data[first++];
}

如上所示，先判斷佇列是否為空，不空則洗掉佇列頭元素，只需要頭指標 first 移動即可，

2.3.3 front 操作

回傳頭元素的值，和堆疊的 top 操作相同的原理，如下所示：

int Queue::front() {
    if(empty()) {
        cout<<"Queue Empty!"<<endl;
        return -1;
    }
    return data[first];
}

先判斷佇列是否為空，非空則回傳頭元素，

2.3.4 empty 操作

判斷佇列是否為空，如下所示：

bool Queue::empty() {
    return first == last;
}

直接比較 first 與 last 是否相等即可，

2.3.5 size 操作

判斷佇列元素個數，如下所示：

int Queue::size() {
    return last - first;
}

使用佇列尾指標與頭指標之前的舉例便是元素個數，

2.3.6 back 操作

回傳佇列尾元素，如下所示：

int Queue::back() {
    if(empty()) {
        cout<<"Queue Empty!"<<endl;
        return -1;
    }
    return data[last-1];
}

先判斷是否為空，不為空則回傳 last - 1 所在的元素，因為 last 指向尾元素的下一個位置，

2.3.7 陣列佇列測驗

下面是對上面陣列實作的佇列的測驗，如下所示：

int main()
{
    Queue que;

    cout<<"The queue empty is "<<que.empty()<<endl;
    cout<<"The size of queue is "<<que.size()<<endl;
    cout<<"----------------------------------------"<<endl;
    que.push(10);
    que.push(20);
    cout<<"The size of queue is "<<que.size()<<endl;
    cout<<"The front of queue is "<<que.front()<<endl;
    cout<<"The queue empty is "<<que.empty()<<endl;
    cout<<"----------------------------------------"<<endl;

    que.pop();
    cout<<"The size of queue is "<<que.size()<<endl;
    cout<<"The front of queue is "<<que.front()<<endl;

    return 0;
}

輸出為：

linuxy@linuxy:~/Stack$ ./main 
The queue empty is 1
The size of queue is 0
----------------------------------------
The size of queue is 2
The front of queue is 10
The queue empty is 0
----------------------------------------
The size of queue is 1
The front of queue is 20
linuxy@linuxy:~/Stack$

2.4 鏈表實作佇列

2.4.0 類封裝

struct node {   // 鏈表節點
    int val;    // 鏈表值
    struct node* next;
    node(int value) {
        val = value;
    }
};

class Queue {
    struct node *first; // 指向佇列頭元素
    struct node *rear;  // 指向佇列尾元素
    int s_size;         // 記錄佇列元素個數
public:
    Queue() { // 初始化
        first = nullptr;
        rear = nullptr;
        s_size = 0;
    }
    ~Queue();
    void push(int val);  // 添加元素
    int pop();           // 洗掉佇列頭元素
    int front();         // 回傳佇列頭元素
    bool empty();        // 判斷是否為空
    int size();          // 佇列元素個數
    void back();         // 回傳佇列尾元素
};

first 指向佇列頭元素，rear 指向佇列尾元素，s_size 記錄佇列中的元素個數，

2.4.1 push 操作

向佇列中添加元素，添加到佇列尾部，因為佇列是先進先出，如下所示：

void Queue::push(int val) {
    struct node* tmp = new node(val);
    if(tmp == nullptr) {
        cout<<"Failed to allocate space!"<<endl;
        return;
    }
    if(rear == nullptr) { // 添加第一個元素
        first = tmp;
        rear = tmp;
        tmp->next = nullptr;
    } else {              // 已有元素
        rear->next = tmp;
        tmp->next = nullptr;
        rear = tmp;
    }

    s_size++;
}

這里需要先分配空間，第一次添加元素需要將 first 和 rear 都指向該元素，否則添加到尾部即可，別忘記增加 s_size，

2.4.2 pop 操作

洗掉佇列頭元素，如下所示：

int Queue::pop() {
    if(empty()) {
        cout<<"Stack Empty!"<<endl;
        return -1;
    }
    struct node* tmp = first;
    first = first->next;
    int val = tmp->val;
    delete tmp;

    s_size--;
    return val;
}

先判斷佇列是否為空，不為空則移動佇列頭指標，別忘記釋放空間，

2.4.3 front 操作

回傳佇列頭元素的值，并不是洗掉哦！如下所示：

int Queue::front() {
    if(empty()) {
        cout<<"Stack Empty!"<<endl;
        return -1;
    }
    return first->val;
}

佇列的 front 和堆疊的 top 原理類似，

2.4.4 empty 操作

判斷佇列是否為空，如下所示：

bool Queue::empty() {
    return first == nullptr;
}

2.4.5 size 操作

判斷佇列元素個數，如下所示：

int Queue::size() {
    return s_size;
}

這里使用了一個輔助變數 s_size，不然每次求佇列元素個數都需要遍歷一次鏈表，

2.4.6 鏈表佇列測驗

下面是測驗上面的鏈表佇列的實作，如下所示：

int main()
{
    Queue que;

    cout<<"The queue empty is "<<que.empty()<<endl;
    cout<<"The size of queue is "<<que.size()<<endl;
    cout<<"----------------------------------------"<<endl;

    que.push(10);
    que.push(20);
    cout<<"The size of queue is "<<que.size()<<endl;
    cout<<"The top of queue is "<<que.front()<<endl;
    cout<<"The queue empty is "<<que.empty()<<endl;
    cout<<"----------------------------------------"<<endl;

    que.pop();
    cout<<"The size of queue is "<<que.size()<<endl;
    cout<<"The top of queue is "<<que.front()<<endl;
    cout<<"----------------------------------------"<<endl;

    return 0;
}

輸出結果為：

linuxy@linuxy:~/Queue$ ./main 
The queue empty is 1
The size of queue is 0
----------------------------------------
The size of queue is 2
The top of queue is 10
The queue empty is 0
----------------------------------------
The size of queue is 1
The top of queue is 20
----------------------------------------
linuxy@linuxy:~/Queue$

2.5 實戰分析

采用層次遍歷的方法遍歷如下二叉樹：

層次遍歷上圖的二叉樹，即：從上到下一層一層的遍歷二叉樹的節點，按照這個思路，遍歷步驟為：

（1）先訪問 1 節點，1節點有兩個孩子節點，1 節點出佇列后，將 2 和 3 兩個節點入隊；

（2）訪問 2 節點，2 節點出隊，2 節點有兩個子節點 4 和 5，2 節點出隊后，4 和 5 節點入隊；

（3）訪問 3 節點，3 節點沒有子節點，直接出隊；

（4）依次訪問 4 和 5 節點，這兩個節點都沒有子節點，所以出隊即可，

（5）所有節點按照層次遍歷的方式訪問完畢！

來看一下動圖：

2.6 復雜度分析

2.6.1 時間復雜度

不管是鏈表實作的佇列，還是陣列實作的佇列，push、pop、empty、front 等操作的時間復雜度都是O(1)的，

2.6.2 空間復雜度

鏈表相對于陣列更節省空間，因為鏈表使用到才會分配，陣列是提前分配好，而且如果佇列滿時，陣列還需要重新分配，

2.7 佇列的應用

（1）廣度優先搜索

廣度優先搜索的實作通常使用佇列作為輔助的陣列結構，

（2）在一些資源請求或任務調度中，往往是先來先處理，

三、總結

堆疊和佇列都有很強的特性，堆疊是后進先出，佇列是先進先出，應用在不同的應用場景中，

歡迎關注下方👇👇👇公眾號👇👇👇，獲取更多優質內容🤞（比心）！

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

標籤：java

上一篇：畢業半年，識訓人生第一個一百萬，聊聊我的四年大學

下一篇：Java 常用類

??[資料結構]動圖+萬字詳解堆疊和佇列（動圖+實體）【建議收藏】??

一、堆疊

1.1 什么是堆疊

1.2 實作方式

1.3 陣列實作堆疊

1.3.0 類封裝

1.3.1 push 操作

1.3.2 pop 操作

1.3.3 empty 操作

1.3.4 top 操作

1.3.5 size 操作

1.3.6 陣列堆疊測驗

1.4 鏈表實作堆疊

1.4.0 類封裝

1.4.1 push 操作

1.4.2 pop 操作

1.4.3 empty 操作

1.4.4 top 操作

1.4.5 size 操作

1.4.6 鏈表堆疊測驗

1.5 實戰分析

1.6 復雜度分析

1.6.1 時間復雜度

1.6.2 空間復雜度

1.7 堆疊的應用

二、佇列

2.1 什么是佇列

2.2 實作方式

2.3 陣列實作佇列

2.3.0 類封裝

2.3.1 push 操作

2.3.2 pop 操作

2.3.3 front 操作

2.3.4 empty 操作

2.3.5 size 操作

2.3.6 back 操作

2.3.7 陣列佇列測驗

2.4 鏈表實作佇列

2.4.0 類封裝

2.4.1 push 操作

2.4.2 pop 操作

2.4.3 front 操作

2.4.4 empty 操作

2.4.5 size 操作

2.4.6 鏈表佇列測驗

2.5 實戰分析

2.6 復雜度分析

2.6.1 時間復雜度

2.6.2 空間復雜度

2.7 佇列的應用

三、總結