队列——数据结构严蔚敏C语言版

队列的定义

队列(Queue):先进先出的线性表
队列是仅在队尾进行插入和队头进行删除操作的线性表

• 队头(front)：线性表的表头端,即可删除端
• 队尾(rear)：线性表的表尾端,即可插入端

由于这种队列存在假溢出现象,所以引入了循环链表解决假溢出想象

什么是假溢出可参考这篇文章

环形队列

区别环形队列是满队还是空队的两种方式

• 另设一个标志以区别队列是满队还是空队
• 少用一个元素空间
  队空的条件：Q.front == Q.rear
  队满的条件：(Q.rear+1)%MAXSIZE == Q.front

我们使用第二种方式实现

循环队列的基本操作

#include <iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 10
using namespace std;
typedef int Status;
typedef int QElemType;

typedef struct {
    
    QElemType *base;//存储空间的基地址
    int front;//头指针
    int rear;//尾指针
}SqQueue;

/*初始化队列 1、为队列分配最大容量为MAXSIZE的数组空间,base指向数组空间的首地址 2、头指针和尾指针置为0,表示队列为空 */
Status InitQueue(SqQueue &Q){
    
    Q.base = new QElemType[MAXSIZE];
    if (!Q.base) exit(OVERFLOW);//存储空间分配失败
    Q.front = Q.rear = 0;//头尾指针置零
    return OK;
}
/*队列的长度(队列中元素的个数)*/
int QueueLength(SqQueue Q){
    
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
/*循环队列入队 1、判断队列是否已满,若满则返回ERROR 2、将新元素插入到队尾 3、队尾指针加1 */
Status EnQueue(SqQueue &Q,QElemType e){
    
    if ((Q.rear+1)%MAXSIZE == Q.front) //(循环)队列满了
        return ERROR;
    Q.base[Q.rear] = e;//在队尾插入元素
    Q.rear = (Q.rear+1)%MAXSIZE;//队尾指针加1
    return OK;
}
/*循环队列出队 1、判断队列是否为空,若空则返回ERROR 2、保存队头元素 3、队头指针加1 */
Status DeQueue(SqQueue &Q,QElemType &e){
    
    if (Q.front == Q.rear)//对空
        return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAXSIZE;//对头指针加1
    return OK;
}
/*取循环队列的队头元素*/
QElemType GetHead(SqQueue Q){
    
    if (Q.front != Q.rear)
        return Q.base[Q.front];
}

int main(){
    
    SqQueue Q;
    InitQueue(Q);//初始化循环队列
    EnQueue(Q,1);//循环队列入队
    EnQueue(Q,2);
    EnQueue(Q,3);
    int length = QueueLength(Q);
    cout<<length<<endl;
    cout<<GetHead(Q)<<endl;
    int a,b,c;
    DeQueue(Q,a);//循环队列出队
    DeQueue(Q,b);
    DeQueue(Q,c);
    cout<<a<<b<<c<<endl;
    return 0;
}

链队

链队是指采用链式存储结构实现的队列。通常链队用单链表表示,一个链队显然需要两个分别指向队头和队尾的指针才能唯一确定

链队的基本操作

#include <iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 10;
using namespace std;
typedef int Status;
typedef int QElemType;

typedef struct QNode{
    
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
    
    QueuePtr front;//头指针
    QueuePtr rear;//尾指针
}LinkQueue;

/*链对的初始化 1、生成新结点作为头结点,队头和队尾指针都指向此结点 2、头节点的指针域置空 */
Status InitQueue(LinkQueue &Q){
    
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;
    return OK;
}
/*链队入队 1、为入队元素分配结点空间，用指针p指向 2、将新结点的数据与置为e 3、将新结点插入到队尾 4、修改队尾指针指向p */
Status EnQueue(LinkQueue &Q,QElemType e){
    
    QueuePtr p = new QNode;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;//修改尾指针
    Q.rear = p;
    return OK;
}
/*链队出队 1、判断队列是否为空,若空则返回ERROR 2、临时保存队头的元素空间,已备释放 3、修改队头指针指向下一个结点 4、判断出队元素是否为最后一个元素,若是则将队尾指针指向头结点 5、释放原队头元素的空间 */
Status DeQueue(LinkQueue &Q,QElemType &e){
    
    if (Q.rear == Q.front) //链队为空
        return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;//修好头指针
    if (Q.rear == p) //删除最后一个元素
        Q.rear = Q.front;
    delete p;
    return OK;
}
/*取链队的队头元素*/
QElemType GetHead(LinkQueue Q){
    
    if (Q.front != Q.rear)
        return Q.front->next->data;
}

int main(){
    
    LinkQueue Q;
    InitQueue(Q);
    EnQueue(Q,3);
    EnQueue(Q,2);
    EnQueue(Q,1);
    int a,b,c;
    DeQueue(Q,a);
    DeQueue(Q,b);
    DeQueue(Q,c);
    cout<<a<<b<<c<<endl;
    return 0;
}