1.队列的概念
队列是一种特殊的线性表,仅仅同意在队列的一端进行插入而在还有一端进行删除。
队列一般拥有队首(front指针)和队尾(rear指针)。当一个队列并未存入数据的时候,front和rear指针均指向队首。
入队的操作:rear后移,存入数据在rear指向的单元,队满不可入队,这同一时候也表明front总是指向队首元素的前驱。
出队的操作:front后移,元素出队,队空不可出队。
队列是一种特殊的线性表,仅仅同意在队列的一端进行插入而在还有一端进行删除。
队列一般拥有队首(front指针)和队尾(rear指针)。当一个队列并未存入数据的时候,front和rear指针均指向队首。
入队的操作:rear后移,存入数据在rear指向的单元,队满不可入队,这同一时候也表明front总是指向队首元素的前驱。
出队的操作:front后移,元素出队,队空不可出队。
注意:在这样的队列的实现方式下。浪费了一个单元,可是这样能够保证队满和队空是不同的条件来推断。
2.队列空和队列满
队列空:front = rear
队列满:rear的下一个单元就是front
3.队列的数组实现方式
#include <stdio.h>
#include <malloc.h>
typedef struct sq
{
int maxsize;
int front, rear;
int *quence;
}Qs;
void init_quence(Qs *s, int ms) /*初始化队列*/
{
s->maxsize = ms;
s->quence = (int *)malloc(ms*sizeof(int));
s->front = s->rear = 0;
}
void in_quence(Qs *s, int val) /*入队函数*/
{
if((s->rear+1)%s->maxsize == s->front)
{
printf("Quence is full.\n");
return;
}
s->rear = (s->rear+1)%s->maxsize;
s->quence[s->rear] = val;
}
int out_quence(Qs *s) /*出队函数*/
{
if(s->rear != s->front)
{
s->front = (s->front+1)%s->maxsize;
return s->quence[s->front];
}
}
void print_quence(Qs *s) /*打印队列中元素*/
{
int i;
i = s->front;
if(s->rear == s->front)
return;
do
{
printf("%d ", s->quence[(i+1)%s->maxsize]);
i = (i+1)%s->maxsize;
}while(i != s->rear);
}
void clear_quence(Qs *s) /*清除队列*/
{
free(s->quence);
s->quence = 0;
s->maxsize = 0;
s->front = s->rear = 0;
}
int count_quence(Qs *s) /*统计队列个数*/
{
int i, count = 0;
i = s->front;
if(s->rear == s->front)
return 0;
do
{
count ++;
i = (i+1)%s->maxsize;
}while(i != s->rear);
return count;
}
int main()
{
Qs s;
int i;
int dat[7] = {1, 2, 3, 4, 5, 6, 7};
init_quence(&s, 7);
for(i = 0; i < 7; i++)
{
in_quence(&s, dat[i]);
printf("Quence number is: %d. ", count_quence(&s));
print_quence(&s);
printf("\n");
}
printf("Out quence number is: %d.\n", out_quence(&s));
print_quence(&s);
clear_quence(&s);
return 0;
}
程序执行截图: