Chương 5: Ngăn xếp (Stack)

5.1. Định nghĩa

Stack (ngăn xếp) là một cấu trúc dữ liệu trừu tượng, hoạt động theo nguyên lý "vào sau ra trước" (LIFO - Last In First Out, nghĩa là dữ liệu được nạp vào ngăn xếp trước sẽ được xử lý sau cùng và dữ liệu được nạp vào sau cùng được xử lý đầu tiên).

Có thể hình dung nó như cơ cấu của một hộp chứa đạn súng trường hoặc súng tiểu liên. Lắp đạn vào hay lấy đạn ra cũng chỉ ở 1 đầu hộp. Viên đạn mới nạp vào sẽ nằm ở đỉnh (top), còn viên nạp vào đầu tiên sẽ nằm ở đáy (bottom), điều này cũng có nghĩa là trong stack, các đối tượng có thể được thêm vào bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi ngăn xếp.

5.2. Các thao tác cơ bản trên stack

Trên stack sẽ có 2 thao tác cơ bản chính là push và pop. Thao tác push sẽ bổ sung 1 phần tử vào đỉnh của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. Trong khi đó, thao tác pop lấy ra và trả về phần tử đang đứng ở đỉnh của ngăn xếp.

Hình 5.1 mô tả cách hoạt động của stack với 2 thao tác push và pop trên stack các phần tử là số nguyên. Ngoài những thao tác cơ bản trên thì còn có 1 số thao tác khác:

• Thao tác top(): trả về vị trí phần tử nạp sau cùng vào ngăn xếp
• Thao tác size(): trả về số lượng phần tử được lưu trong ngăn xếp
• Thao tác isEmpty(): kiểm tra xem ngăn xếp có phải rỗng hay không

5.3. Một số ứng dụng của stack

Dựa theo cách thức tổ chức, cơ chế hoạt động của ngăn xếp, ta có một số ứng dụng sau:

• Đổi cơ số trong hệ nhị phân
• Biểu thức số học và ký pháp Ba Lan
• Xây dựng ứng dụng theo dõi lịch sử trình duyệt web
• Xây dựng chức năng undo/redo trong các phần mềm
• Kiểm tra tính hợp lệ của các dấu ngoặc trong biểu thức
• Sử dụng khử đệ quy khi lập trình
  …

5.4. Các thao tác trên ngăn xếp (stack)

Trong phần này, chúng ta sẽ giới thiệu 2 cách cài đặt chính trên ngăn xếp (stack) là dùng mảng và dùng danh sách liên kết, đồng thời cũng giới thiệu cách xây dựng, cách sử dụng 2 thao tác push và pop trên thư viện STL.

5.4.1. Cài đặt ngăn xếp (stack) bằng cách sử dụng mảng:

Đây là cách đơn giản nhất để cài đặt trên ngăn xếp. Ta nạp các phần tử theo thứ tự từ trái sang phải. Có biến lưu giữ chỉ số các phần tử ở đầu ngăn xếp. Thao tác cài đặt ngăn xếp dùng mảng được thực hiện qua các bước sau:

Bước 1: Khai báo cấu trúc dữ liệu của ngăn xếp Ngăn xếp sẽ bao gồm 1 mảng a[ ] chứa các phần tử trong ngăn xếp và 1 biến top để lưu giữ chỉ số của phần tử đầu ngăn xếp

Định nghĩa:

struct Stack {
    int top;
    int a[MAX];
};

Bước 2: Viết các hàm thực hiện các thao tác trên ngăn xếp, bao gồm các thao tác chính:

• Thao tác khởi tạo ngăn xếp
• Thao tác kiểm tra ngăn xếp có rỗng hay không
• Thao tác kiểm tra ngăn xếp có đầy hay không
• Thao tác thêm phần tử vào ngăn xếp
• Thao tác xóa một phần tử ra khỏi ngăn xếp
• Thao tác lấy giá trị trên đỉnh của ngăn xếp

Hàm khởi tạo ngăn xếp:

void createStack(Stack& s) {
    s.top = -1;
}

Hàm kiểm tra ngăn xếp có rỗng hay không

bool isEmpty(Stack s) {
     if (s.top < 0) {           //(s.top == -1)
        return true;
	}
     else {
        return false;
	}
}

Hàm kiểm tra ngăn xếp có đầy hay không

bool isFull(Stack s) {
     if (s.top >= MAX) {
        return true;
	}
     else {
        return false;
	}
}

Hàm thêm phần tử vào ngăn xếp

bool push(Stack& s, int x) {
    if (isFull(s) == 0) {
        s.top++;
        s.a[s.top] = x;
        cout << x << " pushed into stack" << endl;
        return true;
    }
    else {
        cout << "Stack Overflow";
        return false;
    }
}

Hàm xóa 1 phần tử ra khỏi ngăn xếp

int pop(Stack& s) {
    if (isEmpty(s) == 0) {
        int x = s.a[s.top];
        s.top--;
        return x;
    }
    else {
        cout << "Stack Underflow";
        return 0;
    }
}

Hàm lấy giá trị trên đỉnh của ngăn xếp

int peek(Stack& s) {
    if (isEmpty(s) == 0) {
        int x = s.a[s.top];
        return x;
    }
    else {
        cout << "Stack is Empty";
        return 0;
    }
}

Thực thi chương trình:

#include<iostream>
using namespace std;

#define MAX 1000

struct Stack {
    int top;
    int a[MAX];
};

void createStack(Stack& s) {
    s.top = -1;
}

bool isEmpty(Stack s) {
    if (s.top < 0) {           //(s.top == -1)
        return true;
    }
    else {
        return false;
    }
}

bool isFull(Stack s) {
    if (s.top >= MAX) {
        return true;
    }
    else {
        return false;
    }
}

bool push(Stack& s, int x) {
    if (isFull(s) == 0) {
        s.top++;
        s.a[s.top] = x;
        cout << x << " pushed into stack" << endl;
        return true;
    }
    else {
        cout << "Stack Overflow";
        return false;
    }
}

int pop(Stack& s) {
    if (isEmpty(s) == 0) {
        int x = s.a[s.top];
        s.top--;
        return x;
    }
    else {
        cout << "Stack Underflow";
        return 0;
    }
}

int peek(Stack& s) {
    if (isEmpty(s) == 0) {
        int x = s.a[s.top];
        return x;
    }
    else {
        cout << "Stack is Empty";
        return 0;
    }
}

int main()
{
    Stack s;
    createStack(s);
    push(s, 5);
    push(s, 10);
    push(s, 15);
    cout << pop(s) << " popped from stack" << endl;

    cout << "Elements present in stack: ";
    while (!isEmpty(s))
    {
        cout << peek(s) << " ";
        pop(s);
    }
    return 0;
}

Output:

5 pushed into stack
10 pushed into stack
15 pushed into stack
15 popped from stack
Elements present in stack: 10 5

Ưu điểm của việc cài đặt trên:

• Dễ dàng cài đặt
• Không có liên quan đến con trỏ

Nhược điểm:

• Do đây là mảng tĩnh nên bị giới hạn số phần tử, vì thế cần phải xác định số lượng phần tử trước.
  Từ đó, chúng ta có 1 cách cải tiến hơn cho việc cài đặt này

5.4.2. Cài đặt ngăn xếp (stack) sử dụng danh sách liên kết (Linked List)

Thao tác cài đặt ngăn xếp dùng danh sách liên kết được thực hiện qua các bước sau:

Bước 1: Khai báo cấu trúc dữ liệu của ngăn xếp

struct stackNode {
    int data;
    stackNode* next;
};

Cấp phát bộ nhớ một node trên ngăn xếp

stackNode* newNode(int data) {
   stackNode* p = new stackNode();
   p->data = data;
   p->next = NULL;
   return p;
}

Bước 2: Viết các hàm thực hiện các thao tác trên ngăn xếp, bao gồm các thao tác chính:

• Thao tác kiểm tra ngăn xếp có rỗng hay không
• Thao tác thêm phần tử vào ngăn xếp
• Thao tác xóa một phần tử ra khỏi ngăn xếp
• Thao tác lấy giá trị trên đỉnh của ngăn xếp

Hàm kiểm tra ngăn xếp có rỗng hay không

int isEmpty(stackNode* root) {
   return !root;
}

Hàm thêm phần tử vào ngăn xếp

void push(stackNode** root, int data) {
   stackNode* p = newNode(data);
   p->next = *root;
   *root = p;
   cout << data << " pushed to stack\n";
}

Hàm xóa một phần tử ra khỏi ngăn xếp

int pop(stackNode** root) {
   if (isEmpty(*root)) {
       return INT_MIN;
   }
   stackNode* temp = *root;
   *root = (*root)->next;
   int popped = temp->data;
   free(temp);
   return popped;
}

Hàm lấy giá trị trên đỉnh của ngăn xếp

int peek(stackNode* root) {
   if (isEmpty(root)) {
       return INT_MIN;
   }
   return root->data;
}

Thực thi chương trình:

#include<iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;

struct stackNode {
   int data;
   stackNode* next;
};

stackNode* newNode(int data) {
   stackNode* p = new stackNode();
   p->data = data;
   p->next = NULL;
   return p;
}

int isEmpty(stackNode* root) {
   return !root;
}

void push(stackNode** root, int data) {
   stackNode* p = newNode(data);
   p->next = *root;
   *root = p;
   cout << data << " pushed to stack\n";
}

int pop(stackNode** root) {
   if (isEmpty(*root)) {
       return INT_MIN;
   }
   stackNode* temp = *root;
   *root = (*root)->next;
   int popped = temp->data;
   free(temp);
   return popped;
}

int peek(stackNode* root) {
   if (isEmpty(root)) {
       return INT_MIN;
   }
   return root->data;
}

int main() {
   stackNode* root = NULL;

   push(&root, 10);
   push(&root, 20);
   push(&root, 30);

   cout << pop(&root) << " popped from stack" << endl;
   cout << "Top element is " << peek(root) << endl;
   cout << "Elements present in stack : ";

   while (!isEmpty(root)) {
       cout << peek(root) << " ";
       pop(&root);
   }

   return 0;
}

5.4.3. Cách sử dụng các thao tác trên ngăn xếp sử dụng thư viện STL trong C++

• Tên thư viện: stack

Khai báo thư viện:

#include <stack>

Khai báo 1 ngăn xếp (stack) có tên là s, chứa các phần tử là số nguyên:

stack<int> s;

• Cách khai báo các thao tác trên thư viện stack:
  • Thao tác kiểm tra ngăn xếp có rỗng hay không: s.empty();
  • Thao tác thêm n phần tử vào ngăn xếp: s.push(n);
  • Thao tác xóa phần tử ra khỏi ngăn xếp: s.pop();
  • Thao tác lấy phần tử trên đỉnh của ngăn xếp: s.top();
  • Thao tác lấy số phần tử trên ngăn xếp: s.size();

Thực thi chương trình mẫu:

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

int main() {
   stack<int> stack;
   stack.push(1);
   stack.push(2);
   stack.push(4);
   stack.push(5);
   int num = 0;
   stack.push(num);
   stack.pop();
   stack.pop();
   stack.pop();

   while (!stack.empty()) {
       cout << stack.top() << " ";
       stack.pop();
   }
}

Output:

2 1