Ngăn xếp – Stack

2
6521
This entry is part 3 of 10 in the series Cấu trúc dữ liệu

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

1. Lý thuyết về ngăn xếp(stack)

Trong khoa học máy tính, một ngăn xếp (còn gọi là bộ xếp chồng, tiếng Anh: Stack) là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý “vào sau ra trước” (Last In First Out (LIFO). 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 lấy ra khỏi ngăn xếp.

Một ví dụ trực quan, bạn có một chồng sách và bạn để nó trong một cái hộp như hình phía dưới. Giả sử hộp này vừa khít các cuốn sách. Khi đó, bạn có các thao tác:

  • Thêm một cuốn sách vào hộp(push của stack)
  • Lấy một cuốn sách khỏi hộp, bạn chỉ lấy được thằng trên cùng(pop của stack)
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 đỉnh của ngăn xếp, số phần tử của ngăn xếp tăng lên 1.
  • Pop: Xóa bỏ phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp giảm đi 1.
  • Top: Lấy giá trị của phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp không thay đổi.
  • IsEmpty: Kiểm tra ngăn xếp trống hay không. Ngăn xếp trống là ngăn xếp không có phần tử nào.
  • IsFull: Kiểm tra ngăn xếp đã đầy hay chưa. Thao tác này không phải lúc nào cũng có.
  • Size: Lấy số lượng phần tử stack đang có.

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

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

Chúng ta sẽ sử dụng mảng 1 chiều kiểu int làm Stack stack, một biến capacity để lưu kích thước(sức chứa) của stack và một biến top để lưu chỉ số của phần tử ở top của Stack stack.

2.1. Kiểm tra stack đầy(IsFull)

Hàm này sẽ kiểm tra xem stack hiện tại đã đầy hay chưa. Nếu chỉ số top của stack đang bằng với capacity - 1, tức stack đã đầy.

2.2. Kiểm tra stack rỗng(IsEmpty)

Nếu như stack đang không có phần tử nào, ta sẽ gán chỉ số top = -1 để đánh dấu. Như vậy, để kiểm tra stack có đang rỗng hay không rất đơn giản. Ta chỉ cần so sánh giá trị top có phải -1 hay không mà thôi.

2.3. Thêm phần tử vào đỉnh stack(Push)

Chúng ta sẽ chỉ có thể push(thêm phần tử) vào đỉnh stack khi stack chưa đầy. Nếu stack đầy, chúng ta sẽ đưa ra thông báo và không thực hiện push. Ngược lại, ta sẽ tăng top lên một đơn vị và gán giá trị cho phần tử tại chỉ số top.

2.4. Xóa phần tử khỏi đỉnh stack(Pop)

Chúng ta sẽ chỉ có thể pop(xóa phần tử) khỏi đỉnh stack khi stack không trống. Nếu stack trống, chúng ta sẽ đưa ra thông báo và không thực hiện pop. Ngược lại, ta sẽ giảm giá trị top đi một đơn vị.

2.5. Lấy giá trị phần tử ở đỉnh stack(Top)

Để lấy giá trị phần tử ở đỉnh stack, ta có thao tác rất đơn giản:

2.6. Lấy số lượng phần tử stack đang có(Size)

Biến top lưu chỉ số lớn nhất của stack. Như vậy, việc lấy size của stack cực kỳ đơn giản:

Và cuối cùng, chúng ta sẽ có 1 chương trình cài đặt stack hoàn thiện như sau:

Kết quả chạy chương trình trên:

Hình ảnh dưới đây sẽ giải thích chi tiết hơn về quá trình hoạt động của stack ở chương trình trên theo từng bước đã được đánh số thứ tự.

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 ta sẽ sử dụng stack vào bài toán kiểm tra dãy ngoặc có hợp lệ hay không.

Bạn có một dãy các dấu ngoặc bao gồm ngoặc đóng ‘)’ và ngoặc mở ‘(‘. Bạn phải kiểm tra xem dãy ngoặc đó có hợp lệ hay không.

Một dãy ngoặc hợp lệ thì sẽ không thừa dấu ngoặc hoặc không có dấu ngoặc lẻ loi, chẳng hạn như: (), (()), ((()))() là các dãy ngoặc hợp lệ. Còn ((, ()), (()( là các dãy ngoặc không hợp lệ.

Bạn có thể giải quyết bài toán này với stack. Hãy xem chúng ta làm như thế nào nhé.

Ý tưởng: Duyệt qua từng dấu ngoặc trong dãy ngoặc; Sử dụng một stack để push các dấu ngoặc mở vào stack, mỗi khi gặp dấu ngoặc đóng, thực hiện pop một phần tử khỏi stack. Dãy ngoặc sẽ không hợp lệ khi bạn không thể pop hoặc khi kết thúc duyệt mà stack vẫn chưa rỗng.

Kết quả:

4. Một số cách cài đặt ngăn xếp khác

4.1. Cài đặt stack động bằng mảng

4.2. Cài đặt stack sử dụng hướng đối tượng C++

4.3. Cài đặt stack sử dụng danh sách liên kết

4.4. Sử dụng stack trong thư viện STL

5. Bài tập thực hành

Cho một biểu thức hậu tố với số hạng là các số nguyên dương và ba toán tử +, -, *. Hãy tính giá trị của 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ị là 13.

Dữ liệu nhập:

– Gồm một dòng thể hiện 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. Giữa hai số hạng, hoặc giữa hai toán tử, hoặc giữa số hạng và toán tử, cách nhau một khoảng trắng. Chiều dài biểu thức không quá 100 ký tự. Dữ liệu đề bài cho đảm bảo biểu thức hậu tố là hợp lệ. Trong quá trình tính toán đảm bảo trị tuyệt đối các giá trị trung gian không vượt quá 109.

Dữ liệu xuất:

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

Lưu ý: dùng hàm gets() hay getline() để đọc chuỗi.

Ví dụ

  • input:  2 3 4 + * 5 - 2 2 * +
  • output:  13

Series Navigation<< Mảng đa chiều – Multi-dimensional ArrayHàng đợi – Queue >>
avatar
1 Comment threads
1 Thread replies
2 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Nguyễn Văn Hiếuhieu Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
hieu
Guest
hieu

Tại sao khi cài đặt bằng danh sách liên kết ,hàm pos() phải khai báo thêm con tro temp làm gì thế ạ,nếu dùng mỗi TOS->next có sao không ạ?