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

Bởi: Benjamin walker Benjamin walker
Hours cập nhật

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à bộ chuyển đổi vùng chứa. Các đối tượng vùng chứa chứa dữ liệu có kiểu dữ liệu tương tự. Bạn có thể tạo một ngăn xếp từ nhiều vùng chứa trình tự khác nhau. Nếu không có vùng chứa nào được cung cấp thì vùng chứa deque sẽ được sử dụng theo mặc định. Bộ điều hợp vùng chứa không hỗ trợ các trình vòng lặp nên không thể sử dụng nó để 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:

  • value_type- Tham số mẫu đầu tiên, T. Nó biểu thị các loại phần tử.
  • container_type- Tham số mẫu thứ hai, Container. Nó biểu thị loại vùng chứa cơ bản.
  • size_type- Kiểu tích phâ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 - Nó thêm/đẩy một mục vào ngăn xếp.
  • pop - Nó xóa/bật một mục khỏi ngăn xếp.
  • nhìn trộm - Trả về mục trên cùng của ngăn xếp mà không xóa nó.
  • isFull – Kiểm tra xem ngăn xếp có đầy không.
  • isEmpty – Kiểm tra xem ngăn xếp có trống không.

Triển khai ngăn xếp

Triển khai ngăn xếp

Bước 1) Ban đầu chúng tôi có một ngăn xếp trống. Đỉnh của ngăn xếp trống được đặt thành -1.

Bước 2) Tiếp theo, chúng ta đã đẩy phần tử 5 vào ngăn xếp. Đỉnh ngăn xếp sẽ trỏ tới phần tử thứ 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 tôi đã thực hiện thao tác bật lên, loại bỏ phần tử trên cùng khỏi ngăn xếp. Phần tử 50 được lấy ra khỏi ngăn xếp. Đỉnh ngăn xếp bây giờ trỏ đến phần tử 5.

đẩy() và pop()

Các hàm stack::push() thêm mục mới vào đầu ngăn xếp. Kích thước ngăn xếp tăng thêm 1 sau khi chèn. Hàm này có cú pháp 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à mục mới nhất của ngăn xếp. Kích thước ngăn xếp giảm đi 1 sau khi loại bỏ. Đây là cú pháp hàm:

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() và pop()

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

đẩy() và pop()

Giải thích mã:

  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ó trống hay không.
  • size()- trả về kích thước của ngăn xếp, tức là số phần tử trong ngăn xếp.
  • top()- truy cập phần tử ngăn xếp ở trên cùng.

NHỮNG BÀI VIẾT LIÊN QUAN

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:

trống(),kích thước(),top()

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

trống(),kích thước(),top()

Giải thích mã:

  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:

  • emplace()- sau đó chèn phần tử mới vào đầu ngăn xếp.
  • swap()- trao đổi nội dung 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:

đặt chỗ()& trao đổi()

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

đặt chỗ()& trao đổi()

Giải thích mã:

  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:

Ngăn xếp trong STL

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

Ngăn xếp trong STL

Giải thích mã:

  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().

Tổng kết

  • 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 (Vào trước ra trước).
  • std::stack chỉ cho phép thêm và xóa các mục từ một đầu.
  • Lớp std::stack là một bộ điều hợp vùng chứa, chứa các mục có kiểu dữ liệu tương tự.
  • Một ngăn xếp có thể được tạo từ nhiều vùng chứa trình tự khác nhau.
  • Nếu bạn không cung cấp vùng chứa, vùng chứa deque sẽ được sử dụng theo mặc định.
  • Hàm push() dùng để chèn các phần tử vào ngăn xếp.
  • Hàm pop() dùng để xóa mục trên cùng khỏi bước.
  • Hàm Empty() dùng để kiểm tra xem ngăn xếp có trống hay không.

Bạn có thể thích: