Ngăn xếp
Ngăn xếp là cấu trúc dữ liệu trừu tượng (ADT), thường được sử dụng trong hầu hết các ngôn ngữ lập trình. Nó được đặt tên là stack vì nó hoạt động giống như một ngăn xếp trong thế giới thực, ví dụ - một cỗ bài hoặc một đống đĩa, v.v.
Một ngăn xếp trong thế giới thực chỉ cho phép các hoạt động tại vị trí trên cùng của ngăn xếp. Ví dụ, chúng ta chỉ có thể đặt hoặc thêm một lá bài hay một cái đĩa vào trên cùng của ngăn xếp. Do đó, cấu trúc dữ liệu trừu tượng ngăn xếp chỉ cho phép các thao tác dữ liệu tại vị trí trên cùng. Tại bất cứ thời điểm nào, chúng ta chỉ có thể truy cập phần tử trên cùng của ngăn xếp.
Đặc điểm này làm cho ngăn xếp trở thành cấu trúc dữ liệu dạng LIFO. LIFO là viết tắt của Last-In-First-Out. Ở đây, phần tử được đặt vào (được chèn, được thêm vào) cuối cùng sẽ được truy cập đầu tiên. Trong thuật ngữ ngăn xếp, hoạt động chèn được gọi là hoạt động PUSH và hoạt động xóa được gọi là hoạt động POP.
Mô tả cấu trúc dữ liệu ngăn xếp
Sơ đồ sau mô tả một ngăn xếp và các hoạt động của nó:
Một ngăn xếp có thể được triển khai theo phương thức của Mảng, Cấu trúc, Con trỏ và Danh sách Liên kết. Stack có thể là một kích thước cố định hoặc nó có thể có ý nghĩa thay đổi kích thước. Phần dưới chúng ta sẽ triển khai ngăn xếp bởi sử dụng các mảng với việc triển khai các ngăn xếp cố định.
Hoạt động cơ bản
Các hoạt động ngăn xếp có thể liên quan đến việc khởi tạo ngăn xếp, sử dụng nó và sau đó xóa nó. Ngoài những thứ cơ bản này, một ngăn xếp được sử dụng cho hai thao tác chính sau:
- push () - Đẩy (lưu trữ) một phần tử trên ngăn xếp.
- pop () - Loại bỏ (truy cập) một phần tử khỏi ngăn xếp.
Khi dữ liệu đã được PUSH lên trên ngăn xếp:
Để sử dụng stack một cách hiệu quả, chúng ta cũng cần kiểm tra trạng thái của stack. Để phục vụ cho mục đích này, dưới đây là một số tính năng hỗ trợ khác của ngăn xếp:
- peek () - lấy phần tử ở trên cùng của ngăn xếp mà không xóa nó.
- isFull () - kiểm tra xem ngăn xếp đã đầy chưa.
- isEmpty () - kiểm tra xem stack có trống không.
Tại mọi thời điểm, chúng ta duy trì một con trỏ tới phần tử dữ liệu vừa được PUSH cuối cùng vào trên ngăn xếp. Vì con trỏ này luôn đại diện cho đỉnh của ngăn xếp, do đó được đặt tên là top . Con trỏ top cung cấp giá trị của phần tử trên cùng của ngăn xếp mà không thực sự loại bỏ nó.
Trước tiên chúng ta nên tìm hiểu về các thủ tục để hỗ trợ các chức năng ngăn xếp:
peek()
Giải thuật của hàm peek():
begin procedure peek
return stack[top]
end procedure
Triển khai hàm peek() trong ngôn ngữ C:
Ví dụ:
int peek() {
return stack[top];
}
isfull()
Giải thuật của hàm isfull():
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
Triển khai hàm isfull() trong ngôn ngữ C:
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
isempty()
Giải thuật của hàm isempty():
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
Sự triển khai của hàm isempty() trong ngôn ngữ C sẽ hơi khác một chút. Chúng ta khởi tạo top từ -1, giống như chỉ mục của mảng bắt đầu từ số 0. Vì thế, chúng ta kiểm tra nếu top là dưới 0 hoặc -1 để xác định thêm stack có trống hay không. Dưới đây là đoạn mã:
Ví dụ:
bool isempty() {
if(top == -1)
return true;
else
return false;
}
Hoạt động Push
Quá trình đưa một phần tử dữ liệu mới vào ngăn xếp được gọi là thao tác push. Hoạt động push bao gồm một loạt các bước:
- Bước 1 - Kiểm tra xem ngăn xếp đã đầy chưa.
- Bước 2 - Nếu ngăn xếp đầy, tiến trình bị lỗi và thoát.
- Bước 3 - Nếu ngăn xếp không đầy, hãy tăng từ top để trỏ tới phần tử bộ nhớ trống tiếp theo.
- Bước 4 - Thêm phần tử dữ liệu vào vị trí ngăn xếp, nơi mà top đang trỏ đến trên ngăn xếp
- Bước 5 - Trả về thành công.
Nếu danh sách liên kết được sử dụng để thực hiện ngăn xếp, thì trong bước 3, chúng ta cần cấp phát một không gian động.
Thuật toán cho hoạt động PUSH
Một thuật toán đơn giản cho hoạt động Push có thể được bắt đầu như sau -
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure
Thực hiện thuật toán này trong C, rất dễ dàng. Xem mã sau -
Thí dụ
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
Hoạt động Pop
Việc truy cập nội dung phần tử trong khi xóa nó từ ngăn xếp còn được gọi là Hoạt động POP. Trong một triển khai mảng của hoạt động pop (), phần tử dữ liệu không thực sự bị loại bỏ, thay vào đó top sẽ bị giảm về vị trí thấp hơn trong ngăn xếp để trỏ tới giá trị tiếp theo. Nhưng trong sự triển khai Danh sách liên kết, hoạt động pop() thực sụ xóa phần tử xữ liệu và xóa nó khỏi không gian bộ nhớ.
Hoạt động POP có thể bao gồm các bước sau:
- Bước 1: kiểm tra xem ngăn xếp là trống hay không.
- Bước 2: nếu ngăn xếp là trống, tiến trình bị lỗi và thoát ra.
- Bước 3: nếu ngăn xếp là không trống, truy cập phần tử dữ liệu tại top đang trỏ tới.
- Bước 4: giảm giá trị của top đi 1.
- Bước 5: trả về thành công.
Thuật toán cho hoạt động Pop
Một thuật toán đơn giản cho hoạt động Pop có thể được bắt đầu như sau:
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
Việc thực hiện thuật toán này trong C, như sau -
Thí dụ
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
- Hiếu Kiều -
Bài viết nổi bật
Bài viết nổi bật