Stack trong C ++ STL với ví dụ

Mục lục:

Anonim

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ử từ một đầu.

Lớp std :: stack là một bộ điều hợp 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ừ các 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, 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ợ trình vòng lặp, vì vậy nó không thể được sử dụng để thao tác dữ liệu.

Trong hướng dẫn C ++ này, bạn sẽ học

  • Std :: stack là gì?
  • Cú pháp ngăn xếp
  • Các loại thành viên
  • Hoạt động trong ngăn xếp
  • Thực hiện ngăn xếp
  • push () và pop ()
  • rỗng (), size (), top ()
  • emplace () và swap ()
  • Ngăn xếp trong STL

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 ta. Sau đó, chúng tôi sử dụng cú pháp này để xác định std :: stack:

template  > class stack;
  • Kiểu - là Kiểu của phần tử có trong ngăn xếp std ::. Nó có thể là bất kỳ kiểu C ++ hợp lệ nào hoặc thậm chí là kiểu do người dùng xác định.
  • Container - là Loại đối tượng container bên dưới.

Các 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, Vùng chứa. Nó biểu thị loại vùng chứa bên dưới.
  • size_type- Kiểu tích phân không dấu.

Hoạt động trong ngăn xếp

Ngăn xếp C ++ hỗ trợ các hoạt động cơ bản sau:

  • push - Nó thêm / đẩy một mục vào ngăn xếp.
  • pop - Nó loại bỏ / bật một mục khỏi ngăn xếp.
  • peek - Trả về mục trên cùng của ngăn xếp mà không cần xóa nó.
  • isFull - Kiểm tra xem một ngăn xếp đã đầy chưa.
  • isEmpty - Kiểm tra xem một ngăn xếp có trống không.

Thực hiện ngăn xếp

Bước 1) Ban đầu chúng ta có một ngăn xếp trống. Phần trên cùng 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 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. Phần trên cùng 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, xóa phần tử trên cùng khỏi ngăn xếp. Phần tử 50 được xuất hiện từ ngăn xếp. Đỉnh của ngăn xếp bây giờ trỏ đến phần tử 5.

push () 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 được tăng lên 1 sau khi chèn. Hàm có cú pháp sau:

stack.push(value)

Giá trị là mục để 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 được 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 #include using namespace std;int main() {stack 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ã:

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 hàm này.
  5. Tạo một ngăn xếp st để lưu trữ các giá trị số 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, nghĩa 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, nghĩa 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 void () để kiểm tra xem ngăn xếp KHÔNG 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ảng điều khiển.
  14. Gọi hàm pop () trên ngăn xếp.
  15. Cuối phần thân của vòng lặp while.
  16. Kết thúc phần thân của hàm main ().

rỗng (), size (), top ()

Ngăn xếp có các chức năng sẵn có mà bạn có thể sử dụng để chơi xung quanh ngăn xếp và các giá trị của nó. Bao gồm các:

  • rỗng () - kiểm tra xem một 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.

Ví dụ 2:

#include #include using namespace std;void createStack(stack  mystack){stack  ms = mystack;while (!ms.empty()){cout << '\t' << ms.top();ms.pop();}cout << '\n';}int main(){stack  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ã:

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 mystack ngăn xếp. Ngăn xếp sẽ chứa một tập hợp các số nguyên.
  5. Phần đầu của phần thân của hàm createStack.
  6. Tạo một phiên bản của kiểu dữ liệu mystack và đặt tên cho nó là ms.
  7. Sử dụng vòng lặp while và hàm void () để kiểm tra xem ngăn xếp có trống không.
  8. Phần bắt đầu của phần thân của 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ử ở trên cùng của ngăn xếp.
  11. Cuối phần thân của vòng lặp while.
  12. In một dòng trống trên bảng đ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 nên được thêm vào trong phần thân của hàm main ().
  15. Phần bắt đầu của phần thân của 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ảng đ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ị khi hoàn thành thành công.
  30. Cuối phần thân của hàm main ().

emplace () và swap ()

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

  • emplace () - các cấu trúc 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 ngăn xếp khác.

Ví dụ 3:

#include #include #include using namespace std;int main() {stack st1;stack 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ã:

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 là st1 để lưu trữ các giá trị số nguyên.
  7. Khai báo một ngăn xếp có tên là st2 để lưu trữ các giá trị số nguyên.
  8. Sử dụng hàm emplace () để chèn số nguyên 12 vào ngăn xếp có tên là st1.
  9. Sử dụng hàm emplace () để chèn số nguyên 19 vào ngăn xếp có tên là 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 là 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 đến ngăn xếp st2. Nội dung của ngăn xếp st2 nên được chuyển đến 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 void () để kiểm tra xem ngăn xếp st1 có trống không.
  15. In nội dung của ngăn xếp st1 trên bảng điều khiển. Dấu "" thêm khoảng cách 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. Cuối phần nội dung của câu lệnh while.
  18. In một số văn bản trên bảng điều khiển. Endl là một từ khóa C ++ cho dòng kết thúc. 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 void () để kiểm tra xem ngăn xếp st2 có trống không.
  20. In nội dung của ngăn xếp st2 trên bảng điều khiển. Dấu "" thêm khoảng cách 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. Cuối phần nội dung của câu lệnh while.
  23. Cuối phần thân của hàm main ().

Ngăn xếp trong STL

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

stack st;

Cú pháp trên khai báo một ngăn xếp với các phần tử của kiểu dữ liệu T.

Ví dụ 3:

#include #include #include using namespace std;int main() {stack 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ã:

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 nên được thêm vào trong phần thân của hàm này.
  6. Khai báo một stack 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ảng điều khiển.
  11. In kích thước của ngăn xếp trên bảng điều khiển.
  12. Cuối phần thân của hàm main ().

Tóm lược:

  • 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 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ừ các 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 mục 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 rỗng () dùng để kiểm tra xem một ngăn xếp có trống hay không.