隊列的多種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;
}