Xếp chồng vào C++ STL với ví dụ

std::stack là gì?

Ngăn xếp là một cấu trúc dữ liệu hoạt động dựa trên kỹ thuật LIFO (Last In First Out). std::stack chỉ cho phép thêm và xóa các phần tử ở một đầu.

Lớp `std::stack` là một bộ điều hợp container. Các đối tượng container chứa dữ liệu có cùng kiểu dữ liệu. Bạn có thể tạo một ngăn xếp từ nhiều container chuỗi khác nhau. Nếu không cung cấp container nào, container `deque` sẽ được sử dụng theo mặc định. Bộ điều hợp container không hỗ trợ iterator, vì vậy chúng không thể được sử dụng để thao tác dữ liệu.

Cú pháp ngăn xếp

Để tạo một ngăn xếp, chúng ta phải bao gồm tệp tiêu đề trong mã của chúng tôi. Sau đó chúng tôi sử dụng cú pháp này để xác định std::stack:

template <class Type, class Container = deque<Type> > class stack;

• Kiểu – là Loại phần tử có trong std::stack. Nó có thể là bất kỳ giá trị nào C++ loại hoặc thậm chí là loại do người dùng xác định.
• Container – là Loại đối tượng chứa bên dưới.

Loại thành viên

Dưới đây là các loại thành viên ngăn xếp:

• giá trị_kiểu– Tham số mẫu đầu tiên, T. Nó biểu thị các loại phần tử.
• loại container– Tham số mẫu thứ hai, Container. Nó biểu thị loại vùng chứa cơ bản.
• kích thước_loại– Kiểu số nguyên không dấu.

Operacác chức năng trong ngăn xếp

A C++ stack hỗ trợ các hoạt động cơ bản sau:

• đẩy – Thao tác này thêm/đẩy một mục vào ngăn xếp.
• bật – Thao tác này loại bỏ/lấy một mục khỏi ngăn xếp.
• nhìn trộm – Trả về phần tử trên cùng của ngăn xếp mà không xóa nó đi.
• Đã đầy – Kiểm tra xem ngăn xếp đã đầy hay chưa.
• isEmpty – Kiểm tra xem ngăn xếp có rỗng hay không.

Triển khai ngăn xếp

Các bước sau đây minh họa cách phần tử trên cùng của ngăn xếp dịch chuyển khi các phần tử được đẩy vào và sau đó được lấy ra:

Bước 1) Ban đầu, chúng ta có một ngăn xếp rỗng. Phần tử trên cùng của ngăn xếp rỗng được đặt là -1.

Bước 2) Tiếp theo, chúng ta đã đẩy phần tử 5 vào ngăn xếp. Đỉnh của ngăn xếp sẽ trỏ đến phần tử 5.

Bước 3) Tiếp theo, chúng ta đã đẩy phần tử 50 vào ngăn xếp. Đỉnh của ngăn xếp dịch chuyển và trỏ đến phần tử 50.

Bước 4) Sau đó, chúng ta thực hiện thao tác pop, loại bỏ phần tử trên cùng khỏi ngăn xếp. Phần tử 50 được pop khỏi ngăn xếp. Đỉnh của ngăn xếp hiện trỏ đến phần tử 5.

đẩy() và pop()

Hàm `stack::push()` thêm một phần tử mới vào đỉnh của ngăn xếp. Kích thước của ngăn xếp tăng lên 1 sau khi chèn. Hàm này có cú pháp như sau:

stack.push(value)

Giá trị là mục cần chèn vào ngăn xếp.

Hàm `stack::pop()` loại bỏ phần tử trên cùng của ngăn xếp. Đây là phần tử mới nhất trong ngăn xếp. Kích thước của ngăn xếp giảm đi 1 sau khi loại bỏ. Cú pháp của hàm như sau:

stack.pop()

Hàm không có tham số.

Ví dụ 1:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

Đầu ra:

Đây là ảnh chụp màn hình của mã:

Code Giải thích:

1. Bao gồm tệp tiêu đề iostream trong mã của chúng tôi để sử dụng các chức năng của nó.
2. Bao gồm tệp tiêu đề ngăn xếp trong mã của chúng tôi để sử dụng các chức năng của nó.
3. Bao gồm không gian tên std trong mã của chúng tôi để sử dụng các lớp của nó mà không cần gọi nó.
4. Gọi hàm main(). Logic chương trình nên được thêm vào trong chức năng này.
5. Tạo một ngăn xếp st để lưu trữ các giá trị nguyên.
6. Sử dụng hàm push() để chèn giá trị 10 vào ngăn xếp.
7. Sử dụng hàm push() để chèn giá trị 20 vào ngăn xếp.
8. Sử dụng hàm push() để chèn giá trị 30 vào ngăn xếp.
9. Sử dụng hàm push() để chèn giá trị 40 vào ngăn xếp.
10. Sử dụng hàm pop() để xóa phần tử trên cùng khỏi ngăn xếp, tức là 40. Phần tử trên cùng bây giờ trở thành 30.
11. Sử dụng hàm pop() để xóa phần tử trên cùng khỏi ngăn xếp, tức là 30. Phần tử trên cùng bây giờ trở thành 20.
12. Sử dụng vòng lặp while và hàm rỗng() để kiểm tra xem ngăn xếp có trống hay không. Các ! là toán tử NOT.
13. In nội dung hiện tại của ngăn xếp trên bàn điều khiển.
14. Gọi hàm pop() trên ngăn xếp.
15. Kết thúc phần thân của vòng lặp while.
16. Kết thúc phần thân hàm main().

trống(), kích thước(), đỉnh()

Ngăn xếp có sẵn các hàm mà bạn có thể sử dụng để thao tác với ngăn xếp và các giá trị của nó. Bao gồm các:

• trống()– Kiểm tra xem ngăn xếp có rỗng hay không.
• kích thước()– Trả về kích thước của ngăn xếp, tức là số lượng phần tử trong ngăn xếp.
• hàng đầu()– Truy cập phần tử ở đầu ngăn xếp.

Ví dụ 2:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

Đầu ra:

Đây là ảnh chụp màn hình của mã:

Code Giải thích:

1. Bao gồm tệp tiêu đề iostream trong mã của chúng tôi để sử dụng các chức năng của nó.
2. Bao gồm tệp tiêu đề ngăn xếp trong mã của chúng tôi để sử dụng các chức năng của nó.
3. Bao gồm không gian tên std trong chương trình của chúng tôi để sử dụng các lớp của nó mà không cần gọi nó.
4. Tạo hàm createStack mà chúng ta có thể sử dụng để tạo ngăn xếp mystack. Ngăn xếp sẽ chứa một tập hợp các số nguyên.
5. Phần đầu của hàm createStack.
6. Tạo một thể hiện của kiểu dữ liệu mystack và đặt tên là ms.
7. Sử dụng vòng lặp while và hàm rỗng() để kiểm tra xem ngăn xếp có trống không.
8. Sự bắt đầu của phần thân vòng lặp while.
9. Sử dụng hàm top() được lưu trữ ở đầu ngăn xếp. Ký tự \t sẽ tạo một tab mới.
10. Sử dụng hàm pop() để xóa phần tử ở đầu ngăn xếp.
11. Kết thúc phần thân của vòng lặp while.
12. In một dòng trống trên bàn điều khiển.
13. Phần cuối của hàm createStack.
14. Gọi hàm main(). Logic chương trình phải được thêm vào trong phần thân của hàm main().
15. Sự bắt đầu của phần thân hàm main().
16. Tạo một đối tượng ngăn xếp st.
17. Sử dụng hàm push() để chèn phần tử 32 vào ngăn xếp.
18. Sử dụng hàm push() để chèn phần tử 21 vào ngăn xếp.
19. Sử dụng hàm push() để chèn phần tử 39 vào ngăn xếp.
20. Sử dụng hàm push() để chèn phần tử 89 vào ngăn xếp.
21. Sử dụng hàm push() để chèn phần tử 25 vào ngăn xếp.
22. In một số văn bản trên bảng điều khiển.
23. Gọi hàm createStack để thực hiện các thao tác chèn trên vào ngăn xếp.
24. In kích thước của ngăn xếp trên bảng điều khiển cùng với văn bản khác.
25. In phần tử ở đầu ngăn xếp trên bàn điều khiển.
26. In một số văn bản trên bảng điều khiển.
27. Xóa phần tử ở đầu ngăn xếp. Sau đó nó sẽ trả về các phần tử còn lại trong ngăn xếp.
28. Gọi hàm createStack để thực hiện các thao tác trên.
29. Chương trình phải trả về giá trị sau khi hoàn thành thành công.
30. Kết thúc phần thân của hàm main().

emplace() và trao đổi()

Đây là các hàm ngăn xếp sẵn có khác:

• đặt()– Tạo rồi chèn một phần tử mới vào đầu ngăn xếp.
• tráo đổi()– Trao đổi nội dung của ngăn xếp với nội dung của ngăn xếp khác.

Ví dụ 3:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

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

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

Đầu ra:

Đây là ảnh chụp màn hình của mã:

Code Giải thích:

1. Bao gồm tệp tiêu đề iostream trong mã của chúng tôi để sử dụng các chức năng của nó.
2. Bao gồm tệp tiêu đề ngăn xếp trong mã của chúng tôi để sử dụng các chức năng của nó.
3. Bao gồm tệp tiêu đề cstdlib trong mã của chúng tôi để sử dụng các chức năng của nó.
4. Bao gồm không gian tên std trong mã của chúng tôi để sử dụng các lớp của nó mà không cần gọi nó.
5. Gọi hàm main(). Logic chương trình sẽ được thêm vào trong phần thân của hàm này.
6. Khai báo một ngăn xếp có tên st1 để lưu trữ các giá trị nguyên.
7. Khai báo một ngăn xếp có tên st2 để lưu trữ các giá trị nguyên.
8. Sử dụng hàm emplace() để chèn số nguyên 12 vào ngăn xếp có tên st1.
9. Sử dụng hàm emplace() để chèn số nguyên 19 vào ngăn xếp có tên st1.
10. Sử dụng hàm emplace() để chèn số nguyên 20 vào ngăn xếp có tên st2.
11. Sử dụng hàm emplace() để chèn số nguyên 23 vào ngăn xếp có tên st2.
12. Sử dụng hàm swap() để hoán đổi nội dung của hai ngăn xếp st1 và st2. Nội dung của ngăn xếp st1 sẽ được chuyển sang ngăn xếp st2. Nội dung của ngăn xếp st2 sẽ được chuyển vào ngăn xếp st1.
13. In một số văn bản trên bảng điều khiển.
14. Sử dụng câu lệnh while và hàm rỗng() để kiểm tra xem ngăn xếp st1 có trống hay không.
15. In nội dung của ngăn xếp st1 trên bàn điều khiển. ” ” thêm khoảng trống giữa các phần tử ngăn xếp khi in chúng trên bảng điều khiển.
16. Thực thi hàm pop() trên ngăn xếp st1 để loại bỏ phần tử trên cùng.
17. Kết thúc phần thân của câu lệnh while.
18. In một số văn bản trên bảng điều khiển. Cuối cùng là một C++ từ khóa cho dòng cuối cùng. Nó di chuyển con trỏ chuột đến dòng tiếp theo để bắt đầu in từ đó.
19. Sử dụng câu lệnh while và hàm rỗng() để kiểm tra xem ngăn xếp st2 có trống hay không.
20. In nội dung của ngăn xếp st2 trên bàn điều khiển. ” ” thêm khoảng trống giữa các phần tử ngăn xếp khi in chúng trên bảng điều khiển.
21. Thực thi hàm pop() trên ngăn xếp st2 để loại bỏ phần tử trên cùng.
22. Kết thúc phần thân của câu lệnh while.
23. Phần cuối của hàm main().

Ngăn xếp trong STL

STL (Thư viện mẫu tiêu chuẩn) đi kèm với các lớp mẫu cung cấp các tính năng chung C++ các cấu trúc dữ liệu. Do đó, ngăn xếp cũng có thể được triển khai trong STL. Chúng tôi chỉ cần đưa thư viện này vào mã của mình và sử dụng nó để xác định ngăn xếp.

stack<T> st; 

Cú pháp trên khai báo một ngăn xếp st cho các phần tử có kiểu dữ liệu T.

Ví dụ 4:

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

Đầu ra:

Đây là ảnh chụp màn hình của mã:

Code Giải thích:

1. Bao gồm tệp tiêu đề iostream trong mã của chúng tôi để sử dụng các chức năng của nó.
2. Bao gồm tệp tiêu đề ngăn xếp trong mã của chúng tôi để sử dụng các chức năng của nó.
3. Bao gồm tệp tiêu đề cstdlib trong mã của chúng tôi để sử dụng các chức năng của nó.
4. Bao gồm không gian tên std trong mã của chúng tôi để sử dụng các lớp của nó mà không cần gọi nó.
5. Gọi hàm main(). Logic chương trình phải được thêm vào trong phần thân của hàm này.
6. Khai báo một ngăn xếp st để lưu trữ dữ liệu số nguyên.
7. Thêm phần tử 12 vào ngăn xếp.
8. Thêm phần tử 19 vào ngăn xếp.
9. Thêm phần tử 20 vào ngăn xếp.
10. In phần tử ở đầu ngăn xếp trên bàn điều khiển.
11. In kích thước của ngăn xếp trên bàn điều khiển.
12. Kết thúc phần thân của hàm main().

Câu Hỏi Thường Gặp