【數據結構】（面試題）使用兩個棧實現一個隊列(詳細介紹)

http://blog.csdn.net/hanjing_1995/article/details/51539578

使用兩個棧實現一個隊列


思路一：

我們設定s1是入棧的，s2是出棧的。


入隊列，直接壓到s1即可


出隊列，先把s1中的元素倒入到s2中，彈出s2中的棧頂元素；再把s2的剩余元素全部倒回s1中。


wKioL1cMpjajUzcyAABT0frZ3KM694.png

缺點：

每次只要出棧一個元素就要將元素倒來倒去，麻煩！！！



思路2：

入隊列時：
如果s1為空，把s2中所有的元素倒出壓到s1中。否則直接壓入s1? ?

出隊列時：
如果s2不為空，把s2中的棧頂元素直接彈出。否則，把s1的所有元素全部彈出壓入s2中，再彈出s2的棧頂元素


wKiom1cMppLwMd0QAAB3LagChFk387.png



思路1無條件地每次都要將元素倒來倒去，思路2出隊時較思路1簡單



思路3：

我們設定s1是入棧的，s2是出棧的

入隊列：直接壓入元素至s1即可

出隊列：如果s2不為空，把s2中的棧頂元素直接彈出。否則，把s1的所有元素全部彈出壓入s2中，再彈出s2的棧頂元素


wKioL1cMp8HR1m6aAABLlSxXUHE848.png


相比于方法2，入隊直接壓入即可~

那么，我們可以看出，思路三最簡單，我們下面看下代碼。


代碼實現：

1）我們直接調用庫里的stack來實現。（一般調用庫里的就行了）

[cpp]?view plain?copy
  1. #define?_CRT_SECURE_NO_WARNINGS?1??
  2. #include<iostream>??
  3. using?namespace?std;??
  4. //兩個棧實現一個隊列??
  5. #include<stack>??
  6. ??
  7. template<class?T>??
  8. class?Queue??
  9. {??
  10. public:??
  11. ????void?appendTail(const?T&?x)??
  12. ????{??
  13. ????????s1.push(x);??
  14. ????}??
  15. ??
  16. ????void?deleteHead()??
  17. ????{??
  18. ??????????if?(s2.empty())??
  19. ??????????{??
  20. ??????????????while?(!s1.empty())??
  21. ??????????????{??
  22. ??????????????????s2.push(s1.top());??
  23. ??????????????????s1.pop();??
  24. ??????????????}??
  25. ??????????????cout?<<?s2.top()?<<?"??";??
  26. ??????????????s2.pop();??
  27. ??????????}??
  28. ??????????else??
  29. ??????????{??
  30. ???????????????cout?<<?s2.top()?<<?"??";??
  31. ???????????????s2.pop();????????????
  32. ??????????}???
  33. ????}??
  34. private:??
  35. ????stack<T>?s1;??
  36. ????stack<T>?s2;??
  37. ??????
  38. };??
  39. ??
  40. ??
  41. void?Test()??
  42. {??
  43. ????Queue<int>?q;??
  44. ????q.appendTail(1);??
  45. ????q.appendTail(2);??
  46. ????q.appendTail(3);??
  47. ????q.appendTail(4);??
  48. ????q.deleteHead();??
  49. ????q.deleteHead();??
  50. ????q.deleteHead();??
  51. ????q.deleteHead();??
  52. }??
  53. ??
  54. int?main()??
  55. {??
  56. ????Test();??
  57. ????system("pause");??
  58. ????return?0;??
  59. }??



2）自己實現棧實現。

[cpp]?view plain?copy
  1. #define?_CRT_SECURE_NO_WARNINGS?1??
  2. #include<iostream>??
  3. using?namespace?std;??
  4. ??
  5. #include<assert.h>??
  6. ??
  7. //直接實現Stack，也可以用適配器實現棧，或者用庫。??
  8. //將Stack基本功能實現如下：??
  9. template<class?T>??
  10. ??
  11. class?Stack??
  12. {??
  13. public:??
  14. ????Stack()??
  15. ????????:_array(NULL)??
  16. ????????,?_size(0)??
  17. ????????,?_capacity(0)??
  18. ????{}??
  19. ??
  20. ????Stack<T>(const?Stack<T>&?s)??
  21. ????????:?_array(new?T[s._capacity])??
  22. ????{??
  23. ????????swap(_array,?s._array);??
  24. ????????swap(_size,?s._size);??
  25. ????????swap(_capacity,?s._capacity);??
  26. ????}??
  27. ??
  28. ????Stack<T>&?operator=(const?Stack<T>&?s)??
  29. ????{??
  30. ????????if?(&s?!=?this)??
  31. ????????{??
  32. ????????????swap(_array,?s._array);??
  33. ????????????swap(_size,?s._size);??
  34. ????????????swap(_capacity,?s._capacity);??
  35. ????????}??
  36. ????????return?*this;??
  37. ????}??
  38. ??
  39. ????~Stack()??
  40. ????{??
  41. ????????if?(_array)??
  42. ????????{??
  43. ????????????delete[]?_array;??
  44. ????????????_array?=?NULL;??
  45. ????????}??
  46. ????}??
  47. ??
  48. ????void?_CheckCapacity()??
  49. ????{??
  50. ????????if?(_size?==?0)??
  51. ????????{??
  52. ????????????_capacity?=?3;??
  53. ????????????_array?=?new?T[_capacity];??
  54. ????????}??
  55. ????????if?(_size?>=?_capacity)??
  56. ????????{??
  57. ????????????_capacity?*=?2;??
  58. ????????????T*?tmp?=?new?T[_capacity];??
  59. ????????????for?(int?index?=?0;?index?<?_size;?index++)??
  60. ????????????{??
  61. ????????????????tmp[index]?=?_array[index];??
  62. ????????????}??
  63. ????????????delete[]?_array;??
  64. ????????????_array?=?tmp;??
  65. ????????}??
  66. ????}??
  67. ??
  68. ????void?Push(const?T&?x)??
  69. ????{??
  70. ????????_CheckCapacity();??
  71. ????????_array[_size++]?=?x;??
  72. ????}??
  73. ??
  74. ????void?Pop()??
  75. ????{??
  76. ????????if?(_size?==?0)??
  77. ????????{??
  78. ????????????return;??
  79. ????????}??
  80. ????????--_size;??
  81. ????}??
  82. ??
  83. ????size_t?Size()??
  84. ????{??
  85. ????????return?_size;??
  86. ????}??
  87. ??
  88. ????bool?Empty()??
  89. ????{??
  90. ????????return?Size()?==?0;??
  91. ????}??
  92. ??
  93. ????T&?Top()??
  94. ????{??
  95. ????????assert(_size?>?0);??
  96. ????????return?_array[_size?-?1];??
  97. ????}??
  98. ??
  99. private:??
  100. ????T*?_array;??
  101. ????size_t?_size;??
  102. ????size_t?_capacity;??
  103. };??
  104. ??
  105. ??
  106. template<class?T>??
  107. class?Queue??
  108. {??
  109. public:??
  110. ????void?InQueue(const?T&?x)??
  111. ????{??
  112. ????????s1.Push(x);??
  113. ????}??
  114. ??
  115. ????void?OutQueue()??
  116. ????{??
  117. ????????//棧s2為空，則將棧s1的元素全部倒入s2中，再彈出最上面的那個元素??
  118. ????????if?(s2.Empty())??
  119. ????????{??
  120. ????????????while?(!s1.Empty())??
  121. ????????????{??
  122. ????????????????s2.Push(s1.Top());??
  123. ????????????????s1.Pop();??
  124. ????????????}??
  125. ????????????s2.Pop();??
  126. ????????}??
  127. ??
  128. ????????//棧s2不為空，直接彈出元素??
  129. ????????else??
  130. ????????{??
  131. ????????????s2.Pop();??
  132. ????????}??
  133. ????}??
  134. ??
  135. ??????
  136. ????void?Print()????//打印隊列元素，分四種情況。??
  137. ????{??
  138. ????????if?(s1.Empty()?&&?s2.Empty())??
  139. ????????{??
  140. ????????????cout?<<?"The?Queue?is?Empty!";??
  141. ????????}??
  142. ??
  143. ????????else?if?(!s1.Empty()?&&?s2.Empty())??
  144. ????????{??
  145. ????????????while?(!s1.Empty())??
  146. ????????????{??
  147. ????????????????s2.Push(s1.Top());??
  148. ????????????????s1.Pop();??
  149. ????????????}??
  150. ??
  151. ????????????while?(!s2.Empty())??
  152. ????????????{??
  153. ????????????????cout?<<?s2.Top()?<<?"??";??
  154. ????????????????s2.Pop();??
  155. ????????????}??
  156. ????????}??
  157. ??
  158. ????????else?if?(s1.Empty()?&&?!s2.Empty())??
  159. ????????{??
  160. ????????????while?(!s2.Empty())??
  161. ????????????{??
  162. ????????????????cout?<<?s2.Top()?<<?"??";??
  163. ????????????????s2.Pop();??
  164. ????????????}??
  165. ????????}??
  166. ??
  167. ????????else??
  168. ????????{??
  169. ????????????while?(!s2.Empty())??
  170. ????????????{??
  171. ????????????????cout?<<?s2.Top()?<<?"??";??
  172. ????????????????s2.Pop();??
  173. ????????????}??
  174. ??
  175. ????????????while?(!s1.Empty())??
  176. ????????????{??
  177. ????????????????s2.Push(s1.Top());??
  178. ????????????????s1.Pop();??
  179. ????????????}??
  180. ??
  181. ????????????while?(!s2.Empty())??
  182. ????????????{??
  183. ????????????????cout?<<?s2.Top()?<<?"??";??
  184. ????????????????s2.Pop();??
  185. ????????????}??
  186. ????????}??
  187. ????????cout?<<?endl;??
  188. ????}??
  189. ??
  190. private:??
  191. ????Stack<T>?s1;????//入隊??
  192. ????Stack<T>?s2;????//出隊??
  193. };??
  194. ??
  195. ??
  196. ??
  197. //測試兩個棧實現一個隊列??
  198. void?Test1()??
  199. {??
  200. ????Queue<int>?q1;??
  201. ????q1.InQueue(1);??
  202. ????q1.InQueue(2);??
  203. ????q1.InQueue(3);??
  204. ????q1.InQueue(4);??
  205. ????/*q1.Print();*/??
  206. ??
  207. ????q1.OutQueue();??
  208. ????/*q1.Print();*/??
  209. ????q1.InQueue(5);??
  210. ????q1.InQueue(6);??
  211. ????q1.InQueue(7);??
  212. ??
  213. ????q1.Print();??
  214. }??
  215. ??
  216. ??
  217. ??
  218. int?main()??
  219. {??
  220. ????Test1();??
  221. ????system("pause");??
  222. ????return?0;??
  223. }??


(1個細節)：


????? 注意再將元素倒入另一個棧時，代碼并不是先pop,再push。因為這樣push后元素就找不到了。因此要先訪問到棧頂元素top,再push,而后pop。

本文出自 “Han Jing's Blog” 博客，請務必保留此出處http://10740184.blog.51cto.com/10730184/1763006


本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383907.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383907.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383907.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

POJ 1006 Biorhythms

POJ 1006 Biorhythms

中國剩余定理的模板題 只是有一個問題就是求出來Xk*MR中的R比給定的日期還大&#xff0c;但是如果負數的整除就不是向下取整了&#xff0c;為了解決這個問題&#xff0c;我們將R減小M&#xff0c;這樣總是正的&#xff0c;求出來的就沒有什么問題。 #include <iostream>…
閱讀更多...
POJ 3696 歐拉函數+快速冪

POJ 3696 歐拉函數+快速冪

題目的意思大概就是問是否存在一串全是8的數字是L的倍數 直接想沒有什么想法&#xff0c;要想到用簡潔的形式將這個數字表示出來&#xff0c;對于每一位都是8的數字我們可以用 X8*(10k-1)/9的形式表示出來&#xff0c;那么題目的意思就是求X使L|X&#xff0c;我們先處理一下8和…
閱讀更多...
兩個棧實現一個隊列，兩個隊列實現一個棧

兩個棧實現一個隊列，兩個隊列實現一個棧

http://blog.csdn.net/zw_1510/article/details/51927554 問題1&#xff1a;用兩個棧實現一個隊列&#xff0c;實現隊列的push和delete操作 棧的特性是先進后出&#xff08;FILO&#xff09;,隊列的特性是先進先出&#xff08;FIFO&#xff09;,在實現delete時&#xff0c;我們…
閱讀更多...
C++:String的寫時拷貝

C++:String的寫時拷貝

String的寫時拷貝 //test.h #pragma once#include <iostream> #include <string.h> #include <cstdio> #include <assert.h> using namespace std;#define TESTHEADER printf("\n%s\n", __FUNCTION__) class String { public:String(const …
閱讀更多...
兩個棧實現一個隊列與兩個隊列實現一個棧

兩個棧實現一個隊列與兩個隊列實現一個棧

http://blog.csdn.net/z84616995z/article/details/19204529 兩個棧實現一個隊列&#xff1a; 原理方法&#xff1a;用一個棧為主棧&#xff0c;一個棧為輔助棧存放臨時元素。 入隊&#xff1a;將元素依次壓入主棧 出隊&#xff1a;先檢測輔助棧是否為空&#xff0c;如果非空&a…
閱讀更多...
UVa11426——歐拉函數

UVa11426——歐拉函數

發現對于gcd問題要多和歐拉函數聯系在一起&#xff0c;雖然有時候并不是互質&#xff0c;但是我們知道有多少互質的然后根據互質的數目就能解決很多個gcd的問題 對于這道題目&#xff0c;題目要求的是所有數對的gcd的和&#xff0c;直接思考的話有難度。但是我們如果聯想到歐拉…
閱讀更多...
C++:繼承和多態

C++:繼承和多態

虛函數:只有類的成員函數才能定義為虛函數 虛函數 在類的成員函數前面加上一個 virtual 關鍵字, 此時這個成員函數就叫做虛函數 虛函數 當在子類中定義了一個與父類完全相同的虛函數的時候,此時就叫做子類的虛函數重寫了父類的虛函數 構成多態的條件 派生類重寫基類的虛函數…
閱讀更多...
POJ 1061擴展歐幾里得

POJ 1061擴展歐幾里得

擴展歐幾里得的模板題&#xff0c;需要注意的是為了得到一個最小正數解我們要使axbyc中的a,b都是正數 #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<cmath> #include<ctim…
閱讀更多...
C++::探索對象模型

C++::探索對象模型

前面我們已經知道, 在沒有虛函數的時候, 對象的大小就是對應的成員變量的大小, 而成員函數不會占用對象的空間, 今天我們來討論一下, 當類中定義了虛函數的時候, 此時對象的大小以及對象模型 非繼承下的對象模型 class Base { public:virtual void func1(){cout << &qu…
閱讀更多...
auto_ptr

auto_ptr

#include <iostream> #include <memory> using namespace std;class A { public:A(){cout<<"構造"<<endl;}~A(){cout<<"A析構"<<endl;}void fun(){cout<<"A::fun"<<endl;} };class PA { public…
閱讀更多...
POJ 2142——擴展歐幾里得

POJ 2142——擴展歐幾里得

題目是很裸的擴展歐幾里得&#xff0c;但是對x,y有限制條件&#xff0c;要求所有x,y中abs(x)abs(y)最小&#xff0c;在這個條件下要求abs(a* x)abs(b* y)最小 顯然我們需要用擴展歐幾里得求得一組解&#xff0c;問題在于如何處理這組解以得到符合條件的值。 我是這樣處理的&a…
閱讀更多...
C++::模板

C++::模板

模板的簡單介紹 C中模板是為了能夠使得函數或者類實現范型編程的目的, 同時C模板的出現是為了避免代碼的冗余 舉個例子 void Swap(int& a, int& b) {int tmp a;b a;a b; } void Swap(char& a, char& b) {char tmp a;b a;a b; } 上面的函數除了類型不…
閱讀更多...
Linux select TCP并發服務器與客戶端編程

Linux select TCP并發服務器與客戶端編程

http://blog.csdn.net/szkbsgy/article/details/10558881 [cpp] view plaincopy <span style"font-size:18px;">服務端&#xff1a; #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/time.h> #i…
閱讀更多...
BZOJ - 2186 歐拉函數

BZOJ - 2186 歐拉函數

題目的意思大概是求1~N!中和M&#xff01;互質的數的個數 因為對歐拉函數理解不夠深刻所以我是分析得到結果的&#xff1a; 當N<M的時候顯然符合要求的數的個數為0&#xff1b; 當N>M的時候我們要求的是1~N!中不含1 ~M的素因子的的數的個數&#xff0c;結合歐拉函數的…
閱讀更多...
多態相關概念

多態相關概念

多態相關注意事項 所謂的多態就是指函數有多中狀態, 在C中通常是通過父類指針指向子類對象的方法實現多態, 這樣父類可以通過子類的類型調用不同的方法. 即實現一個接口多種方法, 多態的引用是為了實現接口復用 在 C中多態是通過虛函數來實現的. 子類通過對父類相關接口進行重…
閱讀更多...
模板實現棧隊列以及鏈表

模板實現棧隊列以及鏈表

模板實現鏈表 //test.h #include <iostream> #include <cstdio> #include <assert.h> using namespace std;template <class T> struct ListNode {ListNode* _prev;ListNode* _next;T _data;ListNode(const T& x):_prev(NULL),_next(NULL),_data(…
閱讀更多...
基于Visual C++2013拆解世界五百強面試題--題5-自己實現strstr

基于Visual C++2013拆解世界五百強面試題--題5-自己實現strstr

http://blog.csdn.net/itcastcpp/article/details/12907371 請用C語言實現字符串的查找函數strstr&#xff0c; 找到則返回子字符串的地址&#xff0c;沒有找到返回為空&#xff0c;請用數組操作與指針操作實現 看到題目想到最簡單的方法就是母字符串和子字符串比較&#xff0c…
閱讀更多...
卡特蘭數

卡特蘭數

卡特蘭數的引入與n邊形分成三角形的個數有關&#xff1a; 我們令f[n]表示n邊形可以分成的三角形的個數&#xff0c;特殊的&#xff0c;令f[2]1 我們考慮以頂點1頂點的一個三角形&#xff0c;假設用的是n邊形的k-k1邊&#xff0c;那么這種情況的方案數就是f[k]?f[n?k1]f[k]*…
閱讀更多...
軟件測試相關概念

軟件測試相關概念

什么叫軟件測試 軟件測試就是測試產品沒有錯誤,同時又證明軟件是可以正確運行的 測試和調試的區別 調試一般都在開發期間 ,測試是伴隨著整個軟件的生命周期, 調試是發現程序中問題并且解決問題, 測試是發現程序中的缺陷 軟件測試的目的和原則 目的:驗證軟件有沒有問題 原…
閱讀更多...
Linux 線程信號量同步

Linux 線程信號量同步

https://www.cnblogs.com/jiqingwu/p/linux_semaphore_example.html 信號量和互斥鎖(mutex)的區別&#xff1a;互斥鎖只允許一個線程進入臨界區&#xff0c;而信號量允許多個線程同時進入臨界區。 不多做解釋&#xff0c;要使用信號量同步&#xff0c;需要包含頭文件semaphore.…
閱讀更多...
最新文章

Copyright @ 2022~2023