佇列 (Queue) 與 堆疊 (Stack) 概念與應用重點

一、佇列 (Queue)
1.概念：佇列是一種先進先出 (FIFO, First In First Out) 的資料結構，表示最先進入佇列的元素最先被移除。
2.應用情境：
排隊系統：例如印表機工作列、排隊叫號系統。
作業系統排程：用來處理作業排程和資源管理。
網路數據緩存：如封包排隊等待處理。
3.操作：
enqueue: 將元素加入佇列末端。
dequeue: 從佇列頭部取出元素。
front: 取得佇列頭部的元素，不移除。
empty: 檢查佇列是否為空。

二、堆疊 (Stack)
1.概念：堆疊是一種後進先出 (LIFO, Last In First Out)的資料結構，表示最後進入堆疊的元素最先被移除。
2.應用情境：
函數呼叫堆疊：在程式執行中管理函數呼叫順序（遞迴尤其依賴堆疊）。
括號匹配：檢查程式中的括號是否正確匹配（如括號、括弧、引號等）。
瀏覽器回退功能：儲存使用者的瀏覽歷史。
3.操作：
push: 將元素放入堆疊頂端。
pop: 從堆疊頂端移除元素。
top: 取得堆疊頂端的元素，不移除。
empty: 檢查堆疊是否為空。

三、佇列與堆疊的差異
1.資料進出順序不同：佇列是先進先出，堆疊是後進先出。
2.應用場景不同：佇列通常用於排隊系統或資源分配，堆疊常用於回溯（如函數呼叫、撤銷操作）。

四、雙端佇列 (Deque)
1.概念：雙端佇列允許從兩端進行元素的插入與刪除操作。
應用情境：
2.滑動視窗演算法：適用於處理不固定大小的資料流問題。
3.調度任務管理：如在作業系統中提供靈活的任務調度。

五、C++ 標準庫中的支援
佇列：使用 std::queue 來實現。
堆疊：使用 std::stack 來實現。
雙端佇列：使用 std::deque 來實現。

!!必須根據具體情境選擇適合的結構來優化程式的運行與資源分配!!

實作小練習(字串旋轉程式):

#include <iostream>
#include <cstdlib> 
using namespace std;

#define NUM 100 

class stack {
public:
    stack();          // 建構子
    void push(char);  // 推入字元至堆疊
    char pop();       // 從堆疊彈出字元
    bool is_empty();  // 檢查堆疊是否為空
private:
    char array[NUM];  // 用來儲存堆疊中的字元
    int top;          // 堆疊頂端索引
};

stack::stack() {
    top = -1;
}

void stack::push(char n) {
    if (top == NUM - 1) { 
        cout << "stack is full!" << endl;
        exit(1); 
    }
    array[++top] = n;
}

char stack::pop() {
    if (top == -1) { 
        cout << "stack is empty!" << endl;
        exit(1); 
    }
    return array[top--]; 
}

bool stack::is_empty() {
    return top == -1;
}

int main() {
    stack S1;      
    char str[100]; 
    while (cin >> str) {  
        char *p = str;
        while (*p) {  
            S1.push(*p);
            p++;
        }
        while (!S1.is_empty()) {  
            cout << S1.pop();
        }
        cout << endl;  
    }
    return 0;
}

說明:
堆疊的基本操作，用來反轉使用者輸入的字串。每次輸入字串時，字元依次被推入堆疊，再從堆疊中彈出並輸出，因此字串被反向顯示。堆疊類別包含 push、pop、和 is_empty 方法，並在堆疊滿或空的情況下處理錯誤。

實作小練習(後續運算式):

#include <iostream>
#include <cstdlib> 
using namespace std;

#define NUM 100 

class stack {
public:
    stack();            // 建構子
    void push(int);     // 推入元素
    int pop();          // 彈出元素
    bool is_empty();    // 判斷堆疊是否為空
    void printStack();  // 顯示堆疊內容 (若需要可以實作)
private:
    int array[NUM];     // 堆疊陣列
    int top;            // 堆疊頂端的索引
};

stack::stack() {
    top = -1;
}

void stack::push(int n) {
    if (top == NUM - 1) {  
        cout << "stack is full!" << endl;
        exit(1);  
    }
    array[++top] = n;
}

int stack::pop() {
    if (top == -1) { 
        cout << "stack is empty!" << endl;
        exit(1);
    }
    return array[top--];
}

bool stack::is_empty() {
    return top == -1;
}

int eval(char *str) {
    stack S1;              // 建立一個堆疊
    char *p = str;         // 指向字串的指標

    while (*p) {           // 逐字元讀取
        if (*p >= '0' && *p <= '9') {  // 如果是數字
            S1.push(*p - '0');         // 將數字轉換為整數推入堆疊
        } else {                       // 處理運算符號
            int op2 = S1.pop();        // 彈出兩個操作數
            int op1 = S1.pop();
            switch (*p) {
                case '+': S1.push(op1 + op2); break;
                case '-': S1.push(op1 - op2); break;
                case '*': S1.push(op1 * op2); break;
                case '/': S1.push(op1 / op2); break;
                default: return -1;     // 無效符號，返回錯誤
            }
        }
        p++;
    }

    return S1.pop();
}

int main() {
    char str[NUM]; 

    while (true) { // 無限迴圈等待使用者輸入
        cout << "請輸入一個 postfix 運算式：" << endl;
        cin >> str; 
        cout << "結果：" << eval(str) << endl;
    }

    return 0;
}

說明:
使用堆疊結構存儲操作數，遇到運算符號時，彈出堆疊中的兩個操作數進行運算，結果再推回堆疊。輸入字串可以包含數字和基本運算符號（+、-、*、/），程式會依據後序表達式的規則來計算並輸出結果。

以上內容是跟著第一次學C++就上手第二版第16章一起做學習的。今天在程式執行上一直遇到困難最後才發現原來是在迴圈的設計上出錯了，明天之後會在更加強程式能力希望能越來越進步!