隊列的多種C語言實現

標題：隊列的多種C語言實現

內容：隊列是先進先出（FIFO）的線性表，C語言中可以使用數組、全局變量、引用實現隊列。

作者：MilkCu

概念

隊列的操作

隊列是受限制的線性表，只允許在隊尾（tail）插入、對頭（head）刪除。

隊列的操作方式與堆棧類似，唯一的區別在於隊列只允許新數據在後端進行添加。

隊列的屬性

以隊列q為例。

q.head指向隊頭元素；
q.tail指向下一個新元素將要插入的位置。

在隊列中，位置1緊鄰在n的後面形成一個環序。

隊列的狀態

當q.head = q.tail時，隊列為空，
初始時有q.head = q.tail = 1 ；
當q.head = q.tail + 1時，隊列是滿的 。

數組實現

利用數組q.key[n]實現一個最多容納n-1個元素的隊列。

# include <stdio.h>
# define M 100
typedef struct queue {
int head;
int tail;
int key[M];
int length;
} queue;
queue q;
void enqueue(int x);
int dequeue(void);
int main(void)
{
q.head = q.tail = 1;
q.length = 98;
enqueue(1);
enqueue(3);
enqueue(5);
enqueue(7);
printf("%d\n", dequeue());
printf("%d\n", dequeue());
printf("%d\n", dequeue());
printf("\t%d\n", q.head);
printf("%d\n", dequeue());
}
void enqueue(int x)
{
q.key[q.tail] = x;
if(q.tail == q.length) {
q.tail = 1;
} else {
q.tail++;
}
}
int dequeue(void)
{
int x;

x = q.key[q.head];
if(q.head == q.length) {
q.head = 1;
} else {
q.head++;
}
return x;
}

全局變量實現

全局變量也挺方便的，只是注意不要和局部變量重名而被取代了。

# include <stdio.h>
# define M 100
typedef struct queue {
int head;
int tail;
int key[M];
int length;
} queue;

void enqueue(queue * qp, int x);
int dequeue(queue * qp);
int main(void)
{
queue q;
q.head = q.tail = 1;
q.length = 98;
enqueue(&q, 1);
enqueue(&q, 3);
enqueue(&q, 5);
enqueue(&q, 7);
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
}
void enqueue(queue * pq, int x)
{
pq -> key[pq -> tail] = x;
if(pq -> tail == pq -> length) {
pq -> tail = 1;
} else {
pq -> tail++;
}
}
int dequeue(queue * pq)
{
int x;

x = pq -> key[pq -> head];
if(pq -> head == pq -> length) {
pq -> head = 1;
} else {
pq -> head++;
}
return x;
}