数据结构--队列的顺序存储_队列存储数据

系列文章目录

第五话  数据结构之队列

---

前言

     生活中到处都是队列形式，比如买票需要排队、上下飞机需要排队、递交申请表需要排队。排队是有目的地一个跟一个的队列，人类文明社会中，排队是文明的表现，是有限资源的分配方式之一，以顺序确保公平，是“先到先得”。

     从抽象层面看，凡是两端开口的容器或通道都可以看成列队，如水管、电缆、隧道、单行车道等。对于计算机来说，队列无处不在。

---

一、什么是队列？

     队列是一种“先进先出”的数据结构，即插入操作在表的一端进行，而删除操作在表的另一端进行。和日常生活中的排队是一致的，最先进入列队的一端称为对头。队列的例子在生活中比比皆是，比如一条生产线、排队购物等；在计算机的操作系统中也存在着各种队列，如资源等待队列】就绪队列等。

二、队列的基本特征

先进先出或者后进后出：最先进去的最先出来，最后进去的最后出来

三、队列的基本操作

1.定义存储结构--顺序存储

#include <stdio.h>
#include <stdlib.h>
#define maxsize 100
typedef int Elemtype;
typedef struct{
    Elemtype date[maxsize];
    int rear;
    int front;
}Queue;

2.将队列初始化 

Queue *init_queue()
{
    Queue *Q;
    Q = (Queue*)malloc(sizeof(Queue));
    Q->rear = 0;
    Q->front = 0;
    return Q;
}

3.入队操作

int pushqueue(Queue *Q,Elemtype x)
{
    if((Q->rear+1)%maxsize==Q->front){
        printf("队列已满,无法入队\n");
        return 0;//入队失败返回0
    }else{
        Q->date[Q->rear] = x;
        Q->rear = (Q->rear+1)%maxsize;
        return 1;//入队成功返回1
    }
}

4.出队操作

int popqueue(Queue *Q,Elemtype *x)
{
    if(Q->front==Q->rear){
        printf("队列已空,无法出栈\n");
        return 0;//队空时返回值为0;
    }else{
        *x = Q->date[Q->front];
        Q->front = (Q->front+1)%maxsize;
        return 1;
    }
}

5.在主函数中实现调用

int main()
{
    Queue *Q1;
    int cnt = 0;
    int i = 0;
    Elemtype x;
    Q1 = init_queue();
    printf("请输入入队的数,输入-1代表结束:\n");
    scanf("%d",&x);
    while(x!=-1){
        pushqueue(Q1,x);
        cnt++;
        scanf("%d",&x);
    }
    for(i=0;i<cnt;i++){
        popqueue(Q1,&x);
        printf("x = %d\n",x);
    }
    return 0;
}

 

---

四、总结

由于循环队列的存储特性可知，如果应用程序中使用循环队列，则必须申请一个合理的队列长度；如果无法预估所用队列的大小，则宜采用链队列。