[教學] 教你如何 輕鬆了解資料結構-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;
}

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

大家好
今天要來教大家資料結構中基本的一些基本元素
就是Asymptotic Notation
它是用來表示一個程式演算法或者資料結構的動作
需要花多少時間(次數)來執行
共有六種代號
O,o,Θ,θ,Ω,ω

基於輕鬆了解
我就以常用的O,θ,Ω來做教學
詳細的定義就補充在後面留給有需要的人自行參考

O讀做大歐(big-oh)
θ讀做系打(?)(theta)
Ω讀做偶妹嘎(omega)

※Big-O Notation： O(某多項式)
定義：
代表一個操作數量最慘(最多)不超過這個函式(上界的概念)

舉例：
令f(n)=n^2
g(n)=3*n^6-10
假設有一個操作數量的圖形為f(n)

這是概念圖

你會發現
在後來的狀況下g(n) 會穩定在f(n)的函數圖形上面
因此此操作的asymptotic notation為 O(n^6)

欸???等等
為什麼不是O(3*n^6)?
→寫O(3*n^6)也是可以的，不過因為在asymptotic notation，我們只在乎多項式裡面的最高次方，所以我們就省略3不寫，因此
O(3*n^6) = O(n^6)是成立的

※Theta Notation： θ(某多項式)
定義：
代表一個操作會介於一個常數倍的多項式間(保證在一個範圍內的概念，有夾擊的感覺)

舉例：
令f(n) = n^2
g(n) = n^2+1
c1 = 0.5
c2 = 2
假設有個操作數量函式為f(n)

這是概念圖

你會發現
c1*g(n) 和 c2*g(n)可以把f(n)上下包夾起來
因此這個操作的asymptotic notation就是 θ(n^2)

從上面可以知道
如果你已經知道f(n)是多少
要求θ的話
答案就是f(n)的最高次項，因為他主導了這個函式

※Omega Notation：Ω(某多項式)
定義：
代表一個操作數量至少必大於這個函式(下界的概念)

舉例：
令f(n) = n^2
g(n) = 2n + 1
假設有個操作數量函式為f(n)

你會發現
c*g(n)會在f(n)之下
所以這個操作的asymptotic notation是 Ω(n)


----------------------------------------------------------------------------------------------------------
延伸閱讀

※各符號的詳細定義：
└ Big Oh：f(n) = Ο(g(n)) iff ∃正的常數c和n0，使得f(n) ≤ c × g(n), ∀ n >= n0
└ Theta：f(n) = Θ(g(n)) iff ∃正的常數c1,c2和n0，使得c1 × g(n) ≤ f(n) ≤ c2 × g(n) , ∀ n ≥ n0
└ Omega：f(n) = Ω(g(n)) iff ∃正的常數c和n0，使得f(n) ≥ c × g(n), ∀ n >= n0

註：專用術語/縮寫
iff ：if and only if (若且唯若，只有在後面的狀況下成立前面才會成立，反之亦然)

參考資料：
http://notepad.yehyeh.net/Content/DS/CH01/3.php

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

大家好
今天要來教大家Stack

Stack的概念可以先從一個日常生活的例子來了解：
今天要搬宿舍了
必須把宿舍的書全部搬回家
好在平時已經整理得差不多了
只剩下名偵探柯南的漫畫
一個紙箱就可以把書裝完帶回家了

當你在裝書的時候
因為你有順序強迫症
會按照集數把書一本一本的放入紙箱
你有沒有發現

第一本放進去的書要等第二本書拿起來才能看見
第二本放進去的書要等第三本書拿起來才能看見
以此類推
所以你想看87號的柯南漫畫
你得先把88號的漫畫拿出來才行

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

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

class stack{
public:
stack() : top(-1) {}
~stack() { top = -1;}
void push(int);
void pop();
int get_value();
int size();
private:
int top;
int dat[100];
};

void stack::push(int in)
{
++top;
dat[top] = in;
}

void stack::pop()
{
if(top != -1) --top;
}

int stack::get_value()
{
if(top != -1) return dat[top];
else {
std::cout << "get_value error\n";
return 0;
}
}

int stack::size()
{
return top+1;
}

※簡單測試

#include<iostream>
using namespace std;

int main()

{

stack s1;

int n[5] = {21,1,0,2,5};

for(int i=0;i<5;++i) s1.push(n[i]);

for(int i=0;i<5;++i) {

cout << "The value is " << s1.get_value() << endl;

s1.pop();

}

}