C++中的堆疊和佇列

介紹C 中的堆疊和佇列

堆疊和佇列是C 中常用的資料結構，它們在程式中有著廣泛的應用。本文將對堆疊和佇列的概念、使用方法和應用場景進行詳細介紹。

一、堆疊的概念

堆疊(Stack)是一種線性資料結構，它具有 "先進後出" 的特性。在棧中，越先進棧的數據，越靠近棧底；越後進棧的數據，就越靠近棧頂。

堆疊的主要操作有入棧(push)和出棧(pop)。入棧就是往棧裡添加數據，而出棧則是從棧裡刪除數據。堆疊還有兩個重要的特殊操作：檢查棧頂元素(top)和判斷棧是否為空(empty)。

堆疊的應用場景非常廣泛，例如函數呼叫時就會涉及到堆疊的使用。當函數被呼叫時，它的參數、局部變數等資訊都會被壓入堆疊中。當函數執行結束後，這些資訊就會從堆疊中彈出，恢復到函數呼叫前的狀態。

二、佇列的概念

佇列(Queue)也是一種線性資料結構，它具有 "先進先出" 的特性。在隊列中，越先進隊的數據，越靠近隊頭；越後進隊的數據，越靠近隊尾。

佇列的主要操作有入隊(enqueue)和出隊(dequeue)。入隊就是往隊尾添加數據，而出隊則是從隊頭刪除數據。隊列還有兩個重要的特殊操作：查看隊頭元素(front)和判斷隊列是否為空(empty)。

佇列的應用也非常廣泛，例如作業系統中的進程調度，就可以使用佇列來保存等待執行的進程。當系統資源有空閒時，就從隊頭取出一個行程執行，直到任務全部完成。

三、堆疊和佇列的應用實例

1. 括號符合

在程式設計中，常常需要判斷一個字串中的括號是否符合。例如寫Python程式時，需要檢查程式碼區塊是否正確縮進，就可以使用堆疊來實作。

具體實作方法是，遍歷字串中的每一個字符，當遇到左括號時，將其入堆疊。當遇到右括號時，彈出棧頂元素進行比對。如果匹配成功，則繼續遍歷；否則傳回錯誤訊息。

2. 進程調度

在作業系統中，需要實現對進程的統一調度和協調。這時就可以使用佇列來儲存等待執行的進程，由作業系統決定優先權和執行順序。

具體實作方法是，將每個行程抽象化成一個資料結構，包括行程編號、優先權等資訊。將這些進程放入佇列中，然後依序執行佇列中的進程。當某個行程完成任務後，會被彈出佇列，直到佇列為空。

四、C 中堆疊和佇列的實作

在C 中，可以使用標準函式庫提供的容器類別來實作堆疊和佇列。

1. 堆疊的實作

堆疊可以使用容器類別 std::stack 來實作。

std::stack 是一個模板類，需要指定元素類型和底層容器類型。在未指定底層容器類型時，預設使用 std::deque 作為底層容器。

以下是一個簡單的堆疊的實作範例：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << s.top() << std::endl; // 输出3

    s.pop();

    std::cout << s.top() << std::endl; // 输出2

    while (!s.empty()) {
        s.pop();
    }

    return 0;
}

2. 佇列的實作

佇列可以使用容器類別 std::queue 來實作。

std::queue 也是一個模板類，需要指定元素類型和底層容器類型。在未指定底層容器類型時，預設使用 std::deque 作為底層容器。

以下是一個簡單的佇列的實作範例：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << q.front() << std::endl; // 输出1

    q.pop();

    std::cout << q.front() << std::endl; // 输出2

    while (!q.empty()) {
        q.pop();
    }

    return 0;
}

總結

#透過上述介紹可以看出，堆疊和佇列都是非常實用的資料結構，可以幫助我們解決很多實際問題。在程式設計中，掌握這兩種資料結構的使用方法和實作原理，可以提高程式的效率和可靠性。

以上是C++中的堆疊和佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章！