Ngăn xếp

Trong chương này, bạn sẽ tìm hiểu về bộ điều chỉnh vùng chứa (container adaptor). Bạn sẽ học về ngăn xếp (stack), hàng đợi (queue) và hàng đợi ưu tiên (priority-queue).

Ngăn xếp trong C++ là một cấu trúc dữ liệu dựa trên nguyên tắc LIFO (vào sau, ra trước) . Điều này có nghĩa là phần tử được thêm vào ngăn xếp sau cùng sẽ bị lấy ra đầu tiên, còn phần tử đầu tiên được thêm vào ngăn xếp sẽ được truy cập sau cùng. (Nguyên tắc này rất giống với việc xếp chồng đĩa hoặc bánh kếp. Khi xếp chồng đĩa, bạn không thể lấy chiếc đĩa ở dưới cùng, được thêm vào đầu tiên, mà cần lấy chiếc đĩa trên cùng, được thêm vào sau cùng.)

stack<dataType> stackName;

Để tạo một ngăn xếp trong C++, trước tiên chúng ta cần thêm tệp tiêu đề stack ở đầu tệp C++ bằng #include <stack>. 
Sau đó, chúng ta có thể khai báo một biến ngăn xếp như bên dưới.

stack<int> number_stack = {1, 2, 3};

Vậy làm thế nào để thêm phần tử vào ngăn xếp? Chúng ta dùng phương thức push().

stack<int> number_stack;
number_stack.push(1);
number_stack.push(2);
...

Như vậy, chúng ta có thể thêm phần tử mới vào ngăn xếp.

Chúng ta cũng cần hiển thị phần tử ra màn hình. Ta làm vậy bằng phương thức top(), phương thức này trả về giá trị cuối cùng ở trên cùng của ngăn xếp.

cout << number_stack.top();

Output:
2

Nhưng nếu tiếp tục in top() ra màn hình, chúng ta sẽ luôn nhận được phần tử cuối cùng, trong trường hợp này là 2. Vì vậy, chúng ta cần một phương thức để xóa phần tử trên cùng. Ta dùng phương thức pop(), phương thức này xóa phần tử cuối cùng ở trên cùng của ngăn xếp.

cout << number_stack.top() << endl;
number_stack.pop();
cout << number_stack.top();

Output: 
2
1

Tóm lại, cấu trúc dữ liệu ngăn xếp rất hữu ích trong C++, lập trình nói chung và lập trình thi đấu. Đặc điểm then chốt của cấu trúc này là áp dụng nguyên tắc vào sau, ra trước.

Các phương thức của ngăn xếp