Stack

Stack คืออะไร

Stack เป็นโครงสร้างข้อมูลแบบ linear ที่ทำงานตามหลักการ "เข้าหลังออกก่อน" (Last In, First Out - LIFO) หมายความว่าข้อมูลตัวสุดท้ายที่ถูกเพิ่มเข้าไปใน stack จะเป็นตัวแรกที่ถูกดึงออกมาใช้งาน Stack ถูกใช้อย่างแพร่หลายในงานหลายประเภท ไม่ว่าจะเป็นการกลับลำดับตัวอักษรในข้อความ การวิเคราะห์ expressions ไปจนถึงการจัดการลำดับการทำงานของ function ในภาษาโปรแกรม

ประเภทของ Stack

โดยหลักแล้วสแตกสามารถแบ่งออกเป็น 2 ประเภทตามวิธีการ implement ได้แก่

1. Array-based Stack สร้างโดยใช้ Array ในการเก็บข้อมูล Stack ประเภทนี้จะมีขนาดที่คงที่ หมายความว่า เราต้องกำหนดขนาดสูงสุดของ Stack ไว้ตั้งแต่เริ่มต้น

และนี่คือ code ตัวอย่างของ Array-based Stack

#include <iostream>
#define MAX_SIZE 100 // Defining the maximum size of the stack

class Stack {
private:
  int top;
  int arr[MAX_SIZE];

public:
  Stack() { top = -1; }

  // Function to add an item to the stack. It increases top by 1
  void push(int x) {
    if (top >= (MAX_SIZE - 1)) {
      std::cout << "Stack Overflow" << std::endl;
    } else {
      arr[++top] = x;
      std::cout << x << " pushed into stack\n";
    }
  }

  // Function to remove an item from the stack. It decreases top by 1
  int pop() {
    if (top < 0) {
      std::cout << "Stack Underflow" << std::endl;
      return 0;
    } else {
      int x = arr[top--];
      return x;
    }
  }

  // Function to return the top element of the stack without removing it
  int peek() {
    if (top < 0) {
      std::cout << "Stack is Empty" << std::endl;
      return 0;
    } else {
      int x = arr[top];
      return x;
    }
  }

  // Function to check if the stack is empty
  bool isEmpty() { return (top < 0); }
};

int main() {
  Stack s;
  s.push(10);
  s.push(20);
  std::cout << "Top element is " << s.peek() << std::endl;
  std::cout << "Popped from stack: " << s.pop() << std::endl;
  return 0;
}

2. Linked List-based Stack สร้างโดยใช้ Linked List โดย Stack ประเภทนี้สามารถเพิ่มขนาดได้แบบไดนามิก ทำให้ไม่มีการจำกัดขนาดตายตัว

code ตัวอย่างของการใช้ Stack แบบ Linked List

#include <iostream>

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

class Stack {
private:
  Node *top;

public:
  Stack() { top = nullptr; }

  // Function to add an item to the stack. It changes the top pointer
  void push(int x) {
    Node *newNode = new Node();
    newNode->data = x;
    newNode->next = top;
    top = newNode;
    std::cout << x << " pushed into stack\n";
  }

  // Function to remove an item from the stack. It changes the top pointer
  int pop() {
    if (top == nullptr) {
      std::cout << "Stack Underflow" << std::endl;
      return 0;
    }
    Node *temp = top;
    int poppedValue = top->data;
    top = top->next;
    delete temp;
    return poppedValue;
  }

  // Function to check if the stack is empty
  bool isEmpty() { return top == nullptr; }

  // Function to return the top element of the stack without removing it
  int peek() {
    if (!isEmpty()) {
      return top->data;
    } else {
      std::cout << "Stack is empty" << std::endl;
      return -1;
    }
  }
};

int main() {
  Stack s;
  s.push(10);
  s.push(20);
  std::cout << "Top element is " << s.peek() << std::endl;
  std::cout << "Popped from stack: " << s.pop() << std::endl;
  return 0;
}

ทั้งสองตัวอย่างที่ให้มาแสดงให้เราเห็นการทำงานพื้นฐานของ Stack ไม่ว่าจะเป็น push (เพิ่มข้อมูล), pop (ดึงข้อมูลตัวบนสุดออก), peek (ดูข้อมูลตัวบนสุดโดยไม่ดึงข้อมูลนั้นออก) และ isEmpty (ตรวจสอบว่า Stack ว่างหรือไม่) การจะเลือกใช้ Stack แบบไหน ขึ้นอยู่กับความต้องการของโปรแกรมที่เราจะนำไปใช้ โดยจะต้องพิจารณาเรื่องหน่วยความจำ ประสิทธิภาพการทำงาน และความซับซ้อนของการใช้งานของเราด้วยเช่นกัน

Stack กับ STL

C++ Standard Template Library (STL) มี container adapter ชื่อ stack ให้เราใช้งาน โดย std::stack จะมีลักษณะเป็นโครงสร้างข้อมูลแบบเข้าหลังออกก่อน (LIFO) ซึ่งข้อมูลจะถูกเพิ่มและลบจากด้านใดด้านหนึ่งของ container เราเรียกด้านนี้ว่าด้านบน (top) ของสแตก

std::stack จะทำงานเป็น adapter ครอบ container อื่นๆ ของ STL ไม่ว่าจะเป็น std::deque, std::list หรือ std::vector โดยค่าเริ่มต้นนั้น ถ้าเราไม่ได้ระบุ container อย่างเจาะจงให้กับ stack ตัว std::deque จะเป็นตัวหลักถูกเลือกมาใช้งานกับ stack

การทำงานหลักๆ ของ std::stack ประกอบด้วย

• push(g) เพิ่มข้อมูล 'g' เข้าไปที่ด้านบนของ stack
• pop() ลบข้อมูลที่อยู่ด้านบนของ stack ออก (ไม่มีการคืนค่าของข้อมูลที่ถูกลบ)
• top() คืนค่าตัวชี้ (reference) ของข้อมูลที่อยู่บนสุดของ stack
• empty() ตรวจสอบว่า stack ว่างอยู่หรือไม่ (คืนค่าเป็น boolean)
• size() ตรวจสอบจำนวนข้อมูลที่อยู่ใน stack

ตัวอย่างการใช้งาน

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

int main() {
  stack<int> myStack;

  // Push elements into the stack
  myStack.push(10);
  myStack.push(20);
  myStack.push(30);

  cout << "The top element is: " << myStack.top() << endl;

  // Pop an element from the stack
  myStack.pop();
  cout << "After popping, the top element is: " << myStack.top() << endl;

  // Check if the stack is empty
  if (!myStack.empty()) {
    cout << "The stack is not empty" << endl;
  }

  // Print the size of the stack
  cout << "The stack size is: " << myStack.size() << endl;

  return 0;
}

code ตัวอย่างนี้แสดงให้เห็นถึงการสร้าง stack สำหรับเก็บตัวเลขจำนวนเต็ม การเพิ่มข้อมูลลง stack (push) การเข้าถึงข้อมูลด้านบนสุด (top) การลบข้อมูลด้านบนออก (pop) รวมถึงการตรวจสอบว่า stack ว่างหรือไม่ และดูขนาดของ stack ด้วย

Stack adapter ช่วยให้เราทำงานกับโครงสร้างข้อมูลแบบ LIFO ได้สะดวกขึ้น โดยที่เราไม่ต้องไปยุ่งเกี่ยวกับรายละเอียดเบื้องลึกของ container ที่ถูกใช้งานอยู่ได้

Stack กับ Usecase

ตัวอย่าง classic ที่ทำให้เราเห็นภาพการใช้ stack ใน software แบบชัดเจน 1 use case ก็คือการสร้าง function "ย้อนกลับ" (Undo) ในโปรแกรมประมวลผลข้อความหรือ software สำหรับออกแบบกราฟิกทั่วไป function นี้จะทำให้ผู้ใช้สามารถย้อนกลับการกระทำได้ทีละขั้นตอนได้ ซึ่งเป็นลักษณะการทำงานที่ใช้ได้กับหลักการ "เข้าหลังออกก่อน" (LIFO) ของ stack นั่นเอง

Scenario: "Undo" Feature สำหรับ Text Editor

โจทย์ ในโปรแกรมประมวลผลข้อความ ผู้ใช้จะทำการกระทำต่างๆ อย่างการพิมพ์ข้อความ ลบข้อความ จัดรูปแบบ ฯลฯ เพื่อเพิ่มประสบการณ์การใช้งานที่ดี โปรแกรมควรจะให้ผู้ใช้สามารถย้อนกลับ (undo) การกระทำล่าสุดได้ทีละหนึ่งขั้นได้ และลำดับในการย้อนกลับจะต้องตรงข้ามกับลำดับที่ผู้ใช้ได้ทำการกระทำเหล่านั้นไว้ (กลับไปยังการกระทำก่อนหน้าได้)

วิธีแก้ปัญหาโดยใช้ Stack เพื่อสร้าง function "Undo" เราสามารถใช้ stack ในการติดตามการกระทำของผู้ใช้ได้ การกระทำแต่ละครั้งจะถูกเพิ่ม (push) เข้าไปใน stack เมื่อผู้ใช้ต้องการย้อนกลับการกระทำ (undo) โปรแกรมจะดึงการกระทำล่าสุดออกมาจาก stack (pop) และทำการย้อนกลับกระทำนั้นได้

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// Define an Action structure to represent user actions.
struct Action {
  string type; // The type of action (e.g., "add", "delete")
  string data; // Data involved in the action (e.g., the text added or deleted)

  Action(string type, string data) : type(type), data(data) {}
};

class TextEditor {
private:
  stack<Action>
      actions; // Stack to keep track of actions for undo functionality

public:
  void performAction(const Action &action) {
    // Perform the action and push it onto the stack
    cout << "Performing action: " << action.type << " '" << action.data << "'"
         << endl;
    actions.push(action);
  }

  void undoAction() {
    if (actions.empty()) {
      cout << "No actions to undo." << endl;
      return;
    }

    // Pop the most recent action from the stack and undo it
    Action action = actions.top();
    actions.pop();
    cout << "Undoing action: " << action.type << " '" << action.data << "'"
         << endl;
    // Here, you would add code to actually reverse the action's effect
  }
};

int main() {
  TextEditor editor;

  // Simulate user actions
  editor.performAction(Action("add", "Hello"));
  editor.performAction(Action("add", " World"));
  editor.performAction(Action("delete", "World"));

  // Undo the last action
  editor.undoAction(); // Should undo "delete 'World'"
  editor.undoAction(); // Should undo "add ' World'"

  return 0;
}

ตัวอย่างแบบนี้แสดงให้เห็นถึงวิธีที่ Stack สามารถนำมาใช้ได้ ในการสร้าง feature "ย้อนกลับ" (Undo) สำหรับโปรแกรมประเภทแก้ไขข้อความ แต่ละคำสั่งหรือการกระทำจะถูกเก็บไว้ใน Stack ในรูปแบบของ Object ที่เรียกว่า Action เมื่อผู้ใช้ต้องการย้อนกลับการกระทำ โปรแกรมจะดึง Action ล่าสุดออกจาก Stack และดำเนินการย้อนกลับกระบวนการ วิธีการนี้ใช้ประโยชน์จากลักษณะ "เข้าหลังออกก่อน" (LIFO) ของ Stack ซึ่งทำให้มั่นใจได้ว่าการย้อนกลับจะถูกต้องตามลำดับย้อนหลังได้

use case อื่นๆ

1. Function Call Management Stacks ถูกใช้เพื่อดูแลการเรียกใช้งาน function ในภาษาโปรแกรม เมื่อใดที่ function ถูกเรียก address (ตำแหน่ง) ของ function และตัวแปรต่างๆ จะถูก "push" เข้าไปใน call stack เมื่อ function ทำงานเสร็จ ข้อมูลเหล่านี้จะถูก "pop" ออกจาก stack ทำให้การทำงานกลับไปยังจุดที่ function นั้นถูกเรียกได้
2. Expression Evaluation Stacks มีบทบาทสำคัญในการประเมินค่าของ Expression คณิตศาสตร์ โดยเฉพาะอย่างยิ่งการแปลงนิพจน์แบบ infix ไปเป็น postfix หรือ prefix รวมถึงการประมวณผลลัพธ์ของ Expression เหล่านั้นด้วยเช่นกัน
3. Syntax Parsing Compilers ใช้ Stack เพื่อช่วยในการแยกวิเคราะห์ไวยากรณ์สำหรับภาษาโปรแกรมต่างๆ ทำให้มั่นใจว่าองค์ประกอบของ code มีการใช้เครื่องหมายวงเล็บและเครื่องหมายอื่นๆ ได้อย่างถูกต้อง
4. Backtracking Algorithms ในกรณีต่างๆ เช่น การหาทางออกจากเขาวงกต เกมไขปริศนา หรือการค้นหาข้อมูลในโครงสร้างแบบ tree ที่จำเป็นต้องย้อนกลับไปยังจุดก่อนหน้าเพื่อหาคำตอบ Stack ช่วยในการบริหารจัดการสถานะต่างๆ หรือเส้นทางที่เคยผ่านมาได้
5. Web Browser Navigation ปุ่มย้อนกลับและ Forward ในเว็บเบราว์เซอร์มักจะทำงานโดยใช้ Stack สองชุดเก็บ URL ของเว็บไซต์ที่เข้าชม ซึ่งช่วยให้ผู้ใช้ถอยหลังหรือเดินหน้ากลับไปยังจุดต่างๆ ในประวัติการท่องเว็บได้
6. Undo Mechanisms ในโปรแกรมหลายประเภทที่มี function "ย้อนกลับ" เช่น โปรแกรมแต่งข้อความ หรือ Software ออกแบบกราฟิก Stack สามารถใช้เก็บประวัติของคำสั่งหรือการเปลี่ยนแปลงต่างๆ เวลาที่ต้องการ "ย้อนกลับ" ระบบก็แค่ดึงเอา (pop) คำสั่งล่าสุดออกจาก Stack มาใช้งาน
7. Depth-First Search (DFS) ในทฤษฎีกราฟ หรือ tree algorithm Stack สามารถใช้ในการจัดการว่า node ใดบ้างที่กำลังถูกเข้าเยี่ยมชม ซึ่งทำให้สามารถค้นลึกลงไปบนแต่ละ branch ของกราฟให้ได้มากที่สุดก่อนจะต้องย้อนกลับมาได้
8. String Reversal การใช้ Stack สามารถกลับลำดับตัวอักษรหรือลำดับใดๆ ได้ง่ายๆ โดยการผลัก (push) ตัวอักษรหรือองค์ประกอบต่างๆ เข้า Stack แล้วดึงออกมา (pop) ซึ่งจะทำให้ได้ลำดับที่ถูกย้อนกลับออกมาได้
9. Syntax Checking Stacks มีประโยชน์ในการตรวจสอบไวยากรณ์ภายใน code ได้ เช่นการจับคู่ว่า tag เปิดและปิดใน HTML หรือ XML สอดคล้องกันหรือไม่

ตัวอย่างการใช้ Stack ผ่าน LeetCode

Problem 20 - Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

โจทย์คือ ตรวจสอบว่าวงเล็บต่างๆ ใน string ที่ input เข้ามา มีการจับคู่และเรียงลำดับอย่างถูกต้องหรือไม่

ในการแก้โจทย์ Valid Parentheses สามารถทำได้โดยใช้ stack โดยเราต้องวนตรวจสอบทีละตัวอักษรใน String ที่เป็นค่า input string และใช้ Stack เก็บประวัติของวงเล็บเปิดต่างๆ ไว้

โดยไอเดียคือ เมื่อใดเจอวงเล็บปิด จะต้องตรวจสอบว่ามันตรงกันกับวงเล็บเปิดล่าสุดที่เก็บอยู่ใน Stack หรือไม่ ถ้าตรงกัน ก็ "pop" วงเล็บเปิดนั้นออกจาก Stack ไป แต่ถ้าไม่ตรงกัน ก็แสดงว่าการจัดเรียงวงเล็บไม่ถูกต้อง

และหากการตรวจสอบสิ้นสุดลง และพบว่า Stack ว่างเปล่า นั่นหมายความว่าลำดับวงเล็บนั้นถูกต้อง แต่ถ้า Stack ยังมีข้อมูลเหลืออยู่ แสดงว่าการจัดเรียงวงเล็บไม่ถูกต้อง (แปลว่าวงเล็บเปิด ปิด กันไม่ครบคู่)

class Solution {
public:
  bool isValid(string s) {
    stack<char> parentheses;

    for (char &c : s) {
      switch (c) {
      case '(':
      case '{':
      case '[':
        parentheses.push(c);
        break;
      case ')':
        if (parentheses.empty() || parentheses.top() != '(')
          return false;
        parentheses.pop();
        break;
      case '}':
        if (parentheses.empty() || parentheses.top() != '{')
          return false;
        parentheses.pop();
        break;
      case ']':
        if (parentheses.empty() || parentheses.top() != '[')
          return false;
        parentheses.pop();
        break;
      default:
        // In case of any characters other than the parentheses
        break;
      }
    }

    return parentheses.empty();
  }
};

Problem 1047 - Remove All Adjacent Duplicates In String

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/description/

โจทย์คือ เรามี string ที่ประกอบด้วยตัวอักษรพิมพ์เล็ก ให้เราลบตัวอักษรที่ซ้ำกันและอยู่ติดกันออกไป

ในการแก้โจทย์ Remove All Adjacent Duplicates In String โดยใช้ Stack ให้เริ่มจากการวนตรวจสอบตัวอักษรแต่ละตัวภายใน String และใช้ Stack เพื่อติดตามว่าตัวอักษรใดบ้างที่ถูกใส่ไว้แล้ว

เมื่อเจอตัวอักษรที่ซ้ำกับตัวอักษรด้านบนสุดของ Stack ให้ "pop" ตัวอักษรบนสุดนั้นออก ซึ่งจะลบตัวอักษรที่ซ้ำกันออกไปโดยอัตโนมัติ แต่ถ้าไม่เจอตัวอักษรที่ซ้ำกัน ก็ให้ "push" ตัวอักษรนั้นเข้าไปใน Stack

สุดท้าย สร้างผลลัพธ์เป็น string ใหม่จากตัวอักษรทั้งหมดที่เหลืออยู่ใน Stack ออกมาได้

class Solution {
public:
  string removeDuplicates(string S) {
    stack<char> stk;

    // Iterate through the string
    for (char &c : S) {
      if (!stk.empty() && stk.top() == c) {
        // If the current character is the same as the top of the stack, pop the
        // stack
        stk.pop();
      } else {
        // Otherwise, push the current character onto the stack
        stk.push(c);
      }
    }

    // Construct the result string from the stack
    string result = "";
    while (!stk.empty()) {
      result = stk.top() + result; 
      stk.pop();
    }

    return result;
  }
};