Stack là gì? định nghĩa và giải thích ý nghĩa

     

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

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

Bạn đang xem: Stack là gì? định nghĩa và giải thích ý nghĩa


*

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

Xem thêm: Đánh Giá Xiaomi Poco X3 Pro, Đánh Giá Chi Tiết Xiaomi Poco X3 Pro

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

2. Xây cất ngăn xếp bởi mảng

Khi gây ra stack bằng mảng thì họ lưu ý một vài vấn đề sau:Thêm một trong những phần tử vào stack có nghĩa là thêm một phần tử vào thời gian cuối mảng.Loại bỏ 1 phần tử khỏi stack có nghĩa là loại bỏ 1 phần tử ở cuối mảng.Stack bị tràn khi xẻ sung thành phần vào mảng vẫn đầy. Do mảng gồm số lượng phần tử cố định, đề nghị được khẳng định lúc khai báo.Stack là rỗng khi số phần tử thực sự đang đựng trong mảng bằng 0.Cài đặt các hàm push(), pop(), empty(), size(), top() mang đến stack với C++#include using namespace std;#define max 10000int Stack;int Top;//init Stack with đứng 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: yếu đ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 thừa số lượng thành phần tối đa trong mảng. Chúng ta sử dụng danh sách links đơn (linked list) để tạo stack nhằm khắc phục và hạn chế khuyết điểm này.

Xem thêm: Top Ứng Dụng Sách Nói Tiếng Việt Miễn Phí, Hay Nhất Trên Điện Thoại

3. Gây ra ngăn xếp bằng danh sách links đơn

Khi thiết đặt stack bằng danh sách link đơn, ta quăng quật qua bài toán kiểm tra stack bị tràn. Đồng thời, bộ phận đầu tiên trong danh sách link đơn được xem như là phần tử cuối cùng được phân phối stack. Tức là, hàm push() của stack thì giải pháp xử lý là thêm node vào đầu danh sách link đơn. Còn hàm pop() của stack là hủy bộ phận đầu tiên trong danh sách.
#include using namespace std;struct nodeint 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;elsep->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 emptyreturn 1;//stack isnot emptyint size()if(Top == NULL)return 0;elseint 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 khổng lồ 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 xích sau vào môn học>" data-wpel-link="internal">Hàng hóng (queue) là gì? cách xây dựng hàng đợi >>