初学队列Ⅰ

初学队列Ⅰ


队列(queue)是一种先入先出(First In First Out, FIFO)的线性表。

队列 (queue) 是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列的结构示意

队列的顺序储存(循环队列)

用C语言表示大概是这样的:

1
2
3
4
5
6
struct queue
{
int data[Max_size];
int front; //表示头指针
int rear; //尾指针
};

初始化队列

务必记得初始化!!

1
2
3
4
5
6
void init_queue(struct queue *q)
{
q->front = 0;
q->rear = 0;
return;
}

入队列操作

队列满的判断条件是(q->rear + 1)%Max_size == q->front

1
2
3
4
5
6
7
8
int push(struct queue *q,int num)
{
if((q->rear+1)%Max_size == q->front) //队列满
return -1;
q->data[q->rear] = num;
q->rear = (q->rear+1)%Max_size;
return 0;
}

出队列操作

变量 t 用来返回pop出来的元素。

1
2
3
4
5
6
7
8
int pop(struct queue *q,int *e)
{
if(q->front == q->rear) //队列空
return -1;
*e = q->data[q->front];
q->front = (q->front+1)%Max_size;
return 0;
}

创建一个队列

1
2
3
4
5
6
7
8
9
10
void create_queue(struct queue *q,int n)
{
int i,t;
for(i=0;i<n;i++)
{
scanf("%d",&t);
push(q,t);
}
return;
}

遍历输出队列内的元素

1
2
3
4
5
6
7
8
9
10
11
void print(struct queue *q)
{
while(1)
{
int e;
if(pop(q,&e)==-1) break;
printf("%d ",e);
}
printf("\n");
return;
}