Queue, hàng đợi - Cài đặt và ứng dụng trên C

[PoPoPoPo]

Queue là danh sách cấu trúc tuyến tính ngược với Stack, tuân theo cơ chế FIFO ( vào trước thì ra trước- thế mới công bằng).
Các thao tác trên Queue, dựa trên bài người sản xuất- người tiêu dùng.
NSX sản xuất ra hàng hóa và chất vào kho thứ tự, NTD lấy hàng hóa ra theo thứ tự của queue, cái gì chất vào trước thì tiêu thụ trước(nếu không nó hỏng)

1.Định nghĩa

typedef struct{    int mahang;    char ten[20];} hang;typedef struct {    int front, rear;    hang node[MAX];} queue;

2.Khởi tạo

void Initialize ( queue *pq){    pq->front = pq->rear = MAX -1;}

3.Kiểm tra tính rỗng.

int Empty(queue *pq){    if (pq->front==pq->rear)        return(TRUE);    return(FALSE);}

4.Thêm phần tử

void Insert(queue *pq, hang x){    if (pq->rear==MAX-1 )        pq->rear=0;    else        (pq->rear)++;    if (pq->rear ==pq->front){        printf("\n Queue full");        delay(2000);return;    }    else        pq->node[pq->rear]=x;}

5.Loại bỏ 1 ptử

hang    Remove(queue *pq){    if (Empty(pq)){        printf("\n Queue Empty");        delay(2000);    }    else {        if (pq->front ==MAX-1)            pq->front=0;        else            pq->front++;    }    return(pq->node[pq->front]);}  Thao t¸c Traver: DuyÖt tÊt c¶ c¸c nót trong hµng ®îi.void Traver( queue *pq){    int i;    if(Empty(pq)){        printf("\n Queue Empty");        return;    }    if (pq->front ==MAX-1)        i=0;    else        i = pq->front+1;    while (i!=pq->rear){        printf("\n %11d % 15s", pq->node[i].mahang, pq->node[i].ten);        if(i==MAX-1)            i=0;        else            i++;    }    printf("\n %11d % 15s", pq->node[i].mahang, pq->node[i].ten);}

[PoPoPoPo]

Sau đây là bài hoàn chỉnh:

#include    <stdio.h>#include    <stdlib.h>#include    <conio.h>#include    <dos.h>#include    <string.h>#include    <math.h>#define MAX 50#define TRUE    1#define FALSE   0typedef struct{    int mahang;    char ten[20];} hang;typedef struct {    int front, rear;    hang node[MAX];} queue;/* nguyen mau cua ham*/void    Initialize( queue *pq);int Empty(queue *);void Insert(queue *, hang x);hang  Remove(queue *);void    Traver(queue *); /* Mo ta ham */void Initialize ( queue *pq){    pq->front = pq->rear = MAX -1;}int Empty(queue *pq){    if (pq->front==pq->rear)        return(TRUE);    return(FALSE);}void Insert(queue *pq, hang x){    if (pq->rear==MAX-1 )        pq->rear=0;    else        (pq->rear)++;    if (pq->rear ==pq->front){        printf("\n Queue full");        delay(2000);return;    }    else        pq->node[pq->rear]=x;}hang    Remove(queue *pq){    if (Empty(pq)){        printf("\n Queue Empty");        delay(2000);    }    else {        if (pq->front ==MAX-1)            pq->front=0;        else            pq->front++;    }    return(pq->node[pq->front]);}void Traver( queue *pq){    int i;    if(Empty(pq)){        printf("\n Queue Empty");        return;    }    if (pq->front ==MAX-1)        i=0;    else        i = pq->front+1;    while (i!=pq->rear){        printf("\n %11d % 15s", pq->node[i].mahang, pq->node[i].ten);        if(i==MAX-1)            i=0;        else            i++;    }    printf("\n %11d % 15s", pq->node[i].mahang, pq->node[i].ten);} void main(void){    queue q;    char chucnang, front1; char c; hang mh;    clrscr();    Initialize(&q);    do {        clrscr();        printf("\n NGUOI SAN XUAT/ NHA TIEU DUNG");        printf("\n 1- Nhap mot mat hang");        printf("\n 2- Xuat mot mat hang");        printf("\n 3- Xem mot mat hang");        printf("\n 4- Xem hang moi nhap");        printf("\n 5- Xem tat ca");        printf("\n 6- Xuat toan bo");        printf("\n Chuc nang chon:");chucnang=getch();        switch(chucnang){            case ‘1’:printf("\n Ma mat hang:"); scanf("%d", &mh.mahang);                printf("\n Ten hang:");scanf("%s", mh.ten);                Insert(&q,mh);break;            case ‘2’:                if (!Empty(&q)){                     mh=Remove(&q);                     printf("\n %5d %20s",mh.mahang, mh.ten);                }                else {                    printf("\n Queue Empty");                    delay(1000);                }                break;            case ‘3’:                front1=(q.front==MAX-1)?0:q.front+1;                printf("\n Hang xuat");printf("\n %6d %20s",q.node[front1].mahang, q.node[front1].ten);                break;            case ‘4’:                printf("\n Hang moi nhap");printf("\n %5d %20s", q.node[q.rear].mahang,q.node[q.rear].ten);                break;            case ‘5’:                printf("\ Hang trong kho");                Traverse(&q);delay(2000);break;        }    } while(chucnang!=’0’);}

[PoPoPoPo]

Giả sử cùng 1 lúc CPU của chúng ta cần giải quyết nhiều tiến trình cùng 1 lúc.
Nhưng thực tế không thể giải quyết cùng 1 lúc, mà cũng phải xử lý theo cơ chế hàng đợi.
Sau đây là bài hoàn chỉnh:

#include    <stdio.h>#include    <stdlib.h>#include    <conio.h>#include    <dos.h>#include    <string.h>#include    <math.h>#define MAX 100#define TRUE    1#define FALSE   0typedef struct {    int rear;    int node[MAX];} pqueue;void Pqinitialize(pqueue *pq){    pq->rear=-1;}int Pqempty(pqueue *pq){    if (pq->rear==-1)        return(TRUE);    return(FALSE);}int Pqueuesize(pqueue *pq){    return(pq->rear+1);}void Pqinsert(pqueue *pq, int x){    int i, j;    if (pq->rear ==MAX - 1){        printf("\n Queue full");        delay(2000); return;    }    for (i=0;i<Pqueuesize(pq) && pq->node[i]>=x; i++);    for(j=Pqueuesize(pq);j>i;j--)        pq->node[j]=pq->node[j-1];    pq->node[i]=x;    pq->rear++;}int Pqremove(pqueue *pq){    int x, i;    if (Pqempty(pq)){        printf("\n Queue full");        delay(2000); return(x);    }    else {        x=pq->node[0];        for (i=0;i<pq->rear;i++)            pq->node[i]=pq->node[i+1]++;        pq->rear--;    }    return(x);}void Pqtraver(pqueue *pq){    int i;    if (Pqempty(pq)) {        printf("\n Queue Empty");        delay(2000); return;    }    for (i=0;i<=pq->rear;i++)        printf("%5d",pq->node[i]);}void main(void){    pqueue *pq;    int douutien, chucnang;char c;    Pqinitialize(pq);    do {        clrscr();        printf("\n QUEUE PRIORITY");        printf("\n 1- Them nut uu tien");        printf("\n 2- Xoa nut uu tien");        printf("\n 3- Xoa hang doi");        printf("\n 4- Duyet hang doi");        printf("\n 0- Ket thuc");        chucnang=getch();        switch(chucnang){            case ‘1’:                printf("\n Do uu tien:");scanf("%d",&douutien);                Pqinsert(pq, douutien);                break;            case ‘2’:                Pqremove(pq); break;            case ‘3’:                Pqinitialize(pq); break;            case ‘4’:Pqtraver(pq); delay(2000); break;        }    } while(chucnang!=’0’);}

[fithou91192]

4.Thêm phần tử

void Insert(queue *pq, hang x){    if (pq->rear==MAX-1 )        pq->rear=0;    else        (pq->rear)++;    if (pq->rear ==pq->front){        printf("\n Queue full");        delay(2000);return;    }    else        pq->node[pq->rear]=x;}

em không hiẻu anh cho delay vào làm gì vậy ạ

[aydada]

typedef struct {    int front, rear;    hang node[MAX];} queue;

bạn để ý lại cái khai báo struct này
khai báo hang node[MAX] không phải là đã cố định số lượng phần tử của queue à

[naknah]

Ủa mà bạn dùng trình biên dịch gì để viết C vậy?

[ktpm489]

void Insert(queue *pq, hang x){
if (pq->rear==MAX-1 )
pq->rear=0;
else
(pq->rear)++;
if (pq->rear ==pq->front){
printf("\n Queue full");
delay(2000);return;
}
else
pq->node[pq->rear]=x;//dòng này nghĩa là gì bạn
}
cho mình hỏi pq->rear,pq->front là gì

[hoangtu_codon_14]

Queue (hàng đợi) thực chất của chỉ là 1 mảng nhưng hoạt động theo nguyên tắc FIFO (First In First Out):

//Enqueue : dua phan tu vo hang doi
void Enqueue(int a[],int &n,int x)
{
	a[n] =x;
	n++;
}

// Dequeue : lay phan tu ra khoi hang doi
int Dequeue(int a[],int &n)
{
	if(n==0)
		return -1;
	int x=a[0];
	// lap phan tu a[0]
	for(int i=0;i<n-1;i++)
	{
		a[i] = a[i+1];
	}
	n--;
	return x;
}