I. Stack(ngăn xếp)
1. Nguyên tắc hoạt động: LIFO
2. Cài đặt: Có thể sử dụng mảng hoặc danh sách liên kết đơn hoặc kép
* Bổ sung(PUSH) và lấy ra(POP) đều thực hiện trên 1 đầu gọi là đỉnh(TOP)
3. Các thao tác cơ bản:
a. Khởi tạo Stack = 0
b. Bổ sung 1 phần tử vào Stack
PUSH(x, Stack);
c. Lấy 1 phần tử ra khỏi Stack
x = POP(Stack);
4. Ứng dụng của Stack:
a. Khử đệ quy
VD: Biểu diễn nhị phân của số nguyên dương n
void Bin(int n)
{
Stack s= 0;
while(n>0)
{
PUSH(n%2,s);
n=n/2;
}
while(s!=0)
printf(POP(s));
}
#include <iostream.h>
void PUSH(int x, int &Top, int Stack[])
{
Top++;
Stack[Top]=x;
}
int POP(int &Top, int Stack[])
{
int x = Stack[Top];
Top--;
return x;
}
void BIN(int n)
{
int Top=0, S[100];
while(n>0)
{
PUSH(n%2,Top,S);
n=n/2;
}
while(S!=0)
printf(POP(Top,s));
}
b. Biểu diễn biểu thức theo ký pháp nghịch đảo Balan
Biểu thức:
- Trung tố
- Tiền tố
- Hậu tố
VD: (6-2)*(3+4) -> Trung tố
=> * - 6 2 + 3 4 -> Tiền tố(toán tử đứng trước toán hạng)
=> 6 2 - 3 4 + * -> Hậu tố(toán tử đứng sau toán hạng)
* 2 công đoạn:
Stack
1. Chuyển từ dạng trung tố sang hậu tố
2. Tính giá trị biểu thức hậu tố
posfix stack
6 2 - 3 4 + * 0
2 - 3 4 + * 6
- 3 4 + * 6 2
3 4 + * 4
4 + * 4 3
+ * 4 3 4
* 4 7
0 28
II - Queue(hàng đợi)
1. Nguyên tắc: FIFO
2. Cài đặt:
- Bổ sung(PUSH) ở 1 đầu
- Lấy ra(POP) ở đầu kia