Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 3: Cấu trúc Stack & Queue

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 Chức năng: kiểm tra stack có rỗng hay không. Dữ liệu nhập: không. Dữ liệu xuất: TRUE|FALSE. Tác vụ push Chức năng: thêm nút mới tại đỉnh stack. Dữ liệu nhập: nút mới Dữ liệu xuất: không. Tác vụ pop Chức năng: xóa nút tại đỉnh stack. Dữ liệu nhập: không Điều kiện: stack không bị rỗng. Dữ liệu xuất: nút bị xoá. Tác vụ stacktop Chức năng: truy cập nút tại đỉnh stack. Dữ liệu nhập: không. Điều kiện: stack không bị rỗng. Dữ liệu xuất: nút tại đỉnh stack. Tác vụ stacksize Chức năng: xác định số nút hiện có trong stack. Dữ liệu nhập: không. Dữ liệu xuất: số nút hiện có trong stack. Tác vụ clearstack Chức năng: xoá tấc cả các nút có trong stack. Dữ liệu nhập: không Dữ liệu xuất: stack top về vị trí khởi đầu. 1.3 Ứng dụng của stack Stack thường được dùng để giải quyết các vấn đề có cơ chế LIFO. Stack thường được dùng để giải quyết các vấn đề trong trình biên dịch của các 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]; } 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; } Tác vụ pop int pop(struct stack *ps){ if(empty(ps)){ printf(“Stack bi rong”); }else{ return ps->nodes[ps->top--]; } } 2.2 Hiện thực stack bằng danh sách liên kết Khai báo cấu trúc stack: struct node{ char info; node *next; }; typedef struct node* NODEPTR; NODEPTR top; Tác vụ khởi tạo stack void initialize(){ top=NULL; } Tác vụ kiểm tra stack rỗng int empty(){ if (top==NULL) return TRUE; else return FALSE; } Tác vụ cấp phát bộ nhớ 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; } } 3. CÁC CHƯƠNG TRÌNH MINH HOẠ 3.1. Chương trình đảo chuỗi dùng stack #include #include #include #include #define MAXSTACK 100 #define TRUE 1 #define FALSE 0 //dinh nghia stack struct stack{ int top; char nodes[MAXSTACK]; }; //empty operation: check for whether stack is empty int empty(struct stack *ps){ if(ps->top==-1){ return TRUE; } else{ return FALSE; } } // dua 1 ky tu vao stack void push(struct stack* ps, char x){ if(ps->top==MAXSTACK-1) printf("%s","Stack is full"); else{ 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]); } printf("\n\n Chuoi dao la: "); while(!empty(&s)){ printf("%c",pop(&s)); } printf("\n\n Tiep tuc khong? (c/k): "); c=getche(); }while(c=='c'||c=='C'); } 3.2 Chương trình đổi cơ số thập phân sang cơ số bất kỳ #include #include #include #define MAXSTACK 100 #define TRUE 1 #define FALSE 0 typedef struct stack{ int top; int nodes[MAXSTACK]; } STACK; //Check stack is empty int empty(STACK *ps){ if(ps->top==-1) return TRUE; else return FALSE; } //dua vao stack void push(STACK *ps, int x){ 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; } 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); while( so !=0){ sodu=so %coso; push(&s, sodu); so=so/coso; } printf("\n So da doi la: "); while(!empty(&s)){ printf("%X",pop(&s)); } printf("\n \n Ban co muon tiep tuc khong? "); c=getche(); }while(c=='c'||c=='C'); } 3.3 Chương trình đảo chuỗi hiện thực stack bằng danh sách liên kết #include #include #include #define TRUE 1 #define FALSE 0 struct node{ char info; node *next; }; typedef struct node* NODEPTR; NODEPTR top; void initialize(){ top=NULL; } int empty(){ if (top==NULL) return TRUE; else return FALSE; } NODEPTR getnode(char c){ 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"); return -1; } } void main(){ char chuoi[30]; int chieudai,i; initialize(); printf("\n Nhap vao chuoi: "); scanf("%s",chuoi); chieudai=strlen(chuoi); for(i=0;i<chieudai;i++) push(chuoi[i]); printf("\n Chuoi dao: "); while(!empty()){ printf("%c",pop()); } } 4. GIỚI THIỆU VỀ QUEUE Queue là một dạng danh sách đặt biệt, trong đó chúng ta chỉ được phép thêm vào các phần tử ở cuối hàng đợi và xoá đi các phần tử ở đầu hàng đợi. Vì phần tử thêm vào trước được lấy ra trước nên cấu trúc hàng đợi còn được gọi là cấu trúc FIFO( First In First Out). Hàng đợi là cấu trúc được sử dụng rộng rãi trong thực tế: người ta dùng hàng đợi để giải quyết các vấn đề có cấu trúc FIFO như xử lý các dịch vụ của ngân hàng, để xử lý các tiến trình đang đợi phục vụ trong các hệ điều hành nhiều người sử dụng, quản lý các yêu cầu in trên máy print servers… 4.1 Khái niệm về hàng đợi Hàng đợi chứa các nút có cùng kiểu dữ liệu trải dài từ đầu hàng đợi (front) đến cuối hàng đợ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) 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 Chức năng: Thêm nút mới vào hàng đợi. Dữ liệu nhập: nút mới Điều kiện: hàng đợi không bị đầy. Dữ liệu xuất: không. Tác vụ remove Chức năng: xóa nút tại đầu hàng đợi Dữ liệu nhập: không Điều kiện: hàng đợi không bị rỗng Dữ liệu xuất: nút bị xóa. Tác vụ queuefront Chức năng: truy xuất nút tại đầu hàng đợi Dữ liệu nhập: không Điều kiện: hàng đợi không bị rỗng. Dữ liệu xuất: nút tại đầu hàng đợi. Tác vụ queuerear Chức năng: truy xuất nút cuối của hàng đợi Dữ liệu nhập: không Điều kiện: hàng đợi không bị rỗng Dữ liệu xuất: nút cuối cùng của hàng đợi Tác vụ queuesize Chức năng: xác định số nút hiện có trong hàng đợi Dữ liệu nhập: không Dữ liệu xuất: số nút có trong hàng đợi Tác vụ clearqueue Chức năng: xoá tất cả các nút có trong hàng đợi Dữ liệu nhập: Không Dữ liệu xuất: front và rear được trả về vị trí ban đầu. 4.3 Ứng dụng của hàng đợi Hàng đợi được dùng để giải quyết các vấn đề có cơ chế FIFO (First In First Out). Trong thực tế người ta thường cài đặt hàng đợi trong các chương trình xử lý các 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]; } 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) pq->rear=0; else pq->rear++; if(pq->rear==pq->front) printf(“Hang doi bi day”); else pq->nodes[pq->rear]=x; } Tác vụ xoá một phần tử ra khỏi hàng đợi int remove(struct queue *pq){ if(empty(pq)) printf(“hang doi bi day”); else{ if(pq->front==MAXQUEUE-1) pq->front=0; else pq->front++; return pq->nodes[pq->front]; } } Tác vụ duyệt hàng đợi void traverse(struct queue *pq){ int i; if(empty(pq)){ printf(“Hang doi bi rong”); return; } if(pq->front==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 trước, mặt hàng nào nhập kho sau sẽ xuất kho sau. Chương trình có các chức năng nhập kho, xuất kho, xem tồn kho… //CHUONG TRINH DEMO QUAN LY KHO BANG HANG DOI #include #include #define MAXQUEUE 100 #define TRUE 1 #define FALSE 0 typedef struct mathang{ int mamh; char tenmh[12]; }; struct queue{ int front,rear; mathang nodes[MAXQUEUE]; }; void initialize(struct queue *pq){ pq->front=pq->rear=MAXQUEUE -1; } int empty(struct queue *pq){ if(pq->front==pq->rear) return TRUE; else return FALSE; } void insert(struct queue *pq, mathang x){ if(pq->rear==MAXQUEUE-1) pq->rear=0; 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; 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; } else{ i++; } } printf("\n%11d%15s",pq->nodes[i].mamh,pq->nodes[i].tenmh); } void main(){ struct queue q; int chucnang,front1; mathang mh; initialize(&q); do{ printf("\n\n\t\t CHUONG TRINH QUAN LY KHO"); printf("\n\t\t NHAP TRUOC XUAT TRUOC"); printf("\n\n Cac chuc nang cua chuong trinh"); printf("\n 1. Nhap mot mat hang"); printf("\n 2. Xuat mot mat hang"); printf("\n 3. Xem mot mat hang chuan bi xuat"); printf("\n 4. Xem mat hang moi nhap"); printf("\n 5. Xem cac mat hang co trong kho"); printf("\n 6. Xuat toan bo kho hang"); printf("\n 0. Ket thuc chuong trinh"); printf("\n\n Chuc nang ban chon: "); scanf("%d",&chucnang); switch(chucnang){ case 1: printf("\n Ma mat hang: "); scanf("%d",&mh.mamh); printf("\n Ten mat hang: "); 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"); traverse(&q); break; case 6: initialize(&q); break; } }while(chucnang !=0); } 7. BÀI TẬP 1. Hiện thực hàng đợi và các tác vụ của hàng đợi bằng danh sách liên kết. 2. Viết chương trình quản lý kho hàng dùng hàng đợi được hiện thực bằng danh sách liên kết. 3. Viết chương trình hiện thực hàng đợi có độ ưu tiên. 4. Biểu diễn biểu thức theo cú pháp Ba Lan. Biểu thức nguyên là một dãy được thành lập từ các biến kiểu nguyên nối với nhau bằng các phép toán 2 ngôi: +, -, *, / và các dấu ‘)’, ‘(’. Nguyên tắc đặc tên biến và thứ tự thực hiện các phép toán được thực hiện như sau: Qui tắc đặt tên biến: là dãy các ký tự chữ in thường hoặc ký tự số độ dài không quá 8, ký tự bắt đầu phải là một chữ cái. Qui tắc thực hiện phép toán: biểu thức trong dấu ngoặc đơn được tính trước, phép toán * và / có độ ưu tiên cao hơn phép toán + và -. Dạng viết không dấu ngoặc Ba Lan cho biểu thức nguyên được định nghĩa như sau: - Nếu e là tên biến thì dạng Ba Lan của nó chính là E. - Nếu e1 và e2 là hai biểu thức có dạng viết Ba Lan tương ứng là d1 và d2 thì dạng viết Ba Lan của e1+e2 là d1 d2 +, của e1-e2 là d1 d2 -, của e1*e2 là d1 d2 *, của e1 / e2 là e1 e2 /. -Nếu e là biểu thức có dạng viết Ba Lan là d thì dạng viết Ba Lan của biểu thức có dấu ngoặc đơn (e) chính là d. Ví dụ biểu thức (c+b*(f-d)) có dạng viết Ba Lan là c b f d - * +. Cho file balan.in được tổ chức thành từng dòng, mỗi dòng dài không quá 80 ký tự là biểu 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. Cho file dữ liệu vào lich.in được tổ chức như sau: - Dòng đầu tiên ghi số n là số các quá trình - n dòng kế tiếp, mỗi dòng ghi một thông tin về quá trình đang đợi. Hãy xây dựng hàng đợi các quá trình với độ ưu tiên. Ghi lại thứ tự các quá trình mà CPU đáp ứng trên một dòng của file lich.out. Dòng kế tiếp ghi lại số giờ cần thiết mà CPU cần phải đáp ứng cho các quá trình. Lich.in 7 1 Data_processing 1 10 2 Editor_program 1 20 3 System_Call 3 0.5 4 System_interactive 3 1 5 System_Action 3 2 6 Writing_Data 2 20 7 Reading_Data 2 10 Lich.out 3 4 5 7 6 1 2 63.5