数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

队列

• 前言
• 1. 队列介绍
• • 1.1 什么是队列
  • 1.2 队列的性质
  • 1.3 队列的构成
  • 1.4 队列的框架代码（C++版）
• 2. 队列的操作
• • 2.1 初始化队列
  • • 2.1.1 步骤
    • 2.1.2 代码展示
  • 2.2 入队操作
  • • 2.2.1 步骤
    • 2.2.2 代码展示
  • 2.3 输出队列中的元素
  • • 2.3.1 步骤
    • 2.3.2 代码展示
  • 2.4 出队操作
  • • 2.4.1 步骤
    • 2.4.2 代码展示
  • 2.5 问题分析
• 3 循环队列
• • 3.1 循环队列与普通队列的不同
  • 3.2 代码实现
  • 3.3 循环队列的扩容
• 总结

前言

队列是线性表（线性存储结构）中比较特殊的一种，它的特点总结下来就四个字“先进先出”。本文介绍队列以及循环队列

1. 队列介绍

1.1 什么是队列

队列（queue）是一种遵循”先进先出“的存储方式。

如同这个示意图，数据从head开始依次进入队列（入队），取出数据时同样从head开始 依次离开队列（出队）。就像在高铁检票口前排起的一条队伍，先到的人排在前面，后来的人排在队伍的后面（进入队伍不考虑插队），开始检票的时候也是从前往后依次检票（离开队伍）。

队列只是一种对一组数据的处理方式，对于数据的存储既可以采用顺序表的方式也可以采用链表的方式。

本文采用顺序表的方式存储队列中的数据

1.2 队列的性质

• 新元素插入到队列的末尾

• 队首元素先离开队列

1.3 队列的构成

• 队首位置
• 队尾位置
• 队列的容量
• 数据的存储空间

1.4 队列的框架代码（C++版）

#include <iostream>
#include<iostream>
using namespace std;
//
template <typename Type> class Queue {
private:
    Type *data;
    int head, tail, length;
public:
    Queue(int new_length);	// 构造函数，初始化队列
    ~Queue();				// 析构函数，回收队列的内存空间
    bool push(Type val);	// 入队操作
    void output();			// 输出队列中的元素
    void pop();				// 出队操作
};

下述的所有代码都是基于这个框架

2. 队列的操作

2.1 初始化队列

2.1.1 步骤

1. 根据队列的长度为数据申请存储空间
2. 队伍中没有元素将队首置为0
3. 将队尾置为-1（当有入队操作时使队尾加1）

2.1.2 代码展示

Queue(int new_length) {
    data = new Type[new_length];
    length = new_length;
    head = 0;
    tail = -1;
}
~Queue() {
    delete[] data;
}

2.2 入队操作

bool push(Type val)

val为元素的值

2.2.1 步骤

1. 首先根据队尾位置判断队列是否存在可用空间
2. 队尾位置加一，并在此位置插入新元素

2.2.2 代码展示

bool push(Type val) {
    if (tail + 1 > length) {
        return false;
    }
    data[++tail] = val;
    return true;
}

2.3 输出队列中的元素

void output()

2.3.1 步骤

• 从head开始依次输出，直至tail位置。

2.3.2 代码展示

void output() {
    for (int i = head; i <= tail; i++) {
        if (i - head) cout << " ";
        cout << data[i];
    }
    cout << endl;
}

2.4 出队操作

void pop();

2.4.1 步骤

• 直接使队首后移一位

2.4.2 代码展示

void pop() {
    head++;
}

2.5 问题分析

当队列处于这样的情况时，虽然head前还有两块空间可以使用，但tail + 1 超出了队列的长度，因此程序会判断队列已经没有空间插入元素了，显然这是不合理的。

为了充分利用申请的内存空间，循环队列便应运而生。

3 循环队列

3.1 循环队列与普通队列的不同

循环队列是从普通队列改进而来，因此需要具体分析一下循环队列的行为逻辑。

1. 当tail处于队列的最尾端，并且head前还有空间可以使用时，tail会跳回到队列申请空间的最前端
2. 无法通过tail + 1 > length 来判断队列是否已满

需求已经了解，那该如何解决呢？

对于第一点，通过% 操作可以很轻松的实现tail循环到最前端。

第二点只需要在普通队列的基础上添加一个变量count来记录已存储元素的个数，通过这个变量判断队列是否以满。

3.2 代码实现

#include <iostream>
using namespace std;
template <typename Type> class Queue {
private:
    Type *data;
    int head, tail, length, count;
public:
    Queue(int length_input) {
        data = new Type[length_input];
        length = length_input;
        head = 0;
        tail = -1;
        count = 0;
    }
    ~Queue() {
        delete[] data;
    }
    // 入队操作
    bool push(Type element) {
        if (count >= length) {
            return false;
        }
		tail =(tail + 1) % length;
        data[tail] = element;
        count++;
        return true;
    }
    // 输出队列
    void output() {
        int i = head;
        do {
            cout << data[i] << " ";
            i = (i + 1) % length;
        }while(i != (tail + 1) % length);
        cout << endl;
    }
    // 出队操作
    void pop() {
        head = (head + 1) % length;
        count--;
    }
};

3.3 循环队列的扩容

循环队列的扩容分为三步：

1. 申请一块新的大小合适的存储空间
2. 将原队列的数据转移到新空间内
3. 释放原队列的存储空间

void expand() {
    Type *old_data = data;
    data = new Type[length * 2];
    
    int i = head;
    do {
        cout << data[i] << " ";
        i = (i + 1) % length;
    }while(i != (tail + 1) % length);
    
    delete[] old_data;
}

总结

本篇文章详细介绍了队列，下篇文章介绍栈。

本文仅为个人的学习总结，欢迎各位大佬勘误。