数据结构系列——先进先出队列queue

本期主题：
先进先出队列实现

1.队列定义

队列是什么？定义：

• 一个先进先出的数据结构
• 插入操作称为入队（enqueue），入队始终在队尾添加元素
• 删除操作称为出队（dequeue），出队操作始终从队头开始

2.实现一个简单的队列以及分析

1.代码实现分析

先分析该怎么实现队列，其实前面描述了就三个特点，一一分析：

插入操作在队尾实现，使用vector的push_back接口，直接在动态数组尾部实现添加；
删除操作从队头开始，这个需要有一个位置指针，告诉我们现在头部在哪里，然后每次出一个，头部位置就++；

2.code

按如下分析完之后，我们可以实现代码了：

class MyQueue {
private:
    // store elements
    vector<int> data;
    // a pointer to indicate the start position
    int p_start;
public:
    MyQueue() { p_start = 0; }
    /** Insert an element into the queue. Return true if the operation is successful. */
    bool enQueue(int x) {
        data.push_back(x);
        return true;
    }
    /** Delete an element from the queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        p_start++;
        return true;
    };
    /** Get the front item from the queue. */
    int Front() {
        return data[p_start];
    };
    /** Checks whether the queue is empty or not. */
    bool isEmpty()  {
        return (p_start >= data.size());
    }
};

完整代码：

int main() {
    MyQueue q;
    q.enQueue(5);
    q.enQueue(3);
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
    q.deQueue();
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
    q.deQueue();
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
}

输出结果：

3.优缺点分析

优点：

代码简单，非常好实现

缺点：

存在假满的情况，效率低，有空间浪费情况存在

我们看一个例子：
假设我们定义一个size为5的queue，第一步我们先dequeue，然后再enqueue，会发现此时这个queue已经满了，但实际上有效的数据只有4个

3.循环队列实现

1.循环队列原理

针对上面提到的效率低、空间利用有限的问题，更好的方案是使用一个循环队列，即头和尾能够连在一起，如下图所示：

2.循环队列实现分析

循环队列实现需要分析以下几点：

• 首先，肯定是需要两个位置变量，来表明当前的头和尾
• 判断队列空条件分析：空的时候，头和尾都应该指向非当前数据区域，当头=尾时，应该是只剩了最后一个元素
• 判断队列满条件分析：满的时候，尾+1=头，但是有循环回来的问题，所以应该是 (尾+1)%(整个size)=头

3.code

class MyCircularQueue {
public:
    vector<int> data;
    int head_pos = -1;
    int rear_pos = -1;
    int size = 0;
    
    MyCircularQueue(int k) {
        data.resize(k);
        size = k;
    }
    
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }

        if (isEmpty()) {
            head_pos = 0;
        }
        rear_pos++;

        rear_pos = rear_pos % size;
        data[rear_pos] = value;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        
        if (head_pos == rear_pos) {
            head_pos = -1;
            rear_pos = -1;
            return true;
        }

        head_pos++;
        head_pos = head_pos % size;
        return true;
    }
    
    int Front() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[head_pos];
        }
    }
    
    int Rear() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[rear_pos];
        }
    }
    
    bool isEmpty() {
        return (head_pos == -1);
    }
    
    bool isFull() {
        return ((rear_pos + 1) % size == head_pos);
    }
};