關於 Stack 堆疊 -- by tsaiwn@csie.nctu.edu.tw

    堆疊(Stack)與Queue(佇列; 排隊)是很常用的資料結構(Data structure),
不只電腦中很常用, 平常生活中也很常用! 
當你去學生餐廳吃飯, 你要排隊(Queue; 佇列), 
排到了要拿盤子, 那疊盤子是堆疊(Stack), 
因為最上面那盤子是最後洗好放上去的! 只要最後放的會被最先拿走,
我們就稱之為堆疊 Stack, 也就是後進先出(Last In First Out; LIFO);
至於 Queue 就是先進先出(First In First Out; FIFO), 吃飯要排隊,
搭車要排隊, 註冊要排隊, 幾乎一天到晚都在 Queue(佇列)! 
    堆疊除了那疊盤子, 其實你也天天在用, Suppose 你正在宿舍內念書,
叩叩叩, 有同學來敲門, 你會拿個書籤或把書摺頁暫停, 開門請同學進來哈拉,
哈拉一下忽然電話響了, "對不起我接個電話...", 此時堆疊中被堆放了兩件事,
最底下是"要念書", 再上一層是"與朋友哈拉", 假設電話沒講完, 你另一隻手機
又響了, 於是 "ㄟ你不要掛掉, 我先接另一隻電話, 不要掛掉喔!", 你又把
一個元素推入了堆疊, 開始接新的電話! 靠餐, 原來是打錯的, 很生氣!
掛掉後, pop 出堆疊最頂端: 阿就是繼續講剛剛的電話, 還好, 真的沒掛掉:-)
電話講完後, 再 pop 出頂端來處理:"歹勢歹勢, 剛剛我們哈拉到哪了?",
 "ㄟ你太忙不吵你了, 不跟你打屁了, 走人囉!", 於是, 你又 pop 出最頂端:
阿就是繼續念書啦! 想一想, 日常生活中哪些還用了 Stack 呢? 
    程式執行時, 參數推入堆疊 ( C 語言規定要由右而左推入, 這樣最上
面永遠是第一個參數), 然後  Call 函數時, 硬體CPU會自動把 Call 那句的
下一句之address (也就是 Return address)推入堆疊; 所以剛進入函數之時,
堆疊頂端是 Return address, 這時要用一些技巧(利用 CPU 的 BP 暫存器),
以便等一下有辦法取得 Return address 回到原來 Call 那句之下一句 !
因為這時接著要把堆疊的指標暫時往上移動以便空出一塊給 Auto 變數用,
透過 BP 減掉一些值當作指標就可指到某些 Auto 變數, 透過 BP 加上一些值
就可以指到傳入的參數! 
   等事情做完後要想辦法回去, 也要把堆疊指標還原到要執行 "Call"之時的
狀態, 也就是指著第一個參數, 所以這時候看起來就像 Auto 變數都不見了, 
所以說進入函數就生出Auto變數, 離開函數則Auto變數自動消失!
寫在函數內又沒寫 static 的都是 Auto變數(自動變數)!  
   有時候我們寫的程式也要用到堆疊的概念, 但是我們寫的應用程式無法用到
剛剛說的系統的堆疊(由 CPU 的 SP 所指到的記憶體區塊), 必須自己想辦法
做出堆疊的行為, 最簡單是用 Array 搭配一個整數指到堆疊頂端, 也可以使用
struct 搭配 struct 內用個指標指到下一個元素(這是 Linked List)做出堆疊,
阿就是說可以用 Linked List (鏈結串列)來實作出堆疊!

  其實一般人用 C++ 可不必自己設計 Stack, (資工系的要設計給非資工的用:-)
因為 C++ Class library 已經有女共匪寫的 stack, 是以 template (樣板) 方式
定義; 使用上更為方便! 各種 type 的都可用! 連自己定義的資料結構也可以!
例如, stack<Student_t> x; 這樣 x 是一個堆疊, 每個元素是一個 Student_t;
若你寫 stack<double> y; 則 y 是各元素是 double 的堆疊! 
    但注意 STL Library 的堆疊之函數名稱與用法與一般資料結構課本上講的稍
有不同; 例如, 一般課本 pop( ) 不是void function, 會傳回頂端元素, 但是,
C++ STL Library 的 stack 之 pop( ) 是 void, 若你要頂端元素可用 top( );
又如是否空堆疊STL的 stack 是用 empty( ), 不是 isempty( ) 喔 !
    因為C++ Library 的一些資料結構class Library(類別程式庫)來自HP公司的
STL(Standard Template Library), 是由 HP 兩位工程師參考資料結構課本寫的,
其中一位是來自中國大陸的女生 Meng Lee, 所以說 STL 是女共匪寫的:-) 
STL原先是放在網路上讓大家免費使用, 在1999年正式被納入 C++ 類別程式庫中!


9:58pm ccbsd9:stkabc/> cat -n mymainaa.cpp 
     1 // mymainaa.cpp -- CopyLeft by tsaiwn@csie.nctu.edu.tw
     2 // g++ mymainaa.cpp  ; ./a.out
     3 // 其實用 stack <type> mystk; 是用 deque (雙向 queue) 做的 stack
     4 // 所以寫   stack<int> x;   //..
     5 // ..相當於寫   stack<int, deque<int>  > x;    // 注意這與空格! ! !
     6 ///
     7 //注意以下是 1999之後的 C++ 新寫法, 舊法使用 <iostream.h>
     8 #include<iostream>
     9 #include <stack>
    10 #include <deque>
    11 using namespace std;
    12 int main( ){
    13    stack<int, deque<int>  > x;    // 注意這與空格! !
    14    x.push(880);
    15    x.push(770);
    16    x.push(53);
    17    while(!x.empty()){
    18       cout << x.top();  x.pop();
    19    }
    20    cout << endl;
    21 }
9:58pm ccbsd9:stkabc/> g++ mymainaa.cpp
9:58pm ccbsd9:stkabc/> ./a.out
53770880

9:58pm ccbsd9:stkabc/> cat -n mymainbb.cpp
     1 // mymainbb.cpp  -- CopyLeft by tsaiwn@csie.nctu.edu.tw
     2 // g++ mymainbb.cpp  ; ./a.out
     3 // 這例子要求用 <vector> 做的 stack  (default 是用 deque 做的)
     4 #include <stack>
     5 #include "vector"   // 雙引號夾住會先找目前目錄, 找不到再找系統的
     6 //注意以下是 1999之後的 C++ 新寫法, 舊法使用 <iostream.h>
     7 #include <iostream>
     8 using namespace std;
     9 int main( ){
    10    stack<int, vector<int>  > x;    // 注意這與空格! ! !
    11    x.push(880);
    12    x.push(770);
    13    x.push(53);
    14    while(!x.empty()){
    15       cout << x.top();  x.pop();
    16    }
    17    cout << endl;
    18 }

9:58pm ccbsd9:stkabc/> g++ mymainbb.cpp
9:58pm ccbsd9:stkabc/> ./a.out
53770880
9:58pm ccbsd9:stkabc/> 

9:58pm ccbsd9:stkabc/> cat -n mymaincc.cpp
     1 // mymaincc.cpp -- CopyLeft by tsaiwn@csie.nctu.edu.tw
     2 // g++ mymaincc.cpp  ; ./a.out
     3 // ..這個版本要求用 <list> 做的 stack  (default 是用 deque 做的)
     4 using namespace std;   // 新的 #include 寫法須搭配這 std:: namespace
     5 //注意以下是 1999之後的 C++ 新寫法, 舊法使用 <iostream.h>
     6 #include <iostream>
     7 #include <stack>
     8 #include <list>
     9 int main( ){
    10    stack<int, list<int>  > x;    // 注意這與空格! ! !
    11    x.push(880);
    12    x.push(770);
    13    x.push(53);
    14    while(!x.empty()){
    15       cout << x.top();  x.pop();
    16    }
    17    cout << endl;
    18 }

9:58pm ccbsd9:stkabc/> g++ mymaincc.cpp
9:58pm ccbsd9:stkabc/> ./a.out
53770880
9:58pm ccbsd9:stkabc/> 
D:\test> linenum < mymainaa.cpp
   01 // mymainaa.cpp -- CopyLeft by tsaiwn@csie.nctu.edu.tw
   02 // g++ mymainaa.cpp  ; ./a.out
   03 // 其實用 stack <type> mystk; 是用 deque (雙向 queue) 做的 stack
   04 // 所以寫   stack<int> x;   //..
   05 // ..相當於寫   stack<int, deque<int>  > x;    // 注意這與空格! ! !
   06 ///
   07 //注意以下是 1999之後的 C++ 新寫法, 舊法使用 <iostream.h>
   08 #include<iostream>
   09 #include <stack>
   10 #include <deque>
   11 using namespace std;
   12 int main( ){
   13    stack<int, deque<int>  > x;    // 注意這與空格! ! !
   14    x.push(880);
   15    x.push(770);
   16    x.push(53);
   17    while(!x.empty()){
   18       cout << x.top();  x.pop();
   19    }
   20    cout << endl;
   21 }

D:\test> g++ mymainaa.cpp 

D:\test> a.exe
53770880

D:\test> 
D:\test> linenum < mymainbb.cpp
   01 // mymainbb.cpp  -- CopyLeft by tsaiwn@csie.nctu.edu.tw
   02 // g++ mymainbb.cpp  ; ./a.out
   03 // 這例子要求用 <vector> 做的 stack  (default 是用 deque 做的)
   04 #include <stack>
   05 #include "vector"   // 雙引號夾住會先找目前目錄, 找不到再找系統的
   06 //注意以下是 1999之後的 C++ 新寫法, 舊法使用 <iostream.h>
   07 #include <iostream>
   08 using namespace std;
   09 int main( ){
   10    stack<int, vector<int>  > x;    // 注意這與空格! ! !
   11    x.push(880);
   12    x.push(770);
   13    x.push(53);
   14    while(!x.empty()){
   15       cout << x.top();  x.pop();
   16    }
   17    cout << endl;
   18 }

D:\test> g++ mymainbb.cpp

D:\test> a.exe
53770880

D:\test> linenum < mymaincc.cpp
   01 // mymaincc.cpp -- CopyLeft by tsaiwn@csie.nctu.edu.tw
   02 // g++ mymaincc.cpp  ; ./a.out
   03 // ..這個版本要求用 <list> 做的 stack  (default 是用 deque 做的)
   04 using namespace std;   // 新的 #include 寫法須搭配這 std:: namespace
   05 //注意以下是 1999之後的 C++ 新寫法, 舊法使用 <iostream.h>
   06 #include <iostream>
   07 #include <stack>
   08 #include <list>
   09 int main( ){
   10    stack<int, list<int>  > x;    // 注意兩個大於之間有空格! 
   11    x.push(880);
   12    x.push(770);
   13    x.push(53);
   14    while(!x.empty()){
   15       cout << x.top();  x.pop();
   16    }
   17    cout << endl;
   18 }

D:\test> g++ mymaincc.cpp

D:\test> a.exe
53770880

D:\test>