[教學] 教你如何 輕鬆了解資料結構-Queue

大家好
今天要來教大家Queue

假如你看過了這篇關於stack的介紹
那你其實就很好理解Queue的原理了

Queue的概念可以先從一個日常生活的例子來了解：
今天是柯南劇場版21彈上映的日子
身為忠實柯南迷的你不能錯過這個一年一度的盛事
於是趕緊前去電影院看電影

結果太興奮了
到了電影院才發現自己忘記買票
因為這場柯南的電影據說很精彩
吸引了一大票人來觀賞
把隊伍拉的長～長～長～
想看電影的你只好跟著排隊了

在排隊的期間
你忽然發現
第一個進來隊伍的人就會是第一個被店員服務
第二個進來隊伍的人就會是第二個被店員服務
以此類推
所以如果你是第87個人
得先等1～86的人都被店員服務了才會輪到你

Queue的概念就是如此
如果有一個資料結構
遵守一個法則：先進先出(FIFO) 或 後進後出(LILO)
((如果有學過會計的人應該很熟悉這名詞吧XD
也就是先放進去的東西就會比較快拿出來
我們就稱這個資料結構為Queue

以下是C++的方式實作Queue：

typedef struct node { int datum; struct node* next; } node;
//用typedef的用意是，這樣後面要用到這個struct時，只要寫node而不用寫struct node

class queue{
public:
queue() : front(NULL),back(NULL),sz(0) {}
~queue();
void enqueue(int);
int dequeue();
int get_value();
int size();
private:
node* front;
node* back;
int sz;
};

queue::~queue()
{
while(front != NULL) {
node* tmp=front;
front=front->next;
delete tmp;
}
}

void queue::enqueue(int in)
{
cout<<in<<' ';
node* n = new node;
n->datum = in;
n->next = NULL;
if(front == NULL) {
front = n;
back = n;
sz = 1;
} else {
node* traverse = front;
while(traverse->next != NULL) {
traverse = traverse->next;
}
traverse->next = n;
back = n;
++sz;
}
}

int queue::dequeue()
{
int result = front->datum;
node* tmp = front;
if(front->next != NULL){
front = front->next;
delete tmp;
} else {
front = NULL;
back = NULL;
delete tmp;
}
--sz;
return result;
}

int queue::get_value()
{
return front->datum;
}

int queue::size()
{
return sz;
}

※測試範例
#include<iostream>
int main()
using namespace std;
{
queue q1;
int n[6]={1,2,3,5,9,10};
for(int i=0;i<3;++i) q1.enqueue(n[i]);
cout << endl<< q1.size()<<endl;
for(int i=0;i<2;++i) cout << q1.dequeue()<<' ';
cout << endl<<q1.size()<<endl<<"next\n";
for(int i=3;i<6;++i) q1.enqueue(n[i]);
cout << endl<< q1.size()<<endl;
for(int i=0;i<4;++i) cout << q1.dequeue()<<' ';
cout << endl<<q1.size()<<endl;
}