基本操作	操作函数	备注
初始化	InitQueue(&Q)	初始化一个空队列Q
判空	QueueEmpty(Q)	若队空返回true，否则返回false
进队	EnQueue（&Q,x）	进队，若队列Q未满，则将x加入成为队尾
出队	DeQueue（&Q）	出队，若队列Q非空，则删除队头元素，并用x返回
读队头元素	GetHead（S,&x）	读队头元素，若队列Q非空，把队头元素赋值给x

二、队列的顺序存储结构

（一）队列的顺序存储

分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针和队尾指针

队头指针指向队头元素，队尾指针指向队尾元素的下一个位置


#define MaxSize 50                    //定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];           //存放队列元素
    int front,rear;                   //队头指针和队尾指针
}SqQueue;

初始状态：Q.front==Q.rear==0

进队操作：先送值到队尾元素，再将队尾指针+1

出队操作：先取队头元素，再将队头指针+1

队列中元素数量 = 队尾指针 - 队头指针

Q.rear == MaxSize不能作为队满条件，比如上图情况（e）和（d），实际上队列中是有空位置的，这是一种假溢出，也就无法入队了

（二）循环队列

1.循环队列的定义

顺序队列存在假溢出的缺点，因此引入循环队列的概念，把存储队列元素从逻辑上视为一个环，物理存储上实际还是个数组

初始时：Q.front=Q.rear=0
队首指针进1：Q.front=（Q.front+1）%MaxSize
队尾指针进1：Q.rear = （Q.rear+1）%MaxSize
出队入队时：指针都按顺时针方向进1

队空条件是Q.front = Q.rear

2.循环队列队满条件

但是由于队尾指针指向的会是队尾元素的下一个位置，也就是新元素要进来的位置，所以也可能会出现Q.front = Q.rear的情况

有三种办法可以解决这个情况

（1）空出一个单元来区分

这个时候队满条件为：（Q.rear+1）%MaxSize = =Q.front

队列中元素数量为（Q.rear - Q.front + Maxsize）% Maxsize

（2）类型中增设表示元素个数的数据成员

队空条件Q.size == 0，队满条件 Q.size = MaxSize - 1


#define MaxSize 50                    //定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];           //存放队列元素
    int front,rear;                   //队头指针和队尾指针
    int size;                          //队列内元素个数
}SqQueue;

（3）类型中增设tag数据成员

初始化tag为0，进队操作时tag置为1，出队时tag置为0

当Q.front == Q.rear时，看tag的值，为1说明是因为进队导致的，说明是队满了

为0说明是出队导致的，说明是队空了


#define MaxSize 50                    //定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];           //存放队列元素
    int front,rear;                   //队头指针和队尾指针
    int tag;                          //表示上次的操作类型
}SqQueue;

（三）循环队列的操作

1.初始化


#define MaxSize 50                    //定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];           //存放队列元素
    int front,rear;                   //队头指针和队尾指针
}SqQueue;
 
void InitQueue(SqQueue &Q)
{
    Q.rear = Q.front = 0;
}
 
int main()
{
    SqQueue Q;
    InitQueue(Q);
}

2.判队空


#define MaxSize 50                    //定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];           //存放队列元素
    int front,rear;                   //队头指针和队尾指针
}SqQueue;
 
bool QueueEmpty(SqQueue &Q)
{
    if(Q.rear = Q.front)
        return true;
    else
        return false;
}
 
int main()
{
    SqQueue Q;
    if(QueueEmpty(Q))
        print("Empty!");
}

3.入队


#define MaxSize 50                            //定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];                   //存放队列元素
    int front,rear;                           //队头指针和队尾指针
}SqQueue;
 
bool EnQueue(SqQueue &Q,Elemtype x)
{
    if((Q.rear + 1) % MaxSize == Q.front)     //很明显，这个是空了一个单元的循环队列
        return false
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear+1) % MaxSize;
    return true
         
}
 
int main()
{
    SqQueue Q;
    EnQueue(Q);
}

4.出队


#define MaxSize 50                            //定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];                   //存放队列元素
    int front,rear;                           //队头指针和队尾指针
}SqQueue;
 
bool DeQueue(SqQueue &Q,Elemtype x)
{
    if(Q.rear == Q.front)     
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true
         
}
 
int main()
{
    SqQueue Q;
    DeQueue(Q);
}

三、队列的链式存储结构

（一）队列的链式存储定义

队列的链式表示称为链队列，实际上是一个带有队头指针和队尾指针的单链表，也就是带头指针和尾指针的单链表

代码可描述为


typedef struct                        //链队列的节点
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
 
typedef sturct                        //链式队列
{
    LinkNode *front,*rear;
}*LinkQueue;

一般情况下，链队列都设置为带头结点的

（二）链式队列的基本操作

1.初始化


typedef struct                        //链队列的节点
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
 
typedef sturct                        //链式队列
{
    LinkNode *front,*rear;
}*LinkQueue;
 
void InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = Null;
}
 
int main()
{
    LinkQueue Q;
    InitQueue(Q);
}

2.判队空


typedef struct                        //链队列的节点
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
 
typedef sturct                        //链式队列
{
    LinkNode *front,*rear;
}*LinkQueue;
 
bool QueueEmpty(LinkQueue &Q)
{
    if(Q.front == Q.rear)
        return ture;
    elses
        return false;
}
 
int main()
{
    LinkQueue Q;
    QueueEmpty(Q);
}

3.入队


typedef struct                        //链队列的节点
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
 
typedef sturct                        //链式队列
{
    LinkNode *front,*rear;
}*LinkQueue;
 
void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s;
    s = (LinkNode *)malloc(sizeof(LinkNode));
    s.data = x;
    s->netx = Null;
    Q.rear->next = s;
    Q.rear = s;
}
 
int main()
{
    LinkQueue Q;
    Elemtype x;
    EnQueue(Q,x);
}

4.出队

如果删除的是最后一个结点，那么要再多一次判断


typedef struct                        //链队列的节点
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
 
typedef sturct                        //链式队列
{
    LinkNode *front,*rear;
}*LinkQueue;
 
bool DeQueue(LinkQueue &Q,ElemType x)
{
    if(Q.front == Q.rear)
        return false;
    else
    {
        LinkNode * = Q.front->next;
        x = tmp->data;
        Q.front->next = tmp->next;
        if(Q.rear == tmp)
            Q.rear ==Q.front;
        free(tmp); 
        return true
    }
}
 
int main()
{
    LinkQueue Q;
    Elemtype x;
    DeQueue(Q,x);
}

四、双端队列

允许两端都可以入队和出队操作的队列，队列两端分别称为前端和后端，两端都可以入队和出队

输入受限的双端队列：

输出受限的双端队列：

五、经典例题

（一）选择题

1.在用单链表实现队列时，队头设在链表的（）位置

A.链头 B.链尾 C.链中 D.以上都可以

由于在队头做出队操作，为了便于删除队头元素，故总是选择链头作为队头，不能链中

2.若以1,2,3,4作为双端队列的输入序列，则既不能输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是（）

A.1、2、3、4 B.4、1、3、2 C.4、2、3、1 D.4、2、1、3

这个直接记答案了，硬带也能求出，比较耗时，选C

（二）应用题

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/425631

数据结构第三章——队列_队列指针

一、队列的基本概念

（一）队列的定义

（二） 队列常见的基本操作

二、队列的顺序存储结构

（一）队列的顺序存储

（二）循环队列

1.循环队列的定义

2.循环队列队满条件

（三）循环队列的操作

1.初始化

2.判队空

3.入队

4.出队

三、队列的链式存储结构

（一）队列的链式存储定义

（二）链式队列的基本操作

1.初始化

2.判队空

3.入队

4.出队

四、双端队列

五、经典例题

（一）选择题

（二）应用题

（二）队列常见的基本操作