Danh sách tuyến tính kiểu hàng đợi

Hàng đợi là một vật chứa (container) các đối tượng làm việc theo cơ chế FIFO (First In First Out) nghĩa là việc thêm một đối tượng vào hàng đợi hoặc lấy một đối tượng ra khỏi hàng đợi được thực hiện theo cơ chế "Vào trước ra trước".

Các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi.

Thao tác thêm một đối tượng vào hàng đợi và lấy một đối tượng ra khỏi hàng đợi lần lượt được gọi là "enqueue" và "dequeue".

Việc thêm một đối tượng vào hàng đợi luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.

Ta hình dung nguyên tắc hoạt động của Queue như sau:

Trong tin học, CTDL hàng đợi có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím, .

Ta có thể định nghĩa CTDL hàng đợi như sau: hàng đợi là một CTDL trừu tượng (ADT) tuyến tính. Tương tự như stack, hàng đợi hỗ trợ các thao tác:

EnQueue(o): Thêm đối tượng o vào cuối hàng đợi

DeQueue(): Lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.

IsEmpty(): Kiểm tra xem hàng đợi có rỗng không.

Front(): Trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.

Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở 2 phía khác nhau của hàng đợi do đó hoạt động của hàng đợi được thực hiện theo nguyên tắc FIFO (First In First Out - vào trước ra trước).

Cũng như stack, ta có thể dùng cấu trúc mảng 1 chiều hoặc cấu trúc danh sách liên kết để biểu diễn cấu trúc hàng đợi.

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ụ (ứng dụng trong các hệ điều hành song song).

Bộ đệm (ví dụ: 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ÐH, trình biên dịch), hàng đượi các tiến trình chờ được xử lý, ..

Một số ví dụ:

Chuong trinh quan ly kho

Mat hang nao nhap kho truoc se duoc xuat kho truoc

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define MAXQUEUE 100

#define TRUE 1

#define FALSE 0

// Khai bao cau truc mathang

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)

{

return((pq->front == pq->rear) ? TRUE : 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(empty(pq))

printf("kho khong con hang");

else

{

if(pq->front == MAXQUEUE-1)

pq->front = 0;

else

(pq->front)++;

return(pq->nodes[pq->front]);

}

}

// Tac vu traverse: duyet kho hang tu front toi rear

void traverse(struct queue *pq)

{

int i;

if(empty(pq))

{

printf(" Kho khong con hang");

return;

}

if(pq->front == MAXQUEUE-1)

i = 0;

else

i = pq->front+1;

// vong lap in cac nut tu front den nut ke cuoi

while(i != pq->rear)

{

printf(" %11d%15s", pq->nodes[i].mamh, pq->nodes[i].tenmh);

if(i == MAXQUEUE-1)

i = 0;

else

i++;

}

// in nut cuoi (nut tai rear)

printf(" %11d%15s", pq->nodes[i].mamh, pq->nodes[i].tenmh);

}

// chuong trinh chinh

void main(void)

{

struct queue q;

int chucnang, front1;

char c;

mathang mh;

clrscr();

// khoi tao queue

initialize(&q);

do

{

printf(" CHUONG TRINH QUAN LY KHO");

printf(" (NHAP TRUOC - XUAT TRUOC)");

printf(" Cac chuc nang cua chuong trinh: ");

printf(" 1: Nhap mot mat hang ");

printf(" 2: Xuat mot mat hang ");

printf(" 3: Xem mat hang chuan bi xuat ");

printf(" 4: Xem mat hang moi nhap ");

printf(" 5: Xem cac mat hang co trong kho ");

printf(" 6: Xuat toan bo kho hang ");

printf(" 0: Ket thuc chuong trinh ");

printf("Chuc nang ban chon: ");

scanf("%d", &chucnang);

switch(chucnang)

{

case 1:

{

printf(" Ma mat hang: ");

scanf("%d", &mh.mamh);

printf("Ten mat hang: ");

scanf("%s", &mh.tenmh);

insert(&q, mh);

break;

}

case 2:

{

if(!empty(&q))

{

mh = remove(&q);

printf(" Mat hang xuat: Ma:%d Ten:%s", mh.mamh, mh.tenmh);

}

else

printf(" Kho khong con hang");

break;

}

case 3:

{

front1 = (q.front == MAXQUEUE-1 ? 0 : q.front+1);

printf(" Mat hang chuan bi xuat: Ma:%d Ten:%s",

q.nodes[front1].mamh, q.nodes[front1].tenmh);

break;

}

case 4:

{

printf(" Mat hang moi nhap: Ma:%d Ten:%s",

q.nodes[q.rear].mamh, q.nodes[q.rear].tenmh);

break;

}

case 5:

{

printf(" Cac mat hang co trong kho:");

printf(" %11s%15s", "MA MAT HANG", " TEN MAT HANG");

traverse(&q);

break;

}

case 6: // xoa toan bo queue (khoi dong queue)

{

printf(" Ban co chac khong (c/k): ");

c = getche();

if(c == 'c' || c == 'C')

initialize(&q);

break;

}

}

} while(chucnang != 0);

}