data structure

1. 队列的基本概念

1.1 队列的定义

队列(queue)。队列简称队 ,只允许在表的一端进行插入,而在表的另一端进行删除 。向队列插入元素称为入队或进队;删除元素称为出队或离队 。这和我们日常生活的排队是一致的 。特性是先进先出(First In First Out,FIFO),故又称先进先出的线性表。

  1. 队头(Front)。允许删除的一端,又称队首
  2. 队尾(Rear)。允许插入的一端 。
  3. 空队列 。不含任何元素的空表 。

1.2 队列常见的基本操作

InitQueue(&Q) :初始化队列 ,构造一个空队列 Q

QueueEmpty(Q) :判队列空,若队列 Q 为空返回 true ,否则返回 false 。

EnQueue(&Q,x) :入队 ,若队列 Q 未满 ,将 x 加入 ,使之成为新的队尾

DeQueue(&Q,&x) : 出队 ,若队列 Q 非空,删除队头元素 ,并用 x 返回 。

GetHead(Q, &x) :读队头元素,若队列 Q 非空 ,则将队头元素赋值给 x 。

读取受限,不可读取队列中间的某个数据 。

2. 队列的顺序存储结构

2.1 队列的顺序存储

分配连续的存储单元存放队列中的元素 ,并附设两个指针 front 和 rear 分别指示队头元素和队尾元素的位置 。

初始状态 :front=rear=0

进队操作 :队不满时,先送值到队尾元素,再将队尾指针 + 1 。

出队操作 :队不空时,先取队头元素值 ,再将队头指针 +1

可能出现上溢出 ,但是并不是真正的溢出,因为前面出队后仍然有空位置 。

2.2 循环队列

将顺序队列臆造为一个环状的空间 ,即把存储队列元素的表从逻辑上视为一个环 ,称为循环队列 。当队尾指针 front=MaxSize-1 后 ,再前进一个位置就自动到 0,利用除法取余运算(%)来实现 。

初始时 :front=rear=0

队首指针进 1 :front=(front+1) % MaxSize

队尾指针进 1 :rear=(rear+1) % MaxSize

队列长度 :(rear+MaxSize-front)%MaxSize

出队入队时 ,指针都按顺时针方向进 1 。判断队满有三种方法

  1. 牺牲一个单元来区分队空和队满

    入队时少用一个队列单元,这是一种较为普遍的做法,约定以 “队头指针在队尾指针的下一个位置作为队满的标志”

    队满条件 :(rear+1) % MaxSize == front

    队空条件仍为 :front=rear

    队列中元素的个数为 (rear-front+MaxSize) % MaxSize

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

    队空的条件为 size == 0

    队满的条件为 size ==MaxSize

    这两种情况都有 front == rear

  3. 类型中增设 tag 数据成员

    tag = 0 :若因删除导致 front == rear ,队空 ;

    tag = 1 :若因插入导致 front == rear ,队满 ;

2.3 循环队列的操作

  1. 初始化
  2. 判队空
  3. 入队
  4. 出队

3. 队列的链式存储结构

3.1 队列的链式存储

队列链式表示称为链队列,实际上是一个同时带有队头指针和队尾指针的单链表 。头指针指向队头结点,尾指针指向队尾结点 ,即单链表的最后一个结点 。

不带头结点的链式队列操作上比较麻烦,因此通常将链式队列设计成一个带头结点的单链表 。

当 front == rear 时,链式队列为空 。

3.2 链式队列的基本操作

  1. 初始化
  2. 判队空
  3. 入队
  4. 出队

4. 双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列 。其元素的逻辑结构仍是线性结构 。将队列的两端分别称为前端和后端 ,两端都可以入队和出队 。

输出受限的双端队列 :二入一出

输入受限的双端队列 :二出一入

输入队列为 1,2,3,4 。受限的双端队列不能得到哪些输出队列(P77)(栈的公式,队列的公式,最后是混合列举)