本文已經過時, 最新的重構文章請點擊 : 《【資料結構 – 重構】雙向佇列 (雙端佇列) [上篇]》
雙向佇列是一種限定的線型結構. 儘管名字中存在佇列, 但實際並不是佇列. 它是一種同時具有佇列和堆疊性質的抽象數據類型. 它可以同時在前端或者後端插入或者彈出. 當然, 所有的操控都限於兩端
在實際的應用中, 除去不受限制的雙向佇列, 還有彈出受限制的雙向佇列和插入受限制的雙向佇列
- 輸出受限制 : 一端只允許插入, 另一端允許插入或者彈出
- 輸入受限制 : 一端只允許彈出, 另外一端允許插入和彈出
- 不受限制 : 兩頓都允許插入和彈出
不受限制的雙向佇列, 前端禁止操控即是一個堆疊, 當然實際運用到雙向佇列的話, 基本不會這樣去禁止, 因為可以直接用 stack 來處理
我在寫雙向佇列的時候, 將情況分為 5 種 :
- 前端彈出受限制
- 前端插入受限制
- 後端彈出受限制
- 後端插入受限制
- 兩端都不受限制
這些都可以通過一個類別和不同的選單去完成. 當然, 你可以使用不同的類別和同一個選單和提示完成
我們使用一張 SVG 圖像來表示雙向佇列
在本次的代碼中, 使用到了 STL (C++ 的標準程式庫) 中的 vector. 因為如果使用陣列來表示 Deque 的話, 程式碼會顯得很繁瑣. 並且這次並沒有使用註解, 因為代碼形式和之前的差別不大
下面是本人寫的原始碼
如若有錯誤存在, 可以聯絡我或者直接添加評論. 關於原始碼的註解, 已經給的比較全面, 還有不明白的可以直接評論, 對於註解的建議也可以提出. 直接讀原始碼的函式名稱或者變數名稱可以直接了解作用
Deque.hpp :
#ifndef DEQUE_DEQUE_HPP
#define DEQUE_DEQUE_HPP
#include <iostream>
#include <cstdlib>
#include <vector>
namespace Deque {
using std::cin;
using std::cout;
using std::endl;
using std::vector;
class Queue {
private :
bool isEmpty();
protected :
vector<int> vec;
public :
Queue();
~Queue();
long long int getFirst();
long long int getLast();
void firstEnter(int data);
void lastEnter(int data);
void firstOut();
void lastOut();
void clearDeque();
void clearVector();
void showDeque();
};
}
#endif //DEQUE_DEQUE_HPPDeque.cpp :
#include "Deque.hpp"
using namespace Deque;
Queue::Queue() {
}
Queue::~Queue() {
}
bool Queue::isEmpty() {
if(this->vec.empty()) {
return true;
}
return false;
}
long long int Queue::getFirst() {
if(this->isEmpty()) {
return INT64_MIN;
}
return (long long int)this->vec.front();
}
long long int Queue::getLast() {
if(this->isEmpty()) {
return INT64_MIN;
}
return (long long int)this->vec.back();
}
void Queue::firstEnter(int data) {
this->vec.insert(this->vec.begin(), data);
}
void Queue::lastEnter(int data) {
this->vec.push_back(data);
}
void Queue::firstOut() {
if(this->isEmpty()) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
return;
}
cout << "The element : " << this->vec.front() << " has been out!" << endl;
this->vec.erase(this->vec.begin());
cout << "Press any key to continue!" << endl;
getchar();
getchar();
}
void Queue::lastOut() {
if(this->isEmpty()) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
return;
}
cout << "The element : " << this->vec.back() << " has been out!" << endl;
this->vec.pop_back();
cout << "Press any key to continue!" << endl;
getchar();
getchar();
}
void Queue::clearDeque() {
this->vec.clear();
}
void Queue::clearVector() {
vector<int> tempVector;
tempVector.swap(this->vec);
}
void Queue::showDeque() {
if(this->isEmpty()) {
return;
}
int size = this->vec.size();
cout << "Index : \t";
for(int i = 1; i <= size; i++) {
cout << i << "\t";
}
cout << endl << "Element : \t";
for(vector<int>::iterator iterator = this->vec.begin(); iterator < this->vec.end(); iterator++) {
cout << *iterator << "\t";
}
cout << endl;
}main.cpp :
#include "Deque.hpp"
#define UNLIMITED_QUEUE 1
#define FIRST_OUT_LIMITED_QUEUE 2
#define FIRST_ENTER_LIMITED_QUEUE 3
#define LAST_OUT_LIMITED_QUEUE 4
#define LAST_ENTER_LIMITED_QUEUE 5
using namespace Deque;
void unlimitedQueueMenu();
void unlimitedQueueLoop(Queue *deque);
void firstOutLimitedQueueMenu();
void firstOutLimitedQueueLoop(Queue *deque);
void firstEnterLimitedQueueMenu();
void firstEnterLimitedQueueLoop(Queue *deque);
void lastOutLimitedQueueMenu();
void lastOutLimitedQueueLoop(Queue *deque);
void lastEnterLimitedQueueMenu();
void lastEnterLimitedQueueLoop(Queue *deque);
int main(int argc, char *argv[]) {
int choice;
auto *deque = new Queue;
cout << "-------------------------------------" << endl;
cout << "1. Unlimited Queue" << endl;
cout << "2. First Out Limited Queue" << endl;
cout << "3. First Enter Limited Queue" << endl;
cout << "4. Last Out Limited Queue" << endl;
cout << "5. Last Enter Limited Queue" << endl;
cout << "-------------------------------------" << endl;
cout << "Please choose what queue you want to use : ";
cin >> choice;
switch(choice) {
case UNLIMITED_QUEUE :
unlimitedQueueLoop(deque);
break;
case FIRST_OUT_LIMITED_QUEUE :
firstOutLimitedQueueLoop(deque);
break;
case FIRST_ENTER_LIMITED_QUEUE :
firstEnterLimitedQueueLoop(deque);
break;
case LAST_OUT_LIMITED_QUEUE :
lastOutLimitedQueueLoop(deque);
break;
case LAST_ENTER_LIMITED_QUEUE :
lastEnterLimitedQueueLoop(deque);
break;
default :
break;
}
}
void unlimitedQueueMenu() {
cout << "-------------------------------------" << endl;
cout << "1. Get the first element." << endl;
cout << "2. Get the last element." << endl;
cout << "3. First enter." << endl;
cout << "4. Last enter." << endl;
cout << "5. First out." << endl;
cout << "6. Last out." << endl;
cout << "7. Clear the deque." << endl;
cout << "8. Exit." << endl;
cout << "-------------------------------------" << endl;
cout << "Please enter your choice : ";
}
void unlimitedQueueLoop(Queue *deque) {
int choice;
long long int dataGet;
int data;
do {
system("clear");
deque->showDeque();
unlimitedQueueMenu();
cin >> choice;
switch(choice) {
case 1 :
dataGet = deque->getFirst();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 2 :
dataGet = deque->getLast();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 3 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->firstEnter(data);
break;
case 4 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->lastEnter(data);
break;
case 5 :
deque->firstOut();
break;
case 6 :
deque->lastOut();
break;
case 7 :
deque->clearDeque();
break;
case 8 :
deque->clearVector();
delete deque;
exit(0);
default :
break;
}
}while(choice != 8);
}
void firstOutLimitedQueueMenu() {
cout << "-------------------------------------" << endl;
cout << "1. Get the first element." << endl;
cout << "2. Get the last element." << endl;
cout << "3. First enter." << endl;
cout << "4. Last enter." << endl;
cout << "5. Last out." << endl;
cout << "6. Clear the deque." << endl;
cout << "7. Exit." << endl;
cout << "-------------------------------------" << endl;
cout << "Please enter your choice : ";
}
void firstOutLimitedQueueLoop(Queue *deque) {
int choice;
long long int dataGet;
int data;
do {
system("clear");
deque->showDeque();
firstOutLimitedQueueMenu();
cin >> choice;
switch(choice) {
case 1 :
dataGet = deque->getFirst();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 2 :
dataGet = deque->getLast();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 3 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->firstEnter(data);
break;
case 4 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->lastEnter(data);
break;
case 5 :
deque->lastOut();
break;
case 6 :
deque->clearDeque();
break;
case 7 :
deque->clearVector();
delete deque;
exit(0);
default :
break;
}
}while(choice != 7);
}
void firstEnterLimitedQueueMenu() {
cout << "-------------------------------------" << endl;
cout << "1. Get the first element." << endl;
cout << "2. Get the last element." << endl;
cout << "3. Last enter." << endl;
cout << "4. First out." << endl;
cout << "5. Last out." << endl;
cout << "6. Clear the deque." << endl;
cout << "7. Exit." << endl;
cout << "-------------------------------------" << endl;
cout << "Please enter your choice : ";
}
void firstEnterLimitedQueueLoop(Queue *deque) {
int choice;
long long int dataGet;
int data;
do {
system("clear");
deque->showDeque();
firstEnterLimitedQueueMenu();
cin >> choice;
switch(choice) {
case 1 :
dataGet = deque->getFirst();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 2 :
dataGet = deque->getLast();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 3 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->lastEnter(data);
break;
case 4 :
deque->firstOut();
break;
case 5 :
deque->lastOut();
break;
case 6 :
deque->clearDeque();
break;
case 7 :
deque->clearVector();
delete deque;
exit(0);
default :
break;
}
}while(choice != 7);
}
void lastOutLimitedQueueMenu() {
cout << "-------------------------------------" << endl;
cout << "1. Get the first element." << endl;
cout << "2. Get the last element." << endl;
cout << "3. First enter." << endl;
cout << "4. Last enter." << endl;
cout << "5. First out." << endl;
cout << "6. Clear the deque." << endl;
cout << "7. Exit." << endl;
cout << "-------------------------------------" << endl;
cout << "Please enter your choice : ";
}
void lastOutLimitedQueueLoop(Queue *deque) {
int choice;
long long int dataGet;
int data;
do {
system("clear");
deque->showDeque();
lastOutLimitedQueueMenu();
cin >> choice;
switch(choice) {
case 1 :
dataGet = deque->getFirst();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 2 :
dataGet = deque->getLast();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 3 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->firstEnter(data);
break;
case 4 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->lastEnter(data);
break;
case 5 :
deque->firstOut();
break;
case 6 :
deque->clearDeque();
break;
case 7 :
deque->clearVector();
delete deque;
exit(0);
default :
break;
}
}while(choice != 7);
}
void lastEnterLimitedQueueMenu() {
cout << "-------------------------------------" << endl;
cout << "1. Get the first element." << endl;
cout << "2. Get the last element." << endl;
cout << "3. First enter." << endl;
cout << "4. First out." << endl;
cout << "5. Last out." << endl;
cout << "6. Clear the deque." << endl;
cout << "7. Exit." << endl;
cout << "-------------------------------------" << endl;
cout << "Please enter your choice : ";
}
void lastEnterLimitedQueueLoop(Queue *deque) {
int choice;
long long int dataGet;
int data;
do {
system("clear");
deque->showDeque();
lastEnterLimitedQueueMenu();
cin >> choice;
switch(choice) {
case 1 :
dataGet = deque->getFirst();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 2 :
dataGet = deque->getLast();
if(dataGet == INT64_MIN) {
cout << "The deque is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The first element : " << dataGet << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 3 :
cout << "Please enter the element you want to enter : ";
cin >> data;
deque->firstEnter(data);
break;
case 4 :
deque->firstOut();
break;
case 5 :
deque->lastOut();
break;
case 6 :
deque->clearDeque();
break;
case 7 :
deque->clearVector();
delete deque;
exit(0);
default :
break;
}
}while(choice != 7);
}自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《資料結構 : 雙向佇列 (雙端佇列)》https://jonny.vip/2018/03/08/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e9%9b%99%e5%90%91%e4%bd%87%e5%88%97/
AliPay QR Code
WeChat QR Code
Leave a Reply