資料結構關於堆疊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++)

Z 字型編排問題

 問題描述：8X8的矩陣，有著如下編排：

今天要將編排的方式寫成C++的程式碼，分析如下：

下方圖片內容檔：Z 字型編排問題

換句話說，只有四種動作。

資料來源：

1.算法：Z字型（Zigzag）編排

C++標準函式庫_第五章Standard Template Library標準模板庫_讀後心得與重點整理

容器(圖片摘錄至資料來源1的P.104)

檔名：vector1.cpp

檔案內容：

#include <iostream>

#include <vector>

using namespace std;

int main() {

   vector<int> col1;

   int i;

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

    col1.push_back(i);

   }

   cout << col1.size() <<endl;

   for(i=0;i<col1.size();++i) {

    cout << col1[i] <<' ';

   }

   cout << endl;

}

檔名：deque1.cpp

檔案內容：

#include <iostream>

#include <deque>

using namespace std;

int main() {

deque<int> col1;

int i;

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

    col1.push_front(i);

}

for (i=0;i<col1.size();i++) {

cout << col1[i] <<' ';

}

cout << endl;

}

檔名：list1.cpp

檔案內容：

#include <iostream>

#include <list>

using namespace std;

int main() {

   list<char> coll;

   for (char c='a';c<='z';c++) {

    coll.push_back(c);

   }

   while(!coll.empty()) {

    cout << coll.front() <<' ';

    coll.pop_front();

    }

    cout << endl;

   for (char c='a';c<='z';c++) {

    coll.push_back(c);

   }

   while(!coll.empty()) {

    cout << coll.back() <<' ';

    coll.pop_back();

    }

    cout << endl;

}

檔名：list2.cpp

檔案內容：

#include <iostream>

#include <list>

using namespace std;

int main() {

   list<char> coll;

   list<char>::const_iterator pos;

   for (char c='a';c<='z';c++) {

    coll.push_back(c);

   }

   for (pos=coll.begin();pos!=coll.end();pos++) {

    cout << *pos <<' ';

   }

   cout<<endl;

}

檔名：set1.cpp

檔案內容：

#include <iostream>

#include <set>

using namespace std;

int main() {

    set<int> coll;

    set<int>::const_iterator pos;

    for (int a=1;a<10;++a) {

    coll.insert(a);

}

    coll.insert(1);

    coll.insert(3);

    coll.insert(5);

    for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos <<' ';

}

cout << endl;     

}

檔名：mmap1.cpp

檔案內容：

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

   typedef multimap<int,string> IntStringMMap;

   IntStringMMap coll;

   coll.insert(make_pair(5,"tagged"));

   coll.insert(make_pair(2,"a"));

   coll.insert(make_pair(1,"this"));

   coll.insert(make_pair(4,"of"));

   coll.insert(make_pair(6,"strings"));

   coll.insert(make_pair(1,"is"));

   coll.insert(make_pair(3,"multimap"));

   IntStringMMap::iterator pos;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << pos->second <<' ';

   }

   cout << endl;

   

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << (*pos).second <<' ';

   }

   cout << endl;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << pos->first <<' ';

   }

   cout << endl;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << (*pos).first <<' ';

   }

   cout << endl;

}

檔名：map1.cpp

檔案內容：

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

   typedef map<string,float> StringFloatMap;

   StringFloatMap coll;

   coll["VAT"]=0.15;

   coll["Pi"]=3.1415;

   coll["an arbitrary number"] = 4983.223;

   coll["Null"]=0;

   StringFloatMap::iterator pos;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << "key: \"" << pos->first << "\" "

    << "value: " << pos->second << endl;

   }

}

檔名：algo1.cpp

檔案內容：

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

   vector<int> coll;

   vector<int>::iterator pos;

   

   coll.push_back(2);

   coll.push_back(5);

   coll.push_back(4);

   coll.push_back(1);

   coll.push_back(6);

   coll.push_back(3);

   

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos << ' '; 

   }

   cout << endl;

   

   pos = min_element(coll.begin(),coll.end());

   cout << "min: " << *pos << endl;

   cout << "min: " << *min_element(coll.begin(),coll.end()) << endl;

   pos = max_element(coll.begin(),coll.end());

   cout << "max: " << *pos << endl;

   cout << "max: " << *max_element(coll.begin(),coll.end()) << endl;

   

   sort(coll.begin(),coll.end());

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos << ' '; 

   }

   cout << endl;

   

   pos = find(coll.begin(),coll.end(),3);

   cout << *pos << endl;

   

   reverse(pos,coll.end());

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos << ' '; 

   }

   cout << endl;

}

檔名：find1.cpp

檔案內容：

#include <iostream>

#include <list>

#include <algorithm>

using namespace std;

int main() {

  list<int> coll;

  list<int>::iterator pos;

  

  for (int i=20;i<=40;++i) {

  coll.push_back(i);

  }

  pos = find(coll.begin(),coll.end(),3);

  cout << "pos = "<<*pos <<endl;

  reverse(pos,coll.end());

  for (pos = coll.begin();pos!=coll.end();++pos) {

  cout << *pos <<' ';

  }

  cout << endl;

  

  list<int>::iterator pos25,pos35,pos30;

  

  pos25 = find(coll.begin(),coll.end(),25);

  cout << "pos25: " << *pos25 << endl;

  pos35 = find(coll.begin(),coll.end(),35);

  cout << "pos35: " << *pos35 << endl;

  

  cout << "max: " << *max_element(pos25,pos35) << endl;

  cout << "max: " << *max_element(pos25,++pos35) << endl;

  

  ++pos35;

  pos30 = find(pos25,pos35,30);

  cout << "pos30 = " << *pos30 << endl;

}

檔名：copy2.cpp

檔案內容：

#include <iostream>

#include <vector>

#include <list>

#include <deque>

#include <algorithm>

using namespace std;

int main() {

   list<int> coll1;

   list<int>::iterator pos1;

   vector<int> coll2;

   vector<int>::iterator pos2; 

   

   for (int i=1;i<=9;++i) {

    coll1.push_back(i);

   }

   cout <<"coll1： " << endl;

   for(pos1=coll1.begin();pos1!=coll1.end();++pos1) {

    cout << *pos1 <<' ';

   }

   cout << endl;

   

   coll2.resize(coll1.size());

   

   copy(coll1.begin(),coll1.end(),coll2.begin());

   

   cout <<"coll2： " << endl;

   for(pos2=coll2.begin();pos2!=coll2.end();++pos2) {

    cout << *pos2 <<' ';

   }

   cout << endl;

   

   deque<int> coll3(coll1.size());

   deque<int>::iterator pos3;

   

   copy(coll1.begin(),coll1.end(),coll3.begin());

   

   cout <<"coll3： " << endl;

   for(pos3=coll3.begin();pos3!=coll3.end();++pos3) {

    cout << *pos3 <<' ';

   }

   cout << endl;

}

檔名：vector101.cpp

檔案內容：

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <iterator>

using namespace std;

int main() {

   vector<string> sentence;

   sentence.reserve(5);

   sentence.push_back("Hello,");

   sentence.push_back("how");

   sentence.push_back("are");

   sentence.push_back("you");

   sentence.push_back("?");

   

   copy (sentence.begin(),sentence.end(),ostream_iterator<string>(cout," "));

   cout << endl;

   cout << "max_size()： " << sentence.max_size() << endl;

   cout << " size()： " << sentence.size() << endl;

   cout << " capacity()： " << sentence.capacity() << endl;

   

   swap (sentence[1],sentence[3]);

   sentence.insert( find(sentence.begin(),sentence.end(),"?"),"always");

   

   copy (sentence.begin(),sentence.end(),ostream_iterator<string>(cout," "));

   cout << endl;

   cout << "max_size()： " << sentence.max_size() << endl;

   cout << " size()： " << sentence.size() << endl;

   cout << " capacity()： " << sentence.capacity() << endl;

}

檔名：deque101.cpp

檔案內容：

#include <iostream>

#include <deque>

#include <string>

#include <algorithm>

#include <iterator>

using namespace std;

int main() {

deque<string> col1;

col1.assign(3,string("string"));

col1.push_back("last string");

col1.push_front("first string");

copy(col1.begin(),col1.end(),ostream_iterator<string>(cout,"\n"));

cout << endl;

col1.pop_front();

col1.pop_back();

copy(col1.begin(),col1.end(),ostream_iterator<string>(cout,"\n"));

cout << endl;

cout << col1.size();

cout << endl;

for (int i=1;i<col1.size();++i) {

col1[i] = "another " + col1[i]; 

}

col1.resize(4,"resized string");

copy(col1.begin(),col1.end(),ostream_iterator<string>(cout,"\n"));

}

檔名：map1.cpp

檔案內容：

檔名：map1.cpp

檔案內容：

資料來源：
1.C++標準函式庫(The C++ Standard Library by Josuttis)