队列

julyzqy 2019-12-02 原文

1、队列的定义
队列，简称队，它是一种操作受限的线性表，其限制在表的一端进行插入，另一端进行删除。可进行插入的一端称为队尾（rear）,可进行删除的一端称为队头（front）。向队中插入元素叫入队，新元素进入之后就称为新的队尾元素。从队中删除元素叫出队，元素出队后，其后继结点元素就称为新的队头元素。
2、队列的特点
队的特点就是先进先出（栈为先进后出）。排队买票，排在前面的，先拿到票，排在后面的必须等待着前面买完票，才能轮到他买票。
3、队列的存储结构
队列按存储结构可分为链队和顺序队两种。

先说一下顺序队列，如图：

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef struct
{
    int data[105];
    int front;
    int rear;
}SeqQueue;
void Init(SeqQueue *q)      //置空队列
{
    q->front=q->rear=-1;
}
int EmptyQueue(SeqQueue *q)  //判断队列是否为空
{
    if(q->front==q->rear)
        return 1;
    else
        return 0;
}
int  InQueue(SeqQueue *q,int x)  //进行入队
{
    if(q->rear==105-1)
    {
        printf("队列已经满了！\n");
        return 0;
    }
    q->rear++;
    q->data[q->rear]=x;
    return 1;
}
int OutQueue(SeqQueue *q)      //进行出队
{
    if(q->front<0)
    {
        printf("队列已经为空！\n");
        return 0;
    }
    q->front++;
    return q->data[q->front];
}
int main()
{
    SeqQueue *q;
    q=(SeqQueue *)malloc(sizeof(SeqQueue));
    for(int i=1;i<=10;i++)
    {

        InQueue(q,i);
    }
    for(int i=1;i<=10;i++)
    {
        printf("%d ",OutQueue(q));

    }
}

循环队列：

　　　　　　　　满：当队列添加元素到rear的下一个元素是front的时候，也就是转圈子要碰头了，我们就认为队列满了。(Q.rear+1)%MAXSIZE=Q.front

　　　　　　　　空：当队列删除元素到front=rear的时候，我们认为队列空了。Q.rear==Q.front,不一定为0

　　图示：

代码实现：

#include<bits/stdc++.h>
using namespace std;
#define MAX 105
typedef struct
{
    int data[MAX];
    int front;
    int rear;
}SeqQueue;
void Init(SeqQueue *q)      //置空
{
    q->front=q->rear=-1;

}
int EmptyQueue(SeqQueue *q)   //判断是否为空
{
    if(q->rear==q->front)
        return  1;
    else
        return  0;
}
int InQueue(SeqQueue *q,int x)    //进队
{
    if((q->rear+1)%MAX==q->front)
    {
        printf("循环队列已经满了！\n");
        return 0;
    }
    q->rear=(q->rear+1)%MAX;
    q->data[q->rear]=x;
    return 1;
}
int OutQueue(SeqQueue *q)     //出队
{
    if(q->rear==q->front)
    {
        printf("队已经为空！\n");
        return 0;
    }
    q->front=(q->front+1)%MAX;
    return q->data[q->front];

}
int main()
{
    SeqQueue *q;
    q=(SeqQueue *)malloc(sizeof(SeqQueue));
    for(int i=1;i<=10;i++)
    {
        InQueue(q,i);
    }
    for(int i=1;i<=10;i++)
    {
        printf("%d ",OutQueue(q));

    }
}