Stack

- Stack

Stack^[1]

介紹

• 堆疊 或 棧
• 資料遵從 LIFO (Last-In-First-Out)「先進後出」的原則
• 想像你正在放一疊書進去一個箱子，當你往這個箱子裡上放一本新書時，你只能放在最頂端。而要拿出一本書時也只能從最頂端拿，這個箱子就是 Stack
• 可由 Array 或 Linked-List 實作
• 支援3個操作

Operation	Time Complexty	Description
Peek()		查看最頂端的元素
Push()		從最頂端新增一個元素
Pop()		從最頂端移除一個元素

C++ STL - std::stack

• C++ 的 STL(Standard Library) 有提供現成的 std::stack
• Constructor

  Stack(STL ver.)

  // Default Constructor
  std::stack<int> myStack; // Creates an empty stack of integers
  
  // Constructor with Container
  std::vector<int> myVector = {10, 20, 30};
  std::stack<int, std::vector<int>> stackFromVector(myVector); // Creates a stack initialized with elements from the vector
  
  // Copy Constructor
  std::stack<int> originalStack = /* ... */;
  std::stack<int> newStack(originalStack); // Creates a copy of originalStack

• Operations

  Stack(STL ver.)

  std::stack<int> myStack;
  
  // 從最頂端新增一個元素
  std::cout << myStack.push(1) << "\n"; // Stack(from bottom to top): 1
  std::cout << myStack.push(3) << "\n"; // Stack(from bottom to top): 1 3
  std::cout << myStack.push(5) << "\n"; // Stack(from bottom to top): 1 3 5
  std::cout << myStack.push(7) << "\n"; // Stack(from bottom to top): 1 3 5 7
  std::cout << myStack.push(9) << "\n"; // Stack(from bottom to top): 1 3 5 7 9
  
  // 從最頂端移除一個元素 (不會回傳元素)
  myStack.pop()                         // Stack(from bottom to top): 1 3 5 7
  myStack.pop()                         // Stack(from bottom to top): 1 3 5
  
  // 查看最頂端的元素
  std::cout << myStack.top() << "\n";   // 5
  // 查看stack的大小(元素數量)
  std::cout << myStack.size() << "\n";  // 3
  // 查看stack是否為空
  std::cout << myStack.empty() << "\n"; // False

實作 - Array ver.

Stack(Array ver.)

class Stack{
private:
    static const int MAX_SIZE = 100;
    int arr[MAX_SIZE];
    int top;

public:
    // 初始Stack是空的, top=-1
    Stack(){
        top = -1;
    }
    // 判斷Stack是否是空的
    bool isEmpty(){
        return top == -1;
    }
    // 判斷Stack是否是滿的
    bool isFull(){
        return top == MAX_SIZE - 1;
    }
    // 從最頂端新增一個元素
    void push(int value){
        if(isFull()){
            return; // Stack is full
        }
        arr[++top] = value;
    }
    // 從最頂端移除一個元素
    int pop(){
        if(isEmpty()){   
            return -1; // Stack is empty
        }
        return arr[top--];
    }
    // 查看最頂端的元素
    int peek(){
        if(isEmpty()){
            return -1; // Stack is empty
        }
        return arr[top];
    }
};

Stack(Array ver.) - Result

#include <iostream>
using namespace std;

int main(){
    Stack stack;

    stack.push(5); // Push 5 onto the stack
    stack.push(10); // Push 10 onto the stack
    stack.push(15); // Push 15 onto the stack

    cout << "Top: " << stack.peek() << '\n'; // Output: Top: 15

    cout << "Pop: " << stack.pop() << '\n'; // Output: Pop: 15
    cout << "Pop: " << stack.pop() << '\n'; // Output: Pop: 10

    cout << "Is stack empty? " << (stack.isEmpty() ? "Yes" : "No") << '\n'; // Output: Is stack empty? No
}

實作 - Linked-List ver.

Stack(Linked-List ver.)

class Node{
public:
    int data;
    Node* next;

    Node(int value){
        data = value;
        next = nullptr;
    }
};

class Stack{
private:
    Node* top;

public:
    // 初始Stack是空的, top是nullptr
    Stack(){
        top = nullptr;
    }
    // 判斷Stack是否是空的
    bool isEmpty(){
        return top == nullptr;
    }
    // 創立新的node, 指向原本的top, 後將top更新為此node
    void push(int value){
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
    }
    // 將top指向他的下面一個node(top->next), 並刪除原本的top
    int pop(){
        if(isEmpty()){
            return -1;
        }
        Node* temp = top;
        int poppedValue = temp->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }
    // 查看最頂端的node
    int peek(){
        if(isEmpty()){
            return -1;
        }
        return top->data;
    }
};

相關演算法 Related Algorithm

Will be updated later…

• DFS
• Infix to Postfix
• Parentheses Matching

Reference

• [1] Stack Image