- 公开视频 -> 链接点击跳转公开课程
- 博客首页 -> 链接点击跳转博客主页
结构特性
队列是一种特殊的线性表,限制在表的一端进行插入、在表的另一端进行删除。
表中允许插入的一端称为队尾(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;
}
};