Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách đặc (mảng)

Chương 3 Danh sách đặc (Mảng) 3.1. Định nghĩa • Mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ. • Mảng có thể một chiều hay nhiều chiều. • Mảng hai chiều có thể coi là mảng một chiều trong đó mỗi phần tử của nó là 1 mảng một chiều. 16/11/2008 2Cấu trúc dữ liệu 1 • Mảng 1 chiều được khai báo như sau: []; VD: int a[100]; Hoặc vừa khai báo vừa gán giá trị khởi động cho mảng: int a[5] = {1, 7, -2, 8, 19}; Hoặc: int a[]= {1, 7, -2, 8, 19}; 16/11/2008 3Cấu trúc dữ liệu 1 3.1. Định nghĩa 16/11/2008 4Cấu trúc dữ liệu 1 Tương tự, có thể khai báo mảng 2 chiều hay nhiều chiều như sau: [][]...; VD: int a[100][150]; Hoặc: int a[][] = {{1, 7, -3, 8, 19}, {4, 5, 2, 8, 9}, {21, 7, -45, -3, 4}}; 3.1. Định nghĩa 3.2. Các phép toán trên mảng 3.2.1. Khởi tạo mảng 16/11/2008 5Cấu trúc dữ liệu 1 void khoi_tao(int a[], int &n) { int i; cout<<“Cho biet so phan tu cua danh sach ”; cin>>n; for(i=0;i<n;i++) { cout<<“Nhap phan tu thu ”<<i<<“\t”; cin>>a[i]; } } 3.2. Các phép toán trên mảng 3.2.2. Xuất mảng 16/11/2008 6Cấu trúc dữ liệu 1 void xuat(int a[],int n) { for(int i=0;i<n;i++) cout<<a[i]<<"\t"; cout<<endl; } 16/11/2008 7Cấu trúc dữ liệu 1 Khi thêm một phần tử vào vị trí thứ k (0 ≤ k < n) thì các phần tử từ a[k+1] đến a[n-1] được di chuyển ra sau một vị trí void chen(int a[], int &n) { int i,k,x; cout>x; cout>k; for(i=n-1;i>=k-1;i--) a[i+1]=a[i]; a[k-1]=x; n++; } 3.2. Các phép toán trên mảng 3.2.3. Chèn một phần tử vào mảng 16/11/2008 8Cấu trúc dữ liệu 1 3.2. Các phép toán trên mảng 3.2.4. Xóa một phần tử của mảng Khi xóa một phần tử tại vị trí thứ k (0 ≤ k < n) thì các phần tử từ a[k+1] đến a[n-1] được di chuyển về trước một vị trí void xoa(int a[], int &n) { int i,k; cout>k; for(i=k;i<n;i++) a[i-1]=a[i]; n--; } 16/11/2008 9Cấu trúc dữ liệu 1 • Dễ cài đặt và truy nhập các phần tử dữ liệu • Tốc độ truy nhập đến một vị trí bất kỳ trên mảng nhanh, hiệu quả 3.3. Ưu và khuyết điểm của mảng 3.3.1. Ưu điểm 16/11/2008 10Cấu trúc dữ liệu 1 • Cần phải xác định trước số phần tử mảng trước khi sử dụng⇒không phù hợp với các bài toán chưa biết trước số lượng các phần tử. • Khó khăn trong các thao tác chèn và xóa một phần tử bất kỳ trong mảng. Nếu bài toán mà việc chèn phần tử và xóa phần tử diễn ra liên tục⇒ tốc độ xử lý sẽ rất chậm. 3.3. Ưu và khuyết điểm của mảng 3.3.2. Khuyết điểm 16/11/2008 11Cấu trúc dữ liệu 1 • Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2 cấu trúc dữ liệu khá phổ biến. • Chúng thể hiện cách thức lưu trữ và xử lý dữ liệu theo một trình tự đã được quy ước. 9Hàng đợi: Nguyên tắc hoạt động: FIFO (First In First Out) 9Ngăn xếp: Nguyên tắc hoạt động: LIFO (Last In First Out) 3.4. Stack và Queue 16/11/2008 12Cấu trúc dữ liệu 1 Stack là một kiểu danh sách tuyến tính đặc biệt mà phép thêm vào (PUSH) và phép lấy ra (POP) đều thực hiện ở cùng một đầu gọi là đỉnh (TOP) của stack. Do đó stack hoạt động theo nguyên tắc “vào sau ra trước” LIFO. Stack có thể rỗng hoặc chứa một số phần tử. 3.4. Stack và Queue 3.4.1. Stack Định nghĩa 16/11/2008 13Cấu trúc dữ liệu 1 Biểu diễn stack bằng mô hình mảng với các hàm: - Push theo chế độ tăng trước - Pop theo chế độ giảm sau 3.4. Stack và Queue 3.4.1. Stack Định nghĩa 3 2 1 input output top 16/11/2008 14Cấu trúc dữ liệu 1 Các thao tác chính: - isEmpty: Kiểm tra rỗng - isFull: Kiểm tra đầy - Push: Thêm 1 phần tử - Pop: Lấy ra 1 phần tử 3.4. Stack và Queue 3.4.1. Stack Cài đặt 16/11/2008 15Cấu trúc dữ liệu 1 struct Stack { int data[100]; int top; }; void Initial(Stack &s) { s.top = -1; } 3.4. Stack và Queue 3.4.1. Stack Cài đặt 16/11/2008 16Cấu trúc dữ liệu 1 int isEmpty(Stack s) { return (s.top==-1); } int isFull(Stack s) { return (s.top>=99); } 3.4. Stack và Queue 3.4.1. Stack Cài đặt 16/11/2008 17Cấu trúc dữ liệu 1 void Push(Stack &s,int k) { if (isFull(s)) return; s.data[++s.top]=k; } 3.4. Stack và Queue 3.4.1. Stack Cài đặt 16/11/2008 18Cấu trúc dữ liệu 1 int Pop(Stack &s) { if (isEmpty(s)) return -1; return s.data[s.top--]; } 3.4. Stack và Queue 3.4.1. Stack Cài đặt 16/11/2008 19Cấu trúc dữ liệu 1 Cú pháp của biểu thức: có 3 dạng 1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán hạng. VD: (4 + 5)*(8 - (4 – 1)) Khuyết điểm: - Chỉ dùng được cho các phép toán có hai toán hạng - Nếu bỏ các dấu ngoặc tròn thì phải có: + Quy định về độ ưu tiên thứ tự thực hiện phép toán + Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải sang trái) 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 20Cấu trúc dữ liệu 1 2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách các toán hạng. Có 3 dạng tiền tố cụ thể: - Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách các toán hạng. VD: *(+(1,5),-(8,-(4,1))) - Dạng tiền tố Cambridge Polish (Cambridge Polish prefix): giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD: (*(+1 5)(-8 (-4 1))) 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 21Cấu trúc dữ liệu 1 2. Tiền tố (prefix): - Dạng tiền tố Polish (Polish prefix): các dấu ngoặc tròn được loại bỏ luôn. VD: *+1 5 – 8 - 4 1 Nhận xét: - Dạng tiền tố không được tự nhiên như dạng trung tố - Dạng tiền tố có thể dùng cho các phép toán có số lượng toán hạng bất kỳ, như các phép toán một toán hạng (NOT), các phép gọi hàm. - Dạng tiền tố biểu diễn trực tiếp cơ chế chồng chất hàm nên việc sinh mã thực thi cho biểu thức ở dạng tiền tố cũng dễ dàng hơn dạng trung tố. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 22Cấu trúc dữ liệu 1 3. Hậu tố hay dạng Ba Lan đảo (postfix hay suffix): cũng như dạng tiền tố nhưng ký hiệu phép toán được viết sau danh sách các toán hạng. VD: ((1,5)+,(8,(4,1)-)-)* hay 1 5 + 8 4 1 - - * Nhận xét: - Thứ tự xuất hiện từ trái sang phải của các ký hiệu phép toán trong biểu thức chính là thứ tự thực hiện các phép toán đó. - Dạng hậu tố không phải là dạng biểu diễn cú pháp phổ biến cho biểu thức trong các ngôn ngữ nhưng nó lại có ý nghĩa quan trọng trong việc biểu diễn biểu thức trong thời gian thực thi. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 23Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: các biến, các phép toán có hai toán hạng (+, -, *, /) và các dấu ngoặc trái hay phải. Để đánh dấu bắt đầu và kết thúc một biểu thức ta chèn thêm ký tự “$” trước ký tự đầu tiên và sau ký tự cuối cùng. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 24Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Giải thuật Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ 2. Tùy theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau: - Ký tự bắt đầu “$” luôn được đẩy vào stack - Các ký tự là biến luôn được ghi ra, không cất vào stack - Các ký tự được đọc +, -, *, /, (, ) và ký tự kết thúc “$” có tác vụ được thực hiện theo mã số tác vụ được mô tả trong bảng sau: 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 25Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Ký tự được đọc $ + - * / ( ) Ký tự tại đỉnh stack $ 4 1 1 1 1 1 5 + 2 2 2 1 1 1 2 - 2 2 2 1 1 1 2 * 2 2 2 2 2 1 2 / 2 2 2 2 2 1 2 ( 5 1 1 1 1 1 3 16/11/2008 26Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Các tác vụ có mã số là: 1. Push 2. Pop và ghi ra 3. Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không ghi ra) 4. Giải thuật kết thúc. Kết quả biểu thức được ghi ra 5. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc không được cân đối đúng. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 27Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện giữa ký tự đang đọc, nó có thể là ký tự ở lần so sánh trước hay ký tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì đạt được kết quả. Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng hậu tố Ba Lan đảo. Tuy nhiên, thứ tự của các toán tử là khác nhau. Các toán tử xuất hiện trong dạng hậu tố Ba Lan đảo thì theo thứ tự mà chúng thực sự được thực thi trong việc định giá biểu thức. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 28Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step Biểu thức được đọc Ký tự đang đọc Ký tự ở đỉnh stack Tác vụ Kết quả 1 $(8+2*5)/(1+3*2-4)$ $ Push 2 (8+2*5)/(1+3*2-4)$ ( $ Push 3 8+2*5)/(1+3*2-4)$ 8 ( 8 4 +2*5)/(1+3*2-4)$ + ( Push 5 2*5)/(1+3*2-4)$ 2 + 82 16/11/2008 29Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step Biểu thức được đọc Ký tự đang đọc Ký tự ở đỉnh stack Tác vụ Kết quả 6 *5)/(1+3*2-4)$ * + Push 7 5)/(1+3*2-4)$ 5 * 825 8 )/(1+3*2-4)$ ) * Pop và ghi ra 825* 9 + Pop và ghi ra 825*+ 10 ( Pop và xóa 16/11/2008 30Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step Biểu thức được đọc Ký tự đang đọc Ký tự ở đỉnh stack Tác vụ Kết quả 11 /(1+3*2-4)$ / $ Push 12 (1+3*2-4)$ ( / Push 13 1+3*2-4)$ 1 ( 825*+1 14 +3*2-4)$ + ( Push 15 3*2-4)$ 3 + 825*+13 16/11/2008 31Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step Biểu thức được đọc Ký tự đang đọc Ký tự ở đỉnh stack Tác vụ Kết quả 16 *2-4)$ * + Push 17 2-4)$ 2 * 825*+132 18 -4)$ - * Pop 825*+132* 19 + Pop 825*+132*+ 20 ( Push 16/11/2008 32Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step Biểu thức được đọc Ký tự đang đọc Ký tự ở đỉnh stack Tác vụ Kết quả 21 4)$ 4 - 825*+132*+4 22 )$ ) - Pop 825*+132*+4- 23 $ $ ( Pop và xóa 24 $ / Pop 825*+132*+4-/ 25 $ Stop 16/11/2008 33Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Hoạt động của stack tương ứng là: 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan $ 1 ( $ 2 ( $ 3 + ( $ 4 + ( $ 5 * + ( $ 6 * + ( $ 7 + ( $ 8 16/11/2008 34Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Hoạt động của stack tương ứng là: 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan ( $ 9 $ 10 / $ 11 ( / $ 12 ( / $ 13 + ( / $ 14 + ( / $ 15 * + ( / $ 16 16/11/2008 35Cấu trúc dữ liệu 1 Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Hoạt động của stack tương ứng là: 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan * + ( / $ 17 + ( / $ 18 ( / $ 19 - ( / $ 20 - ( / $ 21 ( / $ 22 / $ 23 $ 24 25 16/11/2008 36Cấu trúc dữ liệu 1 Định giá biểu thức dạng hậu tố Ba Lan đảo Giải thuật: B1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan đảo, bắt đầu từ bên trái cho tới khi gặp một toán tử. B2: Ghi toán tử và hai toán hạng ngay sát bên trái ra ngoài B3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một khoảng trống. B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi kết quả vào khoảng trống. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 37Cấu trúc dữ liệu 1 Định giá biểu thức dạng hậu tố Ba Lan đảo Giải thuật: B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi kết quả vào khoảng trống. B5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải thuật kết thúc, ngược lại thì thực hiện lại bước 1. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 38Cấu trúc dữ liệu 1 Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/ 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step Biểu thức được định giá Toán tử cự trái c Toán hạng bên trái Toán hạng bên phải Kết quả phép toán Biểu thức mới sau khi thực hiện phép toán 1 825*+132*+4-/ * 2 5 10 8 10 + 132*+4-/ 2 8 10 + 132*+4-/ + 8 10 18 18 132*+4-/ 3 18 132*+4-/ * 3 2 6 18 1 6 +4-/ 4 18 1 6 +4-/ + 1 6 7 18 7 4-/ 5 18 7 4-/ - 7 4 3 18 3 / 6 18 3 / / 18 3 6 6 16/11/2008 39Cấu trúc dữ liệu 1 Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Giải thuật Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán tử. Thực hiện lần lượt các bước sau: B1: Đặt k=1 B2: Xét ký tự thứ k: - Nếu ký tự đó là biến, cất vào stack - Nếu ký tự đó là toán tử, lần lượt lấy từ đỉnh của stack hai toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái), thực hiện phép toán và đẩy ngược kết quả lên stack. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 40Cấu trúc dữ liệu 1 Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Giải thuật B3: Nếu k=n, giải thuật kết thúc, kết quả nằm trong stack Ngược lại, k ++, thực hiện lại B2. Lưu ý: Con số trên đỉnh stack là toán hạng bên phải, không phải là toán hạng bên trái. Điều này quan trọng đối với các phép toán trừ và phép toán chia vì thứ tự của các toán hạng này là có ý nghĩa (không giống như phép cộng và phép nhân). 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 16/11/2008 41Cấu trúc dữ liệu 1 Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/ Các bước thực hiện trong tiến trình định giá biểu thức: 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step k Dạng biểu thức còn lại sau khi đọc Tác vụ thực hiện 1 8 2 5*+ 1 3 2*+ 4 -/ Push 8 2 2 5*+ 1 3 2*+ 4 -/ Push 2 3 5*+ 1 3 2*+ 4 -/ Push 5 4 *+ 1 3 2*+ 4 -/ Pop 5, pop 2, nhân 2*5=10, push 10 16/11/2008 42Cấu trúc dữ liệu 1 Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/ 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step k Dạng biểu thức còn lại sau khi đọc Tác vụ thực hiện 5 + 1 3 2*+ 4 -/ Pop 10, pop 8, cộng 8+10=18, push 18 6 1 3 2*+ 4 -/ Push 1 7 3 2*+ 4 -/ Push 3 8 2*+ 4 -/ Push 2 9 *+ 4 -/ Pop 2, pop 3, nhân 3*2=6, push 6 16/11/2008 43Cấu trúc dữ liệu 1 Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/ 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Step k Dạng biểu thức còn lại sau khi đọc Tác vụ thực hiện 10 + 4 -/ Pop 6, pop 1, cộng 1+6=7, push 7 11 4 -/ Push 4 12 -/ Pop 4, pop 7, trừ 7-4=3, push 3 13 / Pop 3, pop 18, chia 18/3=6, push 6 16/11/2008 44Cấu trúc dữ liệu 1 Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Hoạt động của stack tương ứng với các bước của k 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 8 1 2 8 2 5 2 8 3 - 10 8 4 - 18 5 1 18 6 3 1 18 7 2 3 1 18 8 6 1 18 9 7 18 10 4 7 18 11 3 18 12 6 13 16/11/2008 45Cấu trúc dữ liệu 1 Hàng đợi là một kiểu danh sách tuyến tính đặc biệt mà phép thêm vào (PUSH) ở cuối danh sách, qua con trỏ First, và phép lấy ra (POP) ở đầu danh sách, qua con trỏ Last. Do đó, hàng đợi hoạt động theo nguyên tắc “vào trước ra trước” FIFO (First in – First out). Hàng đợi có thể rỗng hoặc chứa một số phần tử. 3.4. Stack và Queue 3.4.2. Queue Định nghĩa 16/11/2008 46Cấu trúc dữ liệu 1 Biểu diễn queue bằng mảng với các biến first (đầu hàng đợi) và last (cuối hàng đợi) hoạt động theo nguyên tắc sau: Khi first < last thì queue rỗng - Hàm thêm một phần tử vào queue: Push với biến last theo chế độ tăng trước. - Hàm lấy một phần tử ra khỏi queue: Pop với biến first theo chế độ tăng sau. 3.4. Stack và Queue Định nghĩa 3.4.2. Queue 16/11/2008 47Cấu trúc dữ liệu 1 3.4. Stack và Queue Định nghĩa 1 2 3 output first last input 3.4.2. Queue 16/11/2008 48Cấu trúc dữ liệu 1 Các thao tác chính: - isEmpty: Kiểm tra rỗng - isFull: Kiểm tra đầy - Push: Thêm 1 phần tử - Pop: Lấy ra 1 phần tử 3.4. Stack và Queue Cài đặt 3.4.2. Queue 16/11/2008 49Cấu trúc dữ liệu 1 struct Queue { int data[100]; int first, last; }; void Initial(Queue &q) { q.first = 0; q.last=-1; } 3.4. Stack và Queue Cài đặt 3.4.2. Queue 16/11/2008 50Cấu trúc dữ liệu 1 int isEmpty(Queue q) { return (q.last<q.first); } int isFull(Queue q) { return (q.last>=99); } 3.4. Stack và Queue Cài đặt 3.4.2. Queue 16/11/2008 51Cấu trúc dữ liệu 1 void Push(Queue &q,int k) { if (isFull(q)) return; q.data[++q.last]=k; } 3.4. Stack và Queue Cài đặt 3.4.2. Queue 16/11/2008 52Cấu trúc dữ liệu 1 int Pop(Queue &q) { if (isEmpty(q)) return -1; return q.data[q.first++]; } 3.4. Stack và Queue 3.4.2. Queue Cài đặt 17/11/2008 53Cấu trúc dữ liệu 1 Hàng đợi có thể được sử dụng trong một số bài toán: - Bài toán “sản xuất và tiêu thụ” - Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý) - Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều hành,trình biên dịch), hàng đợi các tiến trình chờ được xử lý. 3.4. Stack và Queue 3.4.2. Queue Ứng dụng