今天來說說堆疊，並透過三題Leetcode簡單題型來說明Stack的妙用吧!

堆疊（Stack）是一種基本且常見的資料結構，它在許多應用中發揮著關鍵作用。堆疊的簡單性和特定的操作規則使其成為處理多種問題的有力工具。在深入研究之前，讓我們先來了解一下堆疊的基本特點。

堆疊的特點

1. 只能從頂端新增、刪除資料：在堆疊中，只有堆疊頂端的元素是可訪問的，您可以在頂端新增元素（Push），也可以從頂端刪除元素（Pop）。

2. 遵循後進先出(Last In First Out, LIFO)的原則：最後放入堆疊的元素會最先被取出，這種行為就像一疊碗或盤子，您必須先取出最上面的碗，才能夠取下面的碗。

我們來透過程式來看看是如何操作的吧!

Push

我們可以將資料放入頂部

void Stack::push(int data){
    if(isFull()){
        cout << "stack is full" << endl;
        return;
    }
    else{
        top++;
        stackArray[top] = data;
    }
}

Pop

如果裡面有資料，我們可以取出最上面的資料

int Stack::pop(){
    if(isEmpty()){
        cout << "stack is empty" << endl;
        return -1;
    }
    else{
        int data = stackArray[top];
        top--;
        return data;
    }
}

Top

我們可以查看堆疊頂端的資料

int Stack::top(){
    if(isEmpty()){
        cout << "stack is empty" << endl;
        return -1;
    }
    else{
        return stackArray[top];
    }
}

完整程式碼

# include<iostream>
#include<string>
using namespace std;
const int MAX_SIZE = 10; // 堆疊的最大大小
class Stack{
    private:
        int size;            // 堆疊頂端的索引
        int stackArray[MAX_SIZE]; // 用陣列實現堆疊
    public:
    Stack(){
        size = -1;
    }
    void push(int data); // 將資料放入堆疊
    int pop(); // 將資料從堆疊取出
    int top(); // 查看堆疊頂端的資料
    bool isEmpty(); // 檢查堆疊是否為空
    bool isFull(); // 檢查堆疊是否已滿
    void outputStack(); // 輸出堆疊
};
void Stack::push(int data){
    if(isFull()){
        cout << "stack is full" << endl;
        return;
    }
    else{
        size++;
        stackArray[size] = data;
    }
}
int Stack::pop(){
    if(isEmpty()){
        cout << "stack is empty" << endl;
        return -1;
    }
    else{
        int data = stackArray[size];
        size--;
        return data;
    }
}
int Stack::top(){
    if(isEmpty()){
        cout << "stack is empty" << endl;
        return -1;
    }
    else{
        return stackArray[size];
    }
}
bool Stack::isEmpty(){
    return (size == -1);
}
bool Stack::isFull(){
    return (size == MAX_SIZE-1);
}
void Stack::outputStack(){
    cout << "stack: ";
    for(int i=0; i<=size; i++){
        cout << stackArray[i] << " ";
    }
    cout << endl;
}

int main(){
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.outputStack();
    cout << stack.pop() << endl;
    cout << stack.peek() << endl;
    stack.outputStack();
    return 0;
}

Leetcode

682. Baseball Game

程度

Easy

題目

計算棒球比賽的總分。

• x整數: 新的比分為 x
• '+' : 新的比分為前兩次相加
• 'D' : 新的比分為上一次的兩倍
• 'C' : 刪除上一次的分數。

想法

考慮到新的比分可能受到前兩次比賽的影響，我們可以利用堆疊的「後進先出」特性來記錄這種關係。

程式碼

class Solution {
public:
    int calPoints(vector<string>& operations) {
        int ans = 0;
        int tmp1,tmp2;
        stack<int>score;
        for(string ch :operations){
            if(ch == "+"){
                tmp1 = score.top();
                score.pop();
                tmp2 = score.top();
                score.push(tmp1);
                score.push(tmp1+tmp2);

            }
            else if(ch =="D"){
                tmp1 = score.top();
                score.push(tmp1*2);
            }
            else if(ch == "C"){
                score.pop();
            }
            else{
                score.push(stoi(ch));
            }
        }
        while(score.size()>0){
            ans+=score.top();
            score.pop();
        }
        return ans;
    }
};

1047. Remove All Adjacent Duplicates In String

程度

Easy

題目

當我們面對一串小寫英文字母時，我們可以透過重複地進行檢查，刪除那些相同且相鄰的字母。
舉例來說，考慮一個字串 "abbaca"：
首先，我們檢查並刪除 'bb'，得到 "aaca"。
接著，再次進行檢查，刪除 'aa'，最終獲得 "ca"
。

想法

我們可以運用堆疊（Stack）來存儲一系列字串，然後進行逐一的檢查。在每一次檢查中，我們對比當前的字串是否與堆疊頂部的字串相符。如果它們相符，我們便將頂部的字串彈出（pop）堆疊，這樣可以確保相鄰的字元不相同。

程式碼

class Solution {
public:
    string removeDuplicates(string s) {
        string ans ;
        for (int i=0;i<s.size();i++) {
            if(ans.empty()){
                ans +=s[i];
            }
            else if(ans.back() == s[i])
                ans.pop_back();
            else
                ans +=s[i];
        }
        return ans;
    }
};

1021. Remove Outermost Parentheses

程度

Easy

題目

去除給定字串中外部括號

想法

法一(Stack)

使用堆疊（Stack）來跟蹤當前的左括號。
1.當遇到左括號並且堆疊中已經有左括號時，我們將這個左括號添加到結果中，同時將它壓入堆疊。
2.當遇到右括號時，我們檢查堆疊中是否有多於一個左括號。如果是這樣，表示這個右括號不是最外層的括號，因此我們將這個左括號添加到結果中。然後，從堆疊中彈出一個左括號，以維持跟蹤括號的狀態。

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result;
        stack <char>c;
        for(int i=0;i<s.size();i++){
            if(s[i] == '('){
                if(c.size() > 0){
                    result+= '(';
                }
                c.push('(');
            }
            else{
                if(c.size() > 1){
                    result+= ')';
                }
                c.pop();
            }
        }
        return result;
    }
};

法二(Count)

用count 紀錄現在是否還有更大的括號。
當遇到左括號時，增加計數器的值，而當遇到右括號時，會減少計數器的值。

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result;
        int count=0;
        for(int i=0;i<s.size();i++){
            if(s[i] == '('){
                if(count > 0)
                    result+= '(';
                count++;
            }
            else{
                if(count > 1)
                    result+= ')';
                count--;
            }
        }
        return result;
    }
};

留出適當的時間休息，充電，以及深思熟慮，這將有助於我們更好地前行。(好啦就是我今天只想好好耍廢，各位明天再見