数据结构 - C/C++ - 队列
结构特性
-
队列是一种特殊的线性表，限制在表的一端进行插入、在表的另一端进行删除。
-
表中允许插入的一端称为队尾(rear) - 进队 | 入队
-
表中允许删除的一端称为队头(front) - 退队 | 出队
-
-
先进先出(first in first out - FIFO) - 队列中先进入的元素最先出队。
结构实现
-
静态队列 - 基于数组 - 顺序存储
-
动态队列 - 基于链表 - 链式存储
结构容器
-
queue
-
deque
结构设计
-
顺序存储
-
链式存储
class Node
{
public:int value;Node* Next;Node(int Num) : value(Num), Next(nullptr) {}
};class Queue
{
public:Node* front;Node* rear;int size;public:Queue() : front(nullptr) , rear(nullptr), size(0) {}~Queue(){Clear();}public:int GetSize(){return size;}bool IsEmpty(){return size == 0;}void Clear(){Node* node = front;while (node){Node* temp = node;node = node->Next;delete temp;}}public:void Push(int value){Node* node = new Node(value);if (front == nullptr){front = node;rear = node;}else{rear->Next = node;rear = node;}size++;}int Pop(){if (IsEmpty()) return 0;int RetValue = GetFront();Node* node = front;front = front->Next;delete node;size--;return RetValue;}int GetFront(){if (this->front){return this->front->value;}return -1;}int GetRear(){if (this->rear){return this->rear->value;}return - 1;}
};
- 双端队列
#include <iostream>class Node
{
public:int value;Node* Prev;Node* Next;Node(int value) : value(value), Prev(nullptr), Next(nullptr) {}
};class Deque
{
public:Node* front;Node* rear;int size;public:Deque(): front(nullptr), rear(nullptr), size(0) {}~Deque(){Node* node = front;while (node){Node* temp = node;node = node->Next;delete temp;}}public:int GetSize(){return this->size;}bool IsEmpty(){return this->size == 0;}public:void PushFornt(int value){Node* node = new Node(value);if (IsEmpty()){front = rear = node;}else{node->Prev = nullptr;node->Next = front;front->Prev = node;front = node;}size++;}void PushRear(int value){Node* node = new Node(value);if (IsEmpty()){front = rear = node;}else{node->Next = nullptr;node->Prev = rear;rear->Next = node; rear = node;}size++;}int PopFront(){int Ret = 0;if (IsEmpty()){return -1;}else{Ret = this->front->value;Node* node = this->front->Next;if (node != nullptr){node->Prev = nullptr;}delete front;front = node;}size--;return Ret;}int PopRear(){int Ret = 0;if (IsEmpty()){return -1;}else{Ret = this->rear->value;Node* node = this->rear->Prev;if (node != nullptr){node->Next = nullptr;}delete rear;rear = node;}size--;return Ret;}int GetFront(){if (IsEmpty()){return -1;}return front->value;}int GetRear(){if (IsEmpty()){return -1;}return rear->value;}};