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

队列的定义环形队列循环队列的基本操作链队链队的基本操作

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

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

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

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

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

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

我们使用第二种方式实现

#include 
#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;


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;
}

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;
}

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< 
链队 
链队是指采用链式存储结构实现的队列。通常链队用单链表表示,一个链队显然需要两个分别指向队头和队尾的指针才能唯一确定
 
 
链队的基本操作 
 
#include 
#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;


Status InitQueue(linkQueue &Q){
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;
    return OK;
}

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;
}

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<