資料結構關於堆疊Stack例題、佇列Queue例題筆記

堆疊Stack

觀念：
LIFO(last in first out) 後進先出

常用方法：

stack<int> sk 建立一個int型別的stack

sk.size()         堆疊元素數量

sk.empty() 判斷堆疊是否為空

sk.push(x) 從堆疊「頂端」加入一個元素x

sk.pop()         刪除堆疊頂端元素

sk.top()         取得堆疊頂端元素

題目：

EX_01：10進位轉2進位(以STL stack實作)。11->1011

程式碼：

#include <iostream>

#include <stack>

using namespace std;

int main() {

    stack<int> sk;   

    int n;

    cin >> n;

    while (n>0) {                     // n大於0 

    sk.push(n%2);               // 將n除以2的餘數push進堆疊 

    n=n/2;                           // 將n除以2 

}

while (!sk.empty()) {    // 堆疊內還有元素 

cout << sk.top();   // 印出堆疊頂端元素 

sk.pop();                // 將堆疊頂端元素移除 

}

cout <<endl;

}

佇列Queue

觀念：

FIFO(first in first out) 先進先出

常用的方法

queue<int> qe        建立一個int型別的queue

qe.size()                佇列元素數量

qe.empty()        判斷是否為空

qe.push(x)        從佇列「後端」加入一個元素x

qe.pop()                從「前端」刪除一個元素

qe.front()                取得前端元素

qe.back()                取得後端元素

題目：

EX_02：ZeroJudge e183: 10940 - Throwing cards away II  

給你一疊有1~n編號的牌(1在最上面，n在最下面)，在牌數大於1的時候執行以下操作：「丟掉最上面的牌，並把現在最上面的的牌放到最下面。」

求最後剩下的那張牌編號為?(7->6、10->4)

程式碼：

#include <iostream>

#include <queue>

using namespace std;

int main() {

queue<int> q;

int i,n,p;

cin >> n;

for(i=1;i<=n;i++) {

q.push(i);           // 將牌的編號(1 2 3 …)依序push入佇列

}

while(q.size() > 1) {   // 當佇列size>1時繼續執行

q.pop();            // 將最上面的牌丟掉

q.push(q.front());  // 將次張牌重新放入佇列尾端

q.pop();            // 將次張牌丟掉

}

cout << q.front();      // 印出剩下的那張牌

}

資料來源：
1.資料結構與演算法(使用C++)