C C++ โครงสร้างข้อมูลแบบ Stack

โครงสร้างข้อมูลแบบ Stack

ข้อมูลที่เก็บใน Stack จะเก็บในลักษณะวางทับกัน เช่นเดียวกับการวางจานเรียงซ้อนกัน ข้อมูลตัวแรกจะเป็นข้อมูลที่อยู่ล่างสุดของ Stack และ ข้อมูลสุดท้ายจะเป็นข้อมูลที่อยู่บนสุด ของ Stack เมื่อมีการนำข้อมูลออกจาก Stack ข้อมูลที่อยู่บนสุด นั่นคือข้อมูลที่นำลงสู่Stack เป็นข้อมูลสุดท้าย จะเป็นข้อมูลที่จะต้องนำออกจาก Stack ก่อน การทำงานลักษณะนี้เรียกว่า LIFO (last-in-first-out)

class MyStack {
private:
    int n =5;
    int top = -1;
    int arr [5];
public:
    void push(int x);
    int pop();
    void display();
};

Push Stack

ฟังก์ชันนี้เป็นการนำข้อมูลเข้าสู่ Stack คือ ถ้า top น้อยกว่า MAX-1 (n คือค่า MAX) ซึ่งก็คือ ถ้า Stack ยังไม่เต็ม ก็ให้ top++ และเก็บข้อมูลที่ส่งมาทางพารามิเตอร์ what ลงไปในตัวแปร stackdata ช่องที่ top ชี้อยู่นั้นเอง จากนั้น return 1 กลับไปยังจุดที่เรียกใช้เป็นการบอกสถานะว่าตอนนี้ได้ push เรียบร้อยแล้วนั่นเอง แต่ถ้าเงื่อนไข if ไม่เป็นจริง มันก็จะลงมาทำที่ return-1 ดังนั้น ฟังก์ชันนี้คืนค่า -1 แสดงว่า stack เต็มแล้วนั่นเอง

using namespace std;

void MyStack::push(int x) {
    if (this->top >= this->n-1) {
        cout << "Stack Overflow" << endl;
        return;
    }
    top ++;
    this->arr[this->top] = x;
    cout << "Inserted " << x << " to "<< this->top << " "<< endl;
    this->display();
}

Pop Stack

การเอาข้อมูลออกจาก Stack ได้นั้น ก็เพียงแค่คืนค่าข้อมูลตัวที่ top นั้นชี้อยู่กลับไป แต่ก่อนที่จะ Pop ได้นั้นจะต้องดูด้วยว่า top นั้นเป็น -1 หรือไม่ ถ้าเป็น -1 ก็แสดงว่าตอนนั้น Stack ว่าง ให้คืนค่า -1 กลับไป แต่ถ้า top >-1 แสดงว่ามัมมีข้อมูลอยู่ภายใน Stack ดังนั้น ให้คืนค่าตัวที่ top ชี้อยู่กลับไป และลดค่า top ลงอีก 1

int MyStack::pop() {
    if (this->top == -1){
        cout << "Stack Empty." << endl;
        return 0;
    }
    int data = this->arr[this->top];
    this->arr[this->top] = NULL;
    this->top --;
    cout << "Removed " << data << " form "<< this->top+1 << " "<< endl;
    this->display();
    return data;
}

Code ตัวเต็ม

#include <iostream>

class MyStack {
private:
    int n =5;
    int top = -1;
    int arr [5];
public:
    void push(int x);
    int pop();
    void display();
};

using namespace std;

void MyStack::push(int x) {
    if (this->top >= this->n-1) {
        cout << "Stack Overflow" << endl;
        return;
    }
    top ++;
    this->arr[this->top] = x;
    cout << "Inserted " << x << " to "<< this->top << " "<< endl;
    this->display();
}

int MyStack::pop() {
    if (this->top == -1){
        cout << "Stack Empty." << endl;
        return 0;
    }
    int data = this->arr[this->top];
    this->arr[this->top] = NULL;
    this->top --;
    cout << "Removed " << data << " form "<< this->top+1 << " "<< endl;
    this->display();
    return data;
}

void MyStack::display() {
    if (this->top == -1) return;
    cout << "Top = "<< this->top << endl;
    for (int i = 0;i<=this->top;i++) {
        cout << "[" << i << "] ->  " << this->arr[i] <<  " | " ;
    }
    cout << endl;

}

int main() {
    MyStack myStack;
    std::cout << "Matee Suttapak \n " ;

    int menu;
    char ans = 'y';
    while (ans == 'y' || ans == 'Y') {
        std::cout << "\nPls select menu [1]:Push [2]:Pop [3]:Show data " ;
        std::cin >> menu ;
        switch (menu) {
            case 1 :
                int data;
                std::cout << "\nInsert data : " ;
                std::cin>>data;
                myStack.push(data);
                break;
            case 2:
                myStack.pop();
                break;
            case 3:
                myStack.display();
                continue;
            default:
                std::cout << "Pls select 1 -> 2";
                break;
        }

    }
}

โดย program ด้านบนจะเป็นการเขียนแบบเป็น Class หรือแบบ OOP ตั่งชื่อว่า MyStack เก็บ attribute 3 อย่าง

1. n // เป็นจำนวนเต็มบ่งบอกของค่าของความจุสแตก
2. top // เป็นตัวบงชี้ไปที่ค่าบนสุดของสแตก
3. arr // เป็นข้อมูลแบบอาเรย์ใว้เก็บค่าของสแตก
4. function push // ฟังก์ชันนำค่าเข้าไปเก็บในสแตก
5. function pop // ฟังก์ชันนำค่าบนสุดออกจากสแตก
6. function display // ฟังก์ชันแสดงค่าของสแตก

โอเครครับ blog ต่อไปจะเป็น การแปลงนิพจน์ Infix ให้เป็น Postfix ฝากติดตามด้วยนะครับ