Stack là gì

1. Ngắn xếp (stack) là gì?

Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính, hoạt động theo cơ chế LIFO (Last In First Out), tạm dịch là “vào sau ra trước”. Có nghĩa là phần tử nào được thêm vào sau trong stack thì sẽ được lấy ra trước.

Bạn đang xem: Stack là gì

Có thể hình dung ngăn xếp như hình ảnh một chồng đĩa. Các đĩa được chồng lên nhau, đĩa nào được đặt vào chồng sau cùng sẽ nằm trên tất cả các đĩa khác và sẽ được lấy ra đầu tiên.Có thể xem ngăn xếp (stack) là một kiểu danh sách có 2 phép toán đặc trưng là:Bổ sung một phần tử vào cuối danh sáchLoại bỏ một phần tử cũng ở cuối danh sáchVị trí cuối danh sách được gọi là đỉnh (top) của stack.Một stack thông thường có các thao tác như:empty(): kiểm tra stack có rỗng không.size(): cho biết số phần tử trong stack, còn gọi là kích thước của stack.top(): lấy phần tử được thêm vào cuối cùng trong stack.push(): thêm một phần tử vào stack.

Xem thêm: Tổng Hợp Các Tập Phim Naruto Thuần Phục Cửu Vĩ Mới Nhất, Naruto Shippuuden Tập 327

pop(): lấy một phần tử ra khỏi stack.Trong lập trình, có 2 cách thường dùng để xây dựng stack là sử dụng mảng (array) và danh sách liên kết (linked list).

2. Xây dựng ngăn xếp bằng mảng

Khi xây dựng stack bằng mảng thì chúng ta lưu ý một số vấn đề sau:Thêm một phần tử vào stack có nghĩa là thêm một phần tử vào cuối mảng.Loại bỏ một phần tử khỏi stack có nghĩa là loại bỏ một phần tử ở cuối mảng.Stack bị tràn khi bổ sung phần tử vào mảng đã đầy. Vì mảng có số lượng phần tử cố định, phải được xác định lúc khai báo.Stack là rỗng khi số phần tử thực sự đang chứa trong mảng bằng 0.Cài đặt các hàm push(), pop(), empty(), size(), top() cho stack với C++#include using namespace std;#define max 10000int Stack;int Top;//init Stack with Top = -1void StackInit(){Top = -1;}void push(int V){if(Top > max-1){coutKết quảSize of Stack = 510199Size of Stack after pop = 3Nhận xét: Khuyết điểm của việc xây dựng stack bằng mảng (array) là mảng sẽ bị tràn nếu số lượng phần tử trong stack vượt quá số lượng phần tử tối đa trong mảng. Chúng ta sử dụng danh sách liên kết đơn (linked list) để xây dựng stack nhằm khắc phục khuyết điểm này.

Xem thêm: Emperor: Rise Of The Middle Kingdom, ► Hướng Dẫn Viết Hóa,

3. Xây dựng ngăn xếp bằng danh sách liên kết đơn

Khi cài đặt stack bằng danh sách liên kết đơn, ta bỏ qua việc kiểm tra stack bị tràn. Đồng thời, phần tử đầu tiên trong danh sách liên kết đơn được xem là phần tử cuối cùng được thêm vào stack. Tức là, hàm push() của stack thì xử lý là thêm node vào đầu danh sách liên kết đơn. Còn hàm pop() của stack là hủy phần tử đầu tiên trong danh sách.
#include using namespace std;struct node{int data;node *next;};node *Top;void StackInit() {Top = NULL;}void push(int V){node *p;p = new node;p->data = V;if(Top != NULL){p->next = Top;Top = p;}else{p->next = NULL;Top = p;}}int pop(){if(Top == NULL){coutdata;node *p = Top->next;delete Top;Top = p;return res;}}int empty(){if(Top == NULL){return 0;//stack is empty}return 1;//stack isnot empty}int size(){if(Top == NULL){return 0;}else{int sizeStack = 0;node *p;p = Top;while(p!=NULL){sizeStack++;p = p->next;}return sizeStack;//size of stack}}//return value at Topint top(){if (Top == NULL){coutdata;return res;}}int main(){//init StackStackInit();//push to Stackpush(5);push(21);push(10);push(99);push(101);//size of StackcoutKết quảSize of Stack = 510199Size of Stack after pop = 3
Bài trước và bài sau trong môn học>" data-wpel-link="internal">Hàng đợi (queue) là gì? Cách xây dựng hàng đợi >>