队列是受限制的线性表,只允许在队尾(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;
}