10 lượt xem

Ngăn xếp (Stack) – Cài đặt cấu trúc Ngăn xếp trong C/C

Stack trong c++ la gi

Ngăn xếp là cấu trúc dữ liệu quan trọng tiếp theo mà chúng ta sẽ tìm hiểu trong bài viết hôm nay. Bằng cách thêm một số ràng buộc vào mảng, chúng ta có cấu trúc dữ liệu ngăn xếp giúp tính toán nhanh hơn và thuận tiện hơn. Vậy ngăn xếp là gì? Khi nào sử dụng ngăn xếp?

1. Lý thuyết ngăn xếp

Trong khoa học máy tính, ngăn xếp (còn được gọi là ngăn xếp, tiếng Anh: stack) là một cấu trúc dữ liệu trừu tượng tuân theo nguyên tắc “cuối cùng vào trước” ( l ast i n f irst o ut (liveso) tức là phần tử cuối cùng được chèn vào ngăn xếp sẽ là phần tử đầu tiên được xóa khỏi ngăn xếp. p>

Như một ví dụ trực quan, bạn có một chồng sách và bạn đặt nó vào một chiếc hộp, như thể hiện trong hình ảnh bên dưới. Giả sử chiếc hộp phù hợp với những cuốn sách. Sau đó, bạn có các hành động sau:

Bạn đang xem: Stack trong c++ la gi

  • Thêm sách vào hộp (đẩy vào ngăn xếp)
  • Xóa sách khỏi hộp và bạn sẽ chỉ nhận được phần trên cùng (cửa sổ ngăn xếp)

Cấu trúc dữ liệu Ngăn xếp(Stack)

Cấu trúc dữ liệu Ngăn xếp(Stack)

Cấu trúc dữ liệu ngăn xếp bị giới hạn theo cách như trên. Như vậy, việc thao tác với ngăn xếp của chúng ta chỉ bao gồm các hành động sau:

  • push : Thêm một phần tử vào đầu ngăn xếp, tăng số phần tử trong ngăn xếp lên 1.
  • pop : xóa phần tử đầu tiên trên đầu ngăn xếp, giảm số phần tử trên đầu ngăn xếp đi 1.
  • top : Nhận giá trị trên cùng của giá trị ngăn xếp của phần tử đầu tiên ở trên cùng của ngăn xếp. ngăn xếp, số phần tử trong ngăn xếp không thay đổi.
  • isempty : Kiểm tra xem ngăn xếp có trống không. Ngăn xếp rỗng là ngăn xếp không có phần tử.
  • đầy đủ : Kiểm tra xem ngăn xếp đã đầy chưa. Hành động này không phải lúc nào cũng có sẵn.
  • kích thước : Nhận số phần tử ngăn xếp có sẵn.

2. Cài đặt ngăn xếp với mảng

Trong hướng dẫn này, tôi sẽ trình bày chi tiết từng hoạt động của cấu trúc dữ liệu ngăn xếp. Chúng tôi sẽ thực hiện một triển khai ngăn xếp các số nguyên bằng cách sử dụng mảng. Trong phần tiếp theo, tôi sẽ cung cấp cho bạn một số cài đặt khác.

Chúng tôi sẽ sử dụng mảng một chiều kiểu int làm ngăn xếp, khả năng thay đổi để lưu trữ kích thước của ngăn xếp và một đỉnh biến để lưu chỉ mục của phần tử trên cùng của ngăn xếp.

2.1. Kiểm tra ngăn xếp đã đầy (đầy)

Hàm này sẽ kiểm tra xem ngăn xếp hiện tại đã đầy chưa. Nếu chỉ số trên cùng của ngăn xếp bằng dung lượng – 1, thì ngăn xếp đã đầy.

2.2. Kiểm tra xem ngăn xếp có trống không (isempty)

Nếu ngăn xếp không có phần tử nào, chúng tôi sẽ gán chỉ mục top = -1 để đánh dấu nó. Vì vậy, việc kiểm tra xem ngăn xếp có trống không rất đơn giản. Chúng ta chỉ cần so sánh xem giá trị của top có phải là -1 hay không.

2.3. Thêm phần tử vào đầu ngăn xếp (đẩy)

Chúng tôi chỉ có thể đẩy lên đầu ngăn xếp khi ngăn xếp chưa đầy. Nếu ngăn xếp đầy, chúng tôi sẽ gửi thông báo thay vì đẩy. Nếu không, chúng tôi tăng dần từng phần một và gán giá trị cho phần tử ở đầu chỉ mục.

2.4. Xóa một phần tử khỏi đầu ngăn xếp (cửa sổ bật lên)

Chúng tôi chỉ có thể bật (xóa một phần tử) khỏi đầu ngăn xếp nếu ngăn xếp không trống. Nếu ngăn xếp trống, chúng tôi phát ra một thông báo và không bật lên. Nếu không, chúng tôi giảm giá trị cao nhất đi một đơn vị.

2.5. Nhận giá trị của phần tử trên cùng của ngăn xếp (trên cùng)

Để nhận giá trị của phần tử ở đầu ngăn xếp, chúng ta có một thao tác rất đơn giản:

2.6. Nhận số lượng (kích thước) của các phần tử ngăn xếp hiện có

Xem thêm: Chu pa pi nha nhố nghĩa là gì? Những lưu ý nào khi sử dụng?

Đầu biến lưu trữ chỉ số tối đa của ngăn xếp. Vì vậy, việc lấy kích thước của ngăn xếp rất đơn giản:

Cuối cùng, chúng ta sẽ có một trình cài đặt ngăn xếp hoàn chỉnh như sau:

Kết quả của việc chạy chương trình trên:

Sơ đồ sau sẽ giải thích hoạt động của ngăn xếp trong chương trình trên chi tiết hơn theo các bước được đánh số.

stack

Giải thích cách hoạt động của stack ở chương trình trên

3. Ứng dụng của stack

Chúng tôi sẽ sử dụng ngăn xếp để kiểm tra xem các dấu ngoặc đơn có hợp lệ hay không.

Bạn có một chuỗi ngoặc bao gồm một dấu ngoặc nhọn ‘)’ và một dấu ngoặc nhọn ‘(‘. Bạn phải kiểm tra xem chuỗi dấu ngoặc vuông có hợp lệ không.

Một chuỗi dấu ngoặc hợp lệ không có dấu ngoặc đơn bổ sung hoặc không có dấu ngoặc đơn, ví dụ: (), (()), ((())) () đều là dấu ngoặc đơn hợp lệ. và ((, ()), (() (là các chuỗi dấu ngoặc không hợp lệ.

Bạn có thể sử dụng ngăn xếp để giải quyết vấn đề này. Hãy xem cách chúng tôi làm điều đó.

ý tưởng: lặp qua từng dấu ngoặc trong chuỗi ngoặc; sử dụng ngăn xếp để đẩy dấu ngoặc mở vào ngăn xếp và bật một phần tử từ ngăn xếp mỗi khi gặp dấu ngoặc đóng. Dấu ngoặc nhọn không có tác dụng khi bạn không thể bật lên hoặc khi ngăn xếp duyệt xong nhưng ngăn xếp không trống.

Kết quả:

4. Một số triển khai ngăn xếp khác

4.1. Cài đặt ngăn xếp động của mảng

4.2. Triển khai ngăn xếp bằng cách sử dụng c ++ hướng đối tượng

4.3. Triển khai ngăn xếp bằng danh sách được liên kết

4.4. Sử dụng ngăn xếp trong thư viện stl

5. tập thể dục

Xem thêm: Nên mua đồng hồ pin hay đồng hồ dùng năng lượng ánh sáng?

Được sử dụng cho các biểu thức hậu tố với các số hạng nguyên dương và ba toán tử +, -, * . Đánh giá biểu thức hậu tố.

Ví dụ: Biểu thức hậu tố: 2 3 4 + * 5 – 2 2 * + có giá trị 13.

Nhập:

– Chứa một dòng đại diện cho một biểu thức hậu tố, mỗi số hạng là một số nguyên dương trong phạm vi từ 1 đến 100. Cách tách một khoảng trắng giữa hai số hạng, hoặc giữa hai toán tử, hoặc giữa một thuật ngữ và một toán tử. Độ dài biểu thức không được vượt quá 100 ký tự. Đảm bảo rằng biểu thức hậu tố là dữ liệu chủ đề hợp lệ. Trong quá trình tính toán, hãy đảm bảo rằng giá trị tuyệt đối của giá trị trung vị không vượt quá 109.

Đầu ra:

– là giá trị của biểu thức hậu tố.

Lưu ý: Sử dụng các hàm get () hoặc getline () để đọc các chuỗi.

Ví dụ

Ngoài ra, bạn có thể thực hành thêm các bài tập xếp chồng trong bài tập viết mã trực tuyến.

Xem thêm: Vì sao các đầu bếp Ngự Thiện phòng không bị &quottịnh thân&quot như thái giám?

Rate this post

Trả lời

Email của bạn sẽ không được hiển thị công khai.