学习数据结构--第三章:栈和队列(顺序队列的基本操作、循环队列)

学习数据结构--第三章:栈和队列(顺序队列的基本操作、循环队列)

Scroll Down

上篇文章中我们讲了 学习数据结构--第三章:栈和队列(栈的基本操作) 下面讲解队列的基本操作。

1.队列的基本概念

队列(Queue) 只允许在表的 一端(队尾) 进行插入,表的 另一端(对头) 进行删除操作的 线性表

在队列中先进入队列的元素会先出队列即:先进先出 (FIFO)

2.队列的基本操作

  • InitQueue(&Q) 初始化队列,构造一个空队列Q
  • QueueEmpty(Q) 判队列空,若队列Q为空返回true,否则返回 false
  • EnQueue(&Q,x) 入队,若队列Q未满,则将x加入使之成为新的队尾。
  • DeQueue(&q,&x) 出队,若队列Q非空,则删除队头元素,并用x返回。
  • GetHead(Q,&x) 读队头元素,若队列Q非空则用x返回队头元素。
  • ClearQueue(&Q) 销毁队列,并释放队列Q占用的内存空间。

3.队列顺序存储结构

顺序队 采用顺序存储的队列。

在上篇栈的文章中我们直到,栈使用一个top变量存储栈顶的下标,用来出栈和入栈,在队列中是否也可以使用一个top变量存储队头的变量,然后操作栈呢?

答案是不行的,注意栈的出栈和入栈都只在一端进行操作,所以一个变量存储下标完全够了,但是队列不同,队列的入队和出队分别在两端,所以我们需要两个变量分别存储入队地址(front)和出队地址(rear),注意:我们规定rear存储队尾元素的下一个位置。

队列的定义:

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

队列中需要注意:

  • front指向队头元素,rear指向队尾元素的下一位置(或front指向队头元素的前一位置,rear指向队尾元素)
  • 平时使用中我们一般让front指向队头元素,rear指向队尾元素的下一位置
  • 初始时 front==rear==0

3.1顺序队列判空&长度&满

判空

队空条件:Q.front == Q.rear == 0 ???
这个判断条件是不对的,如果入队一个元素,接着出队,此时rearfront都是会移动的,此时不是0但是队列也是空的。所以说,上述条件是:不是充分必要条件,真正的条件是:Q.front == Q.rear

长度

front指向队头元素,rear指向队尾元素的下一位置,故队列的长度是:Q.rear - Q.front

队满

队满条件 Q.rear ==MaxSize ???
当队列满的时候,此时进行出队操作,此时出队的时候只是修改了front,并未修改rear,如果按照上述条件判断,队列是满的,但是实际上是空的,这就是假溢出问题.
那么怎么解决这个问题,同时利用上刚刚出队的那个空间呢?我们可以使用一个特殊队列-----循环队列

4.顺序存储的循环队列

循环队列 把存储队列的顺序队列在逻辑上视为一个环。

改成循环队列,将最后一个数据元素单元和第一个数据元素单元连接起来,方法就是取余(%MaxSize)操作

front指针移动
Q.front=(Q.front + 1) % MaxSize
rear指针移动
Q.rear = (Q.rear + 1) % MaxSize
队列长度
(Q.rear + MaxSize - Q.front) % MaxSize

4.1循环队列判空&满

队列判空:Q.front == Q.rear

队列判满:Q.front == Q.rear

此时发现判空和判满条件一致了,这就出现矛盾了。怎么解决呢?

方法一:牺牲一个存储单元

这是最常用的一种方法,具体就是,最后一个元素的位置不存储元素,当Q.front=(Q.rear+1)%MaxSize的时候,表示队列已经满了。这种方法

  • 队列判空条件不变:Q.front == Q.rear
  • 队列判满条件变成:Q.front=(Q.rear+1)%MaxSize

方法二:增加一个变量代表元素的个数

我们初始化一个变量:Q.size=0 。这种方法

  • 判空条件:Q.size == 0
  • 判满条件:Q.size == MaxSize

方法三:增加tag标识

我们发现队列为空是因为删除操作导致,队列为满是因为插入操作导致,所以我们可以使用一个变量来标识队列当前的状态,当队列为空的时候对于循环队列首先Q.front==Q.rear,此时我们标识tag=0,当队列满的时候首先Q.front==Q.rear,我们标识tag=1。这种方法

  • 判空条件:Q.front==Q.rear&&Q.tag == 0
  • 判满条件:Q.front==Q.rear&&Q.tag == 1

4.2循环队列的基本操作

初始化

void Initqueue(SqQueue &Q){
   Q.rear = Q.front = 0;
}

判空

bool isEmpty(SqQueue Q){ 
   if(Q.rear == front) {
       return true; 
   }else{
       return false;
   }

入队

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

出队

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

5.队列链式存储结构

链队 采用链式存储的队列

下面是有头节点的链队,使用front指针指向队头,使用rear指针指向队尾。

队列中每个结点的结构体

typedef struct{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

链队的结构体也就是队头和队尾的两个指针

typedef struct{
   LinkNode *front,*rear;
}LinkQueue;

6.链队的基本操作

初始化

判空

入队

入队就相当于单链表的尾插法

出队

出队相当于单链表的删除头结点的操作

注意:最后一个if 判断就是,如果当前队列只有一个元素,我们删除最后一个元素后需要将rear指针指向头节点。

7.输出序列

输入和输出连续的情况下

  • 输入序列:1,2,3.....n
  • 输出序列:n....3,2,1

队列

  • 输入序列:1,2,3.....n
  • 输出序列:1,2,3.....n

对于队列无论输入序列是否连续,输出序列一定是一样的,都是输入顺序。

栈 输入和输出非连续的情况下

  • 输入序列:1,2,3
  • 输出序列:3 2 1 、2 1 3 、2 3 1 、1 2 3 、1 3 2

输出序列总共是上面五种加3 1 2 六种(按照排列组合),其中3 1 2不合法,按照这种输出序列则入栈为一次性将1 2 3全部入栈,此时出栈序列必为3 2 1.

例子:

其中橙色标识出的序列都是不合法的,我们发现:出栈序列中每一个元素后面所有比它小的元素组成一个递减序列,这样的序列才是合法的序列
比如:3142 这个不和法的序列,3后面比他小的1、2组成了递增序列。

合法出 栈 序列的个数

进栈序列:1,2,3.....n

f(n)=C(2n,n)/(n+1) 求算合法出栈序列的个数公式

8.队列双端序列

双端队列 允许两端都可以进行入队以及出队操作的队列

无论哪一端先出的元素在前,后出的元素在序列后。

如果我们把某一端的插入与删除操作屏蔽,就构成了一个栈。

如果我们把一端的删除屏蔽,一端的插入屏蔽,就构成了一个队列。

8.受限的双端队列

输出受限的双端队列

输入受限的双端队列

下面我们找受限的双端队列的输出序列

输入序列:1,2,3,4

输出受限的双端队列

对于上面的受限的双端队列,栈的判断输出序列完全适用,其中不合法序列有:

如果队列改成下面的样式我们测试上面的不合法序列可以得到,42314132不是合法的序列。

输入受限的双端队列

对于上面的受限的双端队列,栈的判断输出序列完全适用,其中不合法序列有:

如果队列改成下面的样式我们测试上面的不合法序列可以得到,42134231不是合法的序列。

欢迎关注公众号 理木客更多精彩等你发现