C++實(shí)現(xiàn)順序循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列
語(yǔ)言這個(gè)東西不用真的會(huì)忘鲫剿， 我記得前前后后C++的基本語(yǔ)法我也看了好幾遍了挂捅，一直沒(méi)有動(dòng)手寫過(guò)什么東西，所以一遍遍的看洪囤，一遍遍的忘... ...
正好最近在看數(shù)據(jù)結(jié)構(gòu)，想著自己用C++來(lái)實(shí)現(xiàn)一下撕氧，一方面是熟悉整個(gè)邏輯過(guò)程瘤缩，加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，另一方面伦泥，也熟悉一下C++剥啤。
順序存儲(chǔ)循環(huán)隊(duì)列
棧是“先進(jìn)后出”（FIFO）的結(jié)構(gòu)，與之相反不脯，隊(duì)列是“先進(jìn)先出”（FIFO）結(jié)構(gòu)府怯，就比如我們?cè)谝粋€(gè)窗口排隊(duì)打飯，那么先排隊(duì)的人一定先打好飯（當(dāng)然防楷，要排除插隊(duì)的情況）牺丙。
如上圖所示，如果還有兩個(gè)元素等待進(jìn)入隊(duì)列中時(shí)复局，第一個(gè)元素放到索引為6的位置冲簿，rear也向后移動(dòng)一個(gè)位置；第二個(gè)元素進(jìn)入隊(duì)列時(shí)亿昏，此時(shí)隊(duì)列中還有兩個(gè)位置峦剔，可是rear不能再往后移動(dòng)了，所以這樣會(huì)造成內(nèi)存的浪費(fèi)龙优，如果我們?cè)O(shè)定rear可以向前運(yùn)動(dòng)羊异，此時(shí)就解決了這種情況事秀，如圖所示：
如果按照這種設(shè)計(jì)，需要注意一下幾點(diǎn)：
-
隊(duì)列滿的條件為(rear + 1) % QueueSize == front 時(shí)認(rèn)為棧滿野舶，如下圖所示：
front == 2易迹， rear == 1, QueueSize == 7, (rear + 1) % QueueSize == 2 % 7 == 2 == front;
-
計(jì)算隊(duì)列長(zhǎng)度的公式：(rear - front + QueueSize) % QueueSize，其中QueueSize為隊(duì)列的最大尺寸平道；
如上圖所示睹欲，隊(duì)列長(zhǎng)度為(rear - front + QueueSize) % QueueSize == (1 - 2 + 7) % 7 == 6;
-
入隊(duì)的操作：
data[rear] = elem; //elem為需要入隊(duì)的元素；
rear = (rear + 1) % max_size; -
出隊(duì)的操作
front = (front + 1) % max_size;
代碼實(shí)現(xiàn)：
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;
}
}
};
測(cè)試代碼：
/*
* 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;
}
執(zhí)行結(jié)果：
鏈?zhǔn)酱鎯?chǔ)隊(duì)列
下圖所示為帶有頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列一屋，front指向頭結(jié)點(diǎn)窘疮，rear指向隊(duì)尾的元素。
當(dāng)有元素入隊(duì)時(shí)：
當(dāng)元素出隊(duì)時(shí)的兩種情況：
左圖為刪除的結(jié)點(diǎn)不是隊(duì)尾結(jié)點(diǎn)冀墨，右圖為刪除的結(jié)點(diǎn)為隊(duì)尾結(jié)點(diǎn)：
實(shí)現(xiàn)代碼：
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;
}
}
};
測(cè)試代碼：
/*
* 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;
}
執(zhí)行結(jié)果：
