队列（First In First Out）

顺序队列 

#include <iostream>class MyQueue {private:// store elementsvector<int> data;       // a pointer to indicate the start positionint 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;}
}

假溢出

设计循环队列（数组）

【数据结构】设计循环队列_小陶来咯的博客-CSDN博客 

 

 初始化（设置数组长度为K+1）

 class MyCircularQueue {
public:
MyCircularQueue(int k) {this->capacity=k+1; //初始化队列的容量为K+1this->vec=vector<int>(capacity);  //数组容器大小为capacityfront=rear=0; //初始化首尾 标识}

如果不设置成K+1 

 

---

 

解决办法：牺牲一个存储单元，这个单元不入数据元素，规定如果队尾指针的下一个位置即为队首位置，就认为循环队列满了

---

 进/入栈

！！！判断

首先判断操作的合理性，队列是满/还是空 

 bool enQueue(int value) {if(isFull())return false;else{vec[rear]=value;  //在尾部指示 所在位置插入元素rear=(rear+1)%capacity; //更新尾部指示的位置 %capacity（如果rear在最后一个，要更新为指示0号位置，就需要+1后对capacity取余）return true;}}bool deQueue() {if(isEmpty())return false;else{front=(front+1)%capacity; //无需其他操作，只需更新front 的位置 return true;}}

获取对头/对尾元素

！！！首先判断是不是空队列

 //如果是空集，则没有元素，更别谈队头和队尾int Front() {if(isEmpty())return -1;else{return vec[front];}}int Rear() {if(isEmpty())return -1;else{return vec[(rear-1+capacity)%capacity]; //队尾指示 它指的是 最后一个元素的下一个位置，所以需要减去1，同时需要注意负数的问题，所以+capacity后再对capacity取余}}

判断队列满/空

 bool isEmpty() {return front==rear;}bool isFull() {return front==(rear+1)%capacity;}
private:vector<int>vec;int capacity;int front, rear;
};

为空

front==rear

为满

front==(rear+1)%capacity 

---

 

设计循环队列（链表） 

    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        ListNode *node = new ListNode(value);
        if (!head) {
            head = tail = node; //1
        } else {
            tail->next = node;
            tail = node; //2
        }
        size++;
        return true;
    }

1 

如果头指针为空，就要让head和tail同时指向node 

2 

“tail->next=node;tail=node;这两句话到底什么意思”

将node指针指向的对象赋给tail的next对象，也就是尾指针的下一个对象。由于尾指针有了新的next对象，因此不再是末尾了。
之后tail = node;就是将tail指向新的末尾元素。

 

 

class MyCircularQueue {
private:ListNode *head;ListNode *tail;int capacity;int size;public:MyCircularQueue(int k) {this->capacity = k;this->size = 0;this->head = this->tail = nullptr;}bool enQueue(int value) {if (isFull()) {return false;}ListNode *node = new ListNode(value);if (!head) {head = tail = node;} else {tail->next = node;tail = node;}size++;return true;}bool deQueue() {if (isEmpty()) {return false;}ListNode *node = head;head = head->next;  size--;delete node;return true;}int Front() {if (isEmpty()) {return -1;}return head->val;}int Rear() {if (isEmpty()) {return -1;}return tail->val;}bool isEmpty() {return size == 0;}bool isFull() {return size == capacity;}
};