Rookie's blog

Chapter4 队列

Chapter4 队列

  • 先进先出(FIFO:First In First Out)表
  • 到达越早的结点，离开的时间越早
  • 只能在头端进行删除（队首），在尾端进行插入（队尾）

队列的基本操作

  • 创建一个队列create()：创建一个空的队列；
  • 入队enQueue(x)：将x插入队尾，使之成为队尾元素；
  • 出队deQueue()：删除队头元素并返回队头元素值；
  • 读队头元素getHead()：返回队头元素的值；
  • 判队列空isEmpty()：若队列为空，返回true，否则返回false。

队列的抽象类

1
2
3
4
5
6
7
8
9
template <class elemType>
class queue
 { public: 
        virtual bool isEmpty() = 0;                  //判队空
        virtual void enQueue(const elemType &x) = 0; //进队
        virtual elemType  deQueue() = 0;             //出队
	    virtual elemType getHead() = 0;              //读队头元素
        virtual ~queue() {}                          //虚析构函数
 };

队列的顺序存储

  • 使用数组存储队列中的元素
  • 队列中的结点个数最多为MaxSize个
  • 元素下标的范围从0到MaxSize-1
  • 顺序队列的三种组织方式

    • 队头位置固定（不用）

    • 队头位置不固定（不用）

    • 循环队列（常用）

循环队列

入队操作

1
2
rear = (rear + 1) % maxSize
elem[rear] = x

出队操作

1
front = (front + 1) % maxSize

（关键）如何判空和满？

如果直接使用循环数列，会出现空和满时都是 rear == front的情况，无法区分

所以需要解决方案：

一种解决方案是："牺牲"一个单元，规定front指向的单元不能存储队列元素，只起到标志作用

这样，队列为空的条件为

1
rear == front

队列为满的条件为

1
(rear + 1) % maxSize == front

当然，这并不是唯一的解决方案，也有很多其他方案。

比如，增加一个变量，记录currentLength，然后结合currentLength是否为0判断当然也是可以的

循环队列类的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class elemType>
class seqQueue: public queue<elemType>
{
private:
     elemType *elem;
	 int maxSize;
	 int front, rear;	  
	 void doubleSpace();
public:
   seqQueue(int size = 10)；
   ~seqQueue() ；
   bool isEmpty() ；
   void enQueue(const elemType &x) ;
   elemType deQueue();   
   elemType getHead()；
};

构造/析构

构造：申请一块空间，首地址存入elem。数组规模保存在MaxSize中，front和rear置成0。

1
2
3
4
5
6
7
template <class elemType>
  seqQueue<elemType>::seqQueue(int size)
{ 
      elem = new elemType[size];
      maxSize = size; 
      front = rear = 0;
}

析构：删除数组

1
2
3
4
5
template <class elemType>
seqQueue<elemType>::~seqQueue()
{
    delete [] elem;
}

入队：enQueue()

  • 首先要判断数组是否已放满，需要时扩大数组空间。
  • 将元素放入后面的空位，队尾向后移
1
2
3
4
5
6
7
8
9
template <class elemType>
void seqQueue<elemType>::enQueue
                       (const elemType &x)
{ 
    if ((rear + 1) % maxSize == front)
                doubleSpace();
    rear = (rear + 1) % maxSize;
    elem[rear] = x;
}

doubleSpace()

1
2
3
4
5
6
7
8
9
10
11
template <class elemType>
void seqQueue<elemType>::doubleSpace()
{    elemType *tmp =elem;
     elem = new elemType[2 * maxSize];
     for (int i = 1; i < maxSize; ++i)
	  elem[i] = tmp[(front + i) % maxSize];
	 
     front = 0; rear = maxSize - 1;
     maxSize *= 2;
     delete tmp;
}

deQueue()

  • 将front往后移一个位置
  • 返回elem[front]的内容。
1
2
3
4
5
6
template <class elemType>
elemType seqQueue<elemType>::deQueue()
{
     front = (front + 1) % maxSize;
     return elem[front];
}

getHead()

1
2
3
4
5
template <class elemType>
elemType seqQueue<elemType>::getHead() const
{ 
     return elem[(front + 1) % maxSize];
}

isEmpty()

  • 前面已经分析过队列判空条件
1
2
3
4
5
template <class elemType>
bool seqQueue<elemType>::isEmpty() const 
{
      return front == rear;
}

队列的链接实现

  • 由于队列的操作是在队列的两端进行的，不会对队列中的其他元素进行操作，用单链表就足够了。
  • 队列要对表的两端作操作，为方便两端操作，我们可以采用空间换时间的方法，同时记住头尾结点的位置。
  • 综上，使用无头结点，有头指针和尾指针的单链表
image-20240611131424444

队尾和队首的选择

  • 队尾指出的是插入位置，对单链表来说，有了尾指针，在表头插入和表尾插入一样简单。
  • 队头指出的是删除位置，删除表头元素很简单，但删除表尾元素必须知道它前一元素的存储地址，因此在表尾删除要花O（N）的时间。
  • 为此可以将单链表的表头作为队头，单链表的表尾作为队尾，插入和删除均为O(1)

链接队列类的设计

  • 数据成员：
    • 头尾指针
    • 头尾指针的类型：指向结点（数据，下一结点地址）
  • 成员函数：
    • 构造和析构函数
    • 抽象类规定的功能

构造函数

1
2
3
4
5
template <class elemType>
linkQueue<elemType>::linkQueue() 
{
   front = rear = NULL; 
}

入队enQueue()

  • 首先申请一个结点存储 x；
  • 将结点x作为单链表的表尾，即rear指向的结点的指针部分指向结点x，将结点x作为尾结点。
  • 注意，enQueue操作有个特殊情况，就是队列为空的情况。此时，我们只需要申请一个存放x的结点，让front和rear同时指向这个结点。
1
2
3
4
5
6
7
8
template <class elemType>
void linkQueue<elemType>::enQueue(const elemType &x) 
{
    if (rear == NULL)
  	  front = rear = new node(x);
    else 
	  rear = rear->next = new node(x);
}

出队deQueue()

  • 返回front指向的结点的值并删除该结点。
  • 删除表头结点需要先将表头结点从链表中摘下，然后释放表头结点的空间。
  • 注意，deQueue操作有一个特殊情况，即如果执行deQueue操作时队列中只有一个元素，经过deQueue操作，队列为空，此时必须将front和rear同时置成NULL。
1
2
3
4
5
6
7
8
9
10
11
12
template <class elemType>
elemType linkQueue<elemType>::deQueue()
{
    node *tmp = front;
    if (front) {    
    	elemType value = front->data;
    	front = front->next; 
    	if (front == NULL) rear = NULL;      
    	delete tmp;
    	return value;
    }
}

讨论

如果链接实现想只用一个指示器

image-20240611130517404
  • 采用（单）循环链表即可
  • 此处以链表头为队头，以链表尾为队尾
  • 那么就可以不用同时使用头尾指针，只需要保留尾指针就行

如果顺序实现想只用一个指示器且不牺牲空间

  • 增加属性队列长度length
    • rear=front+length
  • 判断空与满不再需要牺牲一个空间

队列的应用

车厢重排问题

一列货运列车共有n节车厢，重新排列这些车厢，将第n节车厢放在最后，第1节车厢放在最前面。

解决这个问题的方法记住以下几个规则就行：

  • 对于每一个入轨上的车进行处理
    • 如果有队尾编号小于该车编号的轨道，从这些轨道中选队尾编号最大的那一个，把车放进去
    • 如果没有队尾编号小于该车编号的轨道，那么就从空轨道中新建一个轨道来放这辆车
    • 如果既没有这样的轨道，也没有空轨道了，那么该问题无法解决
  • 处理完一辆入轨的车后，遍历所有的轨道（队列），比较队首车的编号和出轨上最后一辆车（没有车的话就是0）的编号，如果首车编号恰好比出轨上最后一辆车的编号大1，则可以将该车出轨
    • 如果有车成功出轨，那么再进行一轮遍历，知道进行一轮遍历后没有任何车出轨为止
  • 以上操作交替进行
0%