C++实现顺序循环队列和链式队列
语言这个东西不用真的会忘， 我记得前前后后C++的基本语法我也看了好几遍了，一直没有动手写过什么东西，所以一遍遍的看，一遍遍的忘... ...
正好最近在看数据结构，想着自己用C++来实现一下，一方面是熟悉整个逻辑过程，加深对数据结构的理解，另一方面，也熟悉一下C++。
顺序存储循环队列
栈是“先进后出”（FIFO）的结构，与之相反，队列是“先进先出”（FIFO）结构，就比如我们在一个窗口排队打饭，那么先排队的人一定先打好饭（当然，要排除插队的情况）。
如上图所示，如果还有两个元素等待进入队列中时，第一个元素放到索引为6的位置，rear也向后移动一个位置；第二个元素进入队列时，此时队列中还有两个位置，可是rear不能再往后移动了，所以这样会造成内存的浪费，如果我们设定rear可以向前运动，此时就解决了这种情况，如图所示：
如果按照这种设计，需要注意一下几点：
-
队列满的条件为(rear + 1) % QueueSize == front 时认为栈满，如下图所示：
front == 2， rear == 1, QueueSize == 7, (rear + 1) % QueueSize == 2 % 7 == 2 == front;
-
计算队列长度的公式：(rear - front + QueueSize) % QueueSize，其中QueueSize为队列的最大尺寸；
如上图所示，队列长度为(rear - front + QueueSize) % QueueSize == (1 - 2 + 7) % 7 == 6;
-
入队的操作：
data[rear] = elem; //elem为需要入队的元素；
rear = (rear + 1) % max_size; -
出队的操作
front = (front + 1) % max_size;
代码实现：
const auto max_size = 100;
template <class T>
class Queue {
private:
T front;
T rear;
T data[max_size];
public:
Queue() : front{0}, rear{0} {}
~Queue() = default;
int getLength() const {
int length = (rear - front + max_size) % max_size;
cout << "The length of the queue is " << length << endl;
return length;
}
bool isEmpty() const {
if (front == rear)
return true;
else
return false;
}
bool isFull() const {
if ((rear + 1) % max_size == front)
return true;
else
return false;
}
void push_back(const T &elem) {
if (isFull())
cout << "The queue is full, push error!" << endl;
else {
data[rear] = elem;
rear = (rear + 1) % max_size;
cout << elem << " is pushed!" << endl;
}
}
void pop_front() {
if (isEmpty())
cout << "The queue is empty, pop error!" << endl;
else {
auto elem = data[front];
cout << elem << " is popped!" << endl;
front = (front + 1) % max_size;
}
}
};
测试代码：
/*
* Software:Jetbrains clion 2022.1
* Created by xiaoxin_zh@foxmail.com
* Implementing CircularQueue with C++
*/
#include <iostream>
int main() {
Queue<int> queue;
queue.push_back(10);
queue.push_back(20);
queue.push_back(30);
queue.push_back(40);
queue.push_back(50);
queue.getLength();
queue.pop_front();
queue.pop_front();
queue.pop_front();
queue.pop_front();
queue.pop_front();
queue.pop_front();
return 0;
}
执行结果：
链式存储队列
下图所示为带有头结点的链式队列，front指向头结点，rear指向队尾的元素。
当有元素入队时：
当元素出队时的两种情况：
左图为删除的结点不是队尾结点，右图为删除的结点为队尾结点：
实现代码：
template<typename T>
class LinkedQueue;
template<typename T>
class Node {
friend class LinkedQueue<T>;
private:
T data;
Node *next;
public:
explicit Node(const T &data = 0) : data{data}, next{nullptr} {}
~Node() = default;
};
template<typename T>
class LinkedQueue {
private:
Node<T> *front;
Node<T> *rear;
int length{0};
public:
LinkedQueue() : front{new Node<T>}, rear{front}, length{0} {}
~LinkedQueue() = default;
int getLength() const {
cout << "The length of the queue is " << length << endl;
return length;
}
bool isEmpty() const {
if (front == rear)
return true;
else
return false;
}
void push_back(const T &data) {
auto temp = new Node<T>;
temp->data = data;
rear->next = temp;
rear = temp;
temp->next = nullptr;
++length;
cout << data << " is pushed!" << endl;
}
void pop_front() {
if (isEmpty()) {
cout << "Pop error!" << endl;
return;
}
else {
auto temp = front->next;
auto elem = temp->data;
if (temp == rear) {
rear = front;
cout << elem << " is popped! The queue is empty now!" << endl;
} else {
front->next = temp->next;
cout << elem << " is popped!" << endl;
}
delete temp;
--length;
}
}
};
测试代码：
/*
* Software:Jetbrains clion 2022.1
* Created by xiaoxin_zh@foxmail.com
* Implementing LinkedQueue with C++
*/
#include <iostream>
using std::cout;
using std::endl;
int main() {
LinkedQueue<int> queue;
queue.isEmpty();
queue.push_back(10);
queue.push_back(20);
queue.push_back(30);
queue.getLength();
queue.push_back(40);
queue.push_back(50);
queue.getLength();
queue.pop_front();
queue.pop_front();
queue.getLength();
queue.pop_front();
queue.pop_front();
queue.pop_front();
queue.pop_front();
queue.pop_front();
queue.getLength();
return 0;
}
执行结果：
