Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
Chương 3
CẤU TRÚC STACK & QUEUE
1. GIỚI THIỆU VỀ STACK
1.1 Khái niệm về stack
Stack có thể được xem là một dạng danh sách đặc biệt trong đó các tác vụ thêm
vào hoặc xóa đi một phần tử chỉ diễn ra ở một đầu gọi là đỉnh stack. Trên stack các nút
được thêm vào sau lại được lấy ra trước nên cấu trúc stack còn được gọi là LIFO (Last In
First Out).
Stack được dùng rộng rải để giải quyết các vấn đề có cơ chế LIFO, ví dụ các trình
biên dịch của các ngôn ngữ lập trình thường dùng stack để kiểm tra cú pháp của các câu
lệnh, để xử lý các biểu thức toán học, để xử lý việc gọi các chương trình con, xử lý việc
gọi hàm đệ qui … Stack cũng thường được dùng để chuyển một giải thuật đệ qui thành
giải thuật không đệ qui.
Có hai tác vụ chính trên stack là tác vụ push dùng để thêm một phần tử vào đỉnh
stack và tác vụ pop dùng để xoá đi một phần tử ra khỏi đỉnh stack.
Hình sau đây mô tả hình ảnh của stack qua các tác vụ:
push(s,A): hình a.
push(s,B): hình b.
pop(s): hình c.
push(s,C): hình d.
1.2 Mô tả stack
Mô tả dữ liệu:
Stack là một kiểu dữ liệu trừu tượng có nhiều nút cùng kiểu dữ liệu trải dài từ đáy
stack đến đỉnh stack.
Mô tả các tác vụ:
• Tác vụ initialize:
Chức năng: khởi động stack
Dữ liệu nhập: không
Dữ liệu xuất: stack top trở về đầu stack.
• Tác vụ empty

ngôn ngữ lập trình như:
 kiểm tra cú pháp của các câu lệnh trong ngôn ngữ lập trình.
 Xử lý các biểu thức toán học: kiểm tra tính hợp lệ của các dấu
trong ngoặc một biểu thức, chuyển biếu thức từ dạng trung tố (infix) sang
dạng hậu tố (postfix), tính giá trị của biểu thứ dạng hậu tố.
 Xử lý việc gọi các chương trình con.
• Stack thường được sử dụng để chuyển một giải thuật đệ qui thành giải thuật
không đệ qui.
2. HIỆN THỰC STACK
2.1 Hiện thực stack bằng danh sách kề
Khai báo cấu trúc stack: là môt mẩu tin có hai trường:
 Trường top: là một số nguyên chỉ đỉnh stack.
 Trường nodes: là mảng một chiều, mỗi phần tử của mảng là một nút của stack.
#define MAXSTACK 100
struct stack{
int top;
int nodes[MAXSTACK];
}
Trang: 2
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
Tác vụ empty
int empty(struct stack *ps){
if(ps->top==-1)
return TRUE;
else
return FALSE;
}
Tác vụ push
void push(struct stack *ps, int x){
ps->nodes[++(ps->top)]=x;

Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
NODEPTR getnode(char c){
NODEPTR q;
q=(NODEPTR)malloc(sizeof(struct node));
q->info=c;
q->next=NULL;
return q;
}
Tác vụ thêm một phần tử vào stack
void push(char c){
NODEPTR p;
p=getnode(c);
p->next=top;
top=p;
}
Tác vụ lấy một phần tử ra khỏi stack
char pop(){
NODEPTR p;
char c;
f(top !=NULL){
p=top;
top=top->next;
c=p->info;
free(p);
return c;
}else{
printf("\n stack trong");
return -1;
}
}

ps->top+=1;
ps->nodes[ps->top]=x;
}
}
//lay mot ky tu ra khoi stack
char pop(struct stack *ps){
if(empty(ps))
printf("%s","Stack bi rong");
else{
char c;
c=ps->nodes[ps->top];
ps->top-=1;
return c;
}
return ' ';
}
void main()
{
struct stack s;
char c, chuoi[MAXSTACK];
int i, vitri;
clrscr();
do{
s.top=-1;
printf("\n\n Chuoi ban nhap vao:");
scanf("%s",chuoi);
vitri =strlen(chuoi);
for(i=0; i<vitri;i++){
push(&s,chuoi[i]);
}

if(ps->top==MAXSTACK -1)
printf("\n Stack bi day");
else{
ps->top++;
ps->nodes[ps->top]=x;
}
}
//lay ra khoi stack
int pop(STACK *ps){
if(empty(ps))
printf("\nStack bi rong");
else{
int i=ps->nodes[ps->top];
ps->top ;
return i;
}
return -1;
}
Trang: 6
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
void main(){
STACK s;
int coso,so,sodu;
char c;
do{
s.top=-1;
printf("\n Nhap vao mot so thap phan");
scanf("%d",&so);
printf("\n Co so ban muon doi sang: ");
scanf("%d",&coso);

return TRUE;
else
return FALSE;
}
NODEPTR getnode(char c){
Trang: 7
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
NODEPTR q;
q=(NODEPTR)malloc(sizeof(struct node));
q->info=c;
q->next=NULL;
return q;
}
void push(char c){
NODEPTR p;
p=getnode(c);
p->next=top;
top=p;
}
char pop(){
NODEPTR p;
char c;
f(top !=NULL){
p=top;
top=top->next;
c=p->info;
free(p);
return c;
}else{
printf("\n stack trong");

đợi (rear).
Có hai tác vụ chính trên hàng đợi là insert – thêm nút mới vào cuối hàng đợi và tác vụ
remove dùng để xoá một phần tử ra khỏi hàng đợi.
Hình vẽ sau đây dùng để mô tả hàng đợi qua các tác vụ như sau:
• Trạng thái bắt đầu: hàng đợi bị rỗng (hình a)
• insert (q,A)
• insert (q,B)
• insert (q,C) (hình b)
• remove(q) (hình c)
• insert(q,D) (hình d)
• remove(q) (hình e)
• insert(q,E) (hình f)
Trang: 9
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
4.2 Mô tả hàng đợi
Mô tả dữ liệu:
Hàng đợi là một kiểu dữ liệu trừu tượng có nhiều nút cùng kiểu dữ liệu trải dài từ đầu
hàng đợi đến cuối hàng đợi.
Mô tả các tác vụ:
• Tác vụ initialize
Chức năng: khởi động hàng đợi
Dữ liệu nhập: không
Dữ liệu xuất: hai con trỏ front và rear được gán các giá trị phù hợp.
• Tác vụ empty
Chức năng: kiểm tra hàng đợi có bị rỗng hay không
Dữ liệu nhập: không
Dữ liệu xuất: TRUE|FALSE
• Tác vụ insert
Trang: 10
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack

dịch vụ ngân hàng, xử lý các tác vụ đang đợi phục vụ trong các hệ điều hành đa
người sử dụng, quản lý các yêu cầu in trong máy server printers…
5. HIỆN THỰC QUEUE
5.1 Dùng mảng vòng hiện thực hàng đợi
Đây là cách thường dùng nhất để cài đặt hàng đợi theo kiểu kế tiếp. Lúc này ta xem mảng
như là mảng vòng chứ không phải là mảng thẳng: nút nodes[0] xem như là nút sau của
nút nodes[MAXQUEUE -1].
Khai báo cấu trúc:
#define MAXQUEUE 100
struct queue{
int front, rear;
int nodes[MAXQUEUE];
}
Trang: 11
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
Tác vụ khởi động:
void initialize(struct queue *pq){
pq->front=pq->rear=MAXQUEUE-1;
}
Tác vụ kiểm tra hàng đợi trống:
int empty(struct queue *pq){
if(pq->front==pq->rear)
return TRUE;
else{
return FALSE;
}
}
Tác vụ thêm vào hàng đợi:
void insert(struct queue *pq, int x){
if(pq->rear==MAXQUEUE -1)

i=0;
else
i=pq->front+1;
while(i!=pq->rear){
printf(“%d”,pq->nodes[i]);
if(i==MAXQUEUE-1)
i=0;
else
i++;
}
printf(“%d”,pq->nodes[i]);
}
5.2 Dùng danh sách liên kết hiện thực hàng đợi
Ta có thể cài đặt hàng đợi như một danh sách liên kết: con trỏ đầu danh sách liên kểt
front chỉ nút tại đầu hàng đợi, con trỏ rear trỏ đến nút cuối cùng của hàng đợi.
Hình vẽ sau thể hiện cách cài đặt hàng đợi bằng danh sách liên kết.
Với cách cài đặt này ta có thể hiện thực các tác vụ của hàng đợi như: insert, remove,
empty…trên danh sách liên kết.
5.3 Hàng đợi có ưu tiên
Hàng đợi hoạt động trên nguyên tắc nút nào vào trước được lấy ra trước, nút nào vào sau
được lấy ra sau là hàng đợi không có ưu tiên.
Trong thực tế có một dạng hàng đợi khác hoạt động theo cơ chế: nút nào có độ ưu tiên
cao hơn sẽ được lấy ra trước, nút nào có độ ưu tiên thấp hơn thì lấy ra sau. Hàng đợi lúc
này gọi là hàng đợi có ưu tiên (priority queue).
Có 2 loại hàng đợi có ưu tiên:
Hàng đợi có ưu tiên tăng: nút có độ ưu tiên cao nhất được lấy ra.
Hàng đợi có ưu tiên giảm: nút có độ ưu tiên giảm sẽ được lấy ra trước.
Phần hiện thực hàng đợi ưu tiên sẽ được xem như bài tập.
6. CHƯƠNG TRÌNH MINH HOẠ
Giả sử chúng ta có một kho hàng có tính chất: mặt hàng nào nhập kho trước sẽ xuất kho

else
pq->rear++;
if(pq->rear==pq->front)
printf("Kho hang bi day");
else
pq->nodes[pq->rear]=x;
}
mathang remove(struct queue *pq){
if(pq->front==MAXQUEUE -1)
pq->front=0;
else
pq->front++;
return pq->nodes[pq->front];
}
void traverse(struct queue *pq){
int i;
Trang: 14
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
if(empty(pq)){
printf("\n Kho khong con hang");
return;
}
if(pq->front==MAXQUEUE-1)
i=0;
else
i=pq->front+1;
while(i !=pq->rear){
printf("\n%11d%15s",pq->nodes[i].mamh,pq->nodes[i].tenmh);
if(i==MAXQUEUE-1){
i=0;

Trang: 15
Giáo trình Cấu trúc dữ liệu và thuật giải Chương 3: Cấu trúc Stack
scanf("%s",&mh.tenmh);
insert(&q,mh);
break;
case 2:
if(!empty(&q)){
mh=remove(&q);
printf("\n Mat hang xuat: Ma: %d Ten:
%s",mh.mamh,mh.tenmh);
}
else
printf("\n Kho khong con hang");
break;
case 3:
if(q.front==MAXQUEUE -1)
front1=0;
else
front1=q.front+1;
printf("\n Mat hang chuan bi xuat: Ma: %d Ten: %s
",q.nodes[front1].mamh,q.nodes[front1].tenmh);
break;
case 4:
printf("\n Mat hang moi nhap: Ma: %d Ten: %s",
q.nodes[q.rear].mamh,q.nodes[q.rear].tenmh);
break;
case 5:
printf("\n Cac mat hang co trong kho: ");
printf("\n %11s%15s", "MA MAT HANG","TEN MAT
HANG");

diễn của biểu thức nguyên A. Hãy dịch các biểu thức nguyên A thành dạng viết Ba Lan
của A ghi vào file balan.out theo từng dòng. Ví dụ
Balan.in Balan.out
a+b a b +
a-b a b –
a*b a b *
a / b a b /
((a+b)*c-(d+e)*f) a b + c* d e + f * -
5. Tính toán giá trị biểu thức Ba Lan. Cho file dữ liệu balan.in gồm 2*n dòng trong đó,
dòng có số thứ tự lẽ (1, 3, 5, …) ghi lại một xâu là biểu diễn Ba Lan của biểu thức
nguyên A, dòng có số thứ tự chẵn (2,4,6…) ghi lại giá trị các biến xuất hiện trong biểu
thức A. Hãy tính giá trị của biểu thức A, ghi lại giá trị của A vào file balan.out từng dòng
theo thứ tự: Dòng có thứ tự lẻ ghi lại biểu thức Ba Lan của A sau khi đã thay thế các giá
trị tương ứng của biến trong A, dòng có thứ tự chẵn ghi lại giá trị của biểu thức trong A.
Ví dụ:
Balan.in balan.out
a b + 3 5 +
3 5 8
a b - 7 3 –
7 3 4
6. Lập lịch với mức độ ưu tiên. Để lập lịch cho CPU đáp ứng cho các quá trình đang đợi
của hệ thống, người ta biểu diễn mỗi quá trình bằng một bản ghi bao gồm những thông
tin: số hiệu quá trình là một số tự nhiên nhỏ hơn 1024, tên quá trình là một xâu ký tự có
độ dài không quá 32 ký tự, độ ưu tiên của quá trình là một số nguyên dương nhỏ hơn 10,
và thời gian thực hiện quá trình là một số thực. Các quá trình đang đợi trong hệ thống
được CPU đáp ứng thông qua một hàng đợi được gọi là hàng đợi các quá trình, hàng đợi
các quá trình với độ ưu tiên được xây dựng sao cho điều kiện sau đây được thoả mãn:
- Các quá trình được sắp theo thứ tự ưu tiên.
- Đối với những quá trình có cùng độ ưu tiên thì quá trình nào có thời gian thực hiện ít
nhất được xếp lên trước nhất.