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

http://blog.csdn.net/z84616995z/article/details/19204529

兩個棧實現一個隊列：

原理方法：用一個棧為主棧，一個棧為輔助棧存放臨時元素。

入隊：將元素依次壓入主棧

出隊：先檢測輔助棧是否為空，如果非空，那么直接彈出輔助棧頂元素，相當于出隊。如果為空，那么將主棧元素倒入到輔助棧中，然后彈出輔助棧頂元素。達到先進先出的目的。

以下是代碼：

[cpp]?view plain?copy
  1. //兩個個棧實現一個隊列??
  2. /*#include?<iostream>??
  3. #include?<time.h>??
  4. #include?<windows.h>??
  5. using?namespace?std;??
  6. #define?MAX?10??
  7. struct?stack??
  8. {??
  9. ????int?Array[MAX];??
  10. ????int?top;??
  11. };??
  12. struct?stack?s1,s2;??
  13. //初始化一個空棧??
  14. int?Init_Stack()??
  15. {??
  16. ????s1.top=s2.top?=?-1;//top為-1表示空棧??
  17. ????return?1;??
  18. }??
  19. //入隊??
  20. void?enqueue(int?Array[],int?x)??
  21. {??
  22. ????if?(s1.top==MAX-1)//檢測是否棧已滿??
  23. ????{??
  24. ????????cout<<"overflow!"<<endl;??
  25. ????}???
  26. ????else??
  27. ????{??
  28. ????????s1.top++;??
  29. ????????s1.Array[s1.top]=x;//將元素壓入主棧??
  30. ????}??
  31. }??
  32. //出隊??
  33. int?dequeue()??
  34. {??
  35. ????if?(s1.top==-1&&s2.top==-1)//如果主棧和輔助棧都是空的，那么就出現下溢。提示錯誤后返回??
  36. ????{??
  37. ????????cout<<"underflow!"<<endl;??
  38. ????????return?-1;??
  39. ????}??
  40. ???if?(s2.top==-1)//如果輔助棧為空，那么就循環地將主棧元素倒入輔助棧??
  41. ???{??
  42. ??????for?(int?i=s1.top;i>0;i--)??
  43. ??????{??
  44. ??????????s1.top--;s2.top++;??
  45. ??????????s2.Array[s2.top]=s1.Array[s1.top+1];??
  46. ??????}??
  47. ??????s1.top--;??
  48. ??????return?s1.Array[s1.top+1];//返回主棧最后一個元素作為出隊元素??
  49. ???}???
  50. ???else?//如果輔助棧不空，那么直接彈出輔助棧棧頂元素作為出隊元素??
  51. ???{??
  52. ???????s2.top--;??
  53. ???????return?s2.Array[s2.top+1];??
  54. ???}??
  55. }??
  56. void?main()??
  57. {??
  58. ????int?x=0;??
  59. ????Init_Stack();??
  60. ????srand(?(unsigned)time(?NULL?)?);??
  61. ????cout<<"數組中的數據入隊中。。。";??
  62. ????for(?int?j=0;?j?<=?100;?j++?)??????//?打印百分比???
  63. ????{??
  64. ????????cout.width(3);??
  65. ????????cout?<<?j?<<?"%";??
  66. ????????Sleep(40);??
  67. ????????cout?<<?"\b\b\b\b";//\b退格符號??
  68. ????}??
  69. ????????cout?<<?"\n\n";??
  70. ????cout<<"Array=";??
  71. ????for?(int?i=0;i<MAX;i++)??
  72. ????{??
  73. ????????x=rand()%100;??
  74. ????????cout<<x<<"?";??
  75. ????????enqueue(s1.Array,x);??
  76. ????}??
  77. ????cout<<endl;??
  78. ????cout<<"所有數據入隊完畢！"<<endl;??
  79. ????cout<<endl;??
  80. ????cout<<"數組中的數據出隊中。。。";??
  81. ????for(??j=0;?j?<=?100;?j++?)??????//?打印百分比???
  82. ????{??
  83. ????????cout.width(3);??
  84. ????????cout?<<?j?<<?"%";??
  85. ????????Sleep(40);??
  86. ????????cout?<<?"\b\b\b\b";//\b退格符號??
  87. ????}??
  88. ????cout?<<?"\n\n";??
  89. ????cout<<"Array=";??
  90. ????for?(?i=0;i<MAX;i++)??
  91. ????{??
  92. ????????cout<<dequeue()<<"?";??
  93. ????}??
  94. ????cout<<endl;??
  95. ????cout<<"所有數據出隊完畢！"<<endl;??
  96. ????cout<<endl;??
  97. ????enqueue(s1.Array,?56);??
  98. ????cout<<dequeue()<<endl;??
  99. ????cout<<dequeue()<<endl;??
  100. ????cout<<dequeue()<<endl;??
  101. ????enqueue(s1.Array,?65);??
  102. ????enqueue(s1.Array,?10);??
  103. ????enqueue(s1.Array,?32);??
  104. ????cout<<dequeue()<<endl;??
  105. ????cout<<dequeue()<<endl;??
  106. ????enqueue(s1.Array,?2);??
  107. ????cout<<dequeue()<<endl;????????
  108. }??

運行時間為O(n),在進行倒入操作時需要循環倒入，所以時間為n


兩個隊列實現一個棧：

原理方法：用一個隊列為主隊列，一個隊列為輔助隊列存放臨時元素。

入棧：將元素依次壓入主隊列

出棧：先將擁有n個元素的主隊列的其中的n-1個元素倒入輔助隊列，然后將原主隊列的最后剩下的一個元素彈出隊列，相當于出棧，這個時候，輔助隊列和主隊列進行交換，繼續進行剛才的出棧操作。

[cpp]?view plain?copy
  1. //兩個隊列實現一個棧??
  2. #include?<iostream>??
  3. #include?<time.h>??
  4. #include?<windows.h>??
  5. using?namespace?std;??
  6. #define?MAX?10???
  7. struct?queue??
  8. {??
  9. ????int?head;//聲明隊頭指針??
  10. ????int?tail;//聲明隊尾指針??
  11. ????int?length;//聲明隊列當前含有的元素個數??
  12. ????int?Array[MAX];//聲明數組所能容納的最大元素個數??
  13. };??
  14. struct?queue?q1,q2;?//聲明兩個隊列結構體全局變量??
  15. void?Init_queue(struct?queue?&q1)//初始化隊列??
  16. {??
  17. ????q1.head=q1.tail=1;//隊列初始時是從數組Array[1]開始的，所以其實Array[0]是數組最后一個元素，而不是Array[MAX-1]！這是需要注意的。??
  18. ????q1.length=1;??
  19. }??
  20. //入棧??
  21. int?push(int?Array[],int?x)??
  22. {??
  23. ???if?(q1.head==q1.tail+1)//進行入隊操作的前提判斷是否隊列已滿??
  24. ???{??
  25. ???????cerr<<"overflow!"<<endl;//若已滿，那么提示錯誤后返回。??
  26. ???????return?-1;??
  27. ???}??
  28. ???else??
  29. ???{??
  30. ???????if?(q1.length==0)//恢復隊列中沒有元素時的初始值q1.length=1;??
  31. ???????{??
  32. ???????????q1.length++;q2.length++;??
  33. ???????}??
  34. ???????q1.length++;q2.length++;//每次入隊數組元素個數+1??
  35. ???????if?(q1.tail==q1.length)//隊尾指針既然已經指向當前數組最后一個元素的下一個位置??
  36. ???????{??
  37. ???????????q1.tail=0;//那么元素只能插入Array[0]最后一個元素，原因在Init_queue函數注釋中。??
  38. ???????????q1.Array[q1.tail]=x;??
  39. ???????}???
  40. ???????else??
  41. ???????{??
  42. ???????????q1.Array[q1.tail]=x;??
  43. ???????????q1.tail++;??
  44. ???????????if?(q1.tail==MAX)//若隊尾指針指向數組最后一個元素的下一個位置??
  45. ???????????{??
  46. ???????????????q1.length--;q2.length--;//由于兩個隊列元素個數是從1開始的，那么主和輔助隊列元素個數已經超過MAX，所以需要調整為MAX，以便下次入隊時插入到Array[0]這個位置??
  47. ???????????}??
  48. ???????}??
  49. ???????return?q1.tail;??
  50. ???}??
  51. }??
  52. //出棧??
  53. int?pop()??
  54. {??
  55. ????int?x=0;??
  56. ????if?(q1.length<=0)//如果主隊列里面有0個元素，那么說明不能進行出隊（出棧）操作，直接返回錯誤提示??
  57. ????{??
  58. ????????cerr<<"underflow"<<endl;??
  59. ????????return?-1;??
  60. ????}???
  61. ????else??
  62. ????{??
  63. ????????if?(q1.tail==0)//通常情況需要返回的是隊頭指針作為出隊元素，那么這里為什么返回隊尾指針？因為我們需要用兩個隊列實現一個棧，那么有n個元素的主棧，把n-1個元素傳遞給輔助隊列后，最后入隊的也是將要出棧的元素肯定在主棧隊尾。??
  64. ????????{??
  65. ???????????x=q1.Array[q1.tail];//隊尾指針指向0時（其實指向的就是數組最后一位，因為初始化是從1開始的），直接返回Array[0]??
  66. ????????}??
  67. ????????else??
  68. ????????{??
  69. ???????????x=q1.Array[q1.tail-1];//隊尾指針指向其它時，由于隊尾指針總是指向數組最后一個數據的下一位，那么需要返回的是數組最后一個數據，所以要-1.??
  70. ????????}??
  71. ????????while(q1.tail!=q1.head)//隊頭和隊尾相等時，說明已經遍歷了整個隊列，所以退出循環??
  72. ????????{??
  73. ??????????????
  74. ????????????q2.Array[q2.tail]=q1.Array[q1.head];//將主棧的數據傳遞給輔助棧??
  75. ????????????if?(q2.tail==MAX)//由于需要循環遍歷隊列，所以當隊尾等于數組所能容納的最大元素個數時，隊尾指針自動調整到數組第一個位置。??
  76. ????????????{??
  77. ????????????????q2.tail=0;??
  78. ????????????}??
  79. ????????????else??
  80. ????????????{??
  81. ????????????????q2.tail++;??
  82. ????????????}??
  83. ????????????if?(q1.head==MAX)//和上面的if-else類似。??
  84. ????????????{??
  85. ????????????????q1.head=0;??
  86. ????????????}??
  87. ????????????else??
  88. ????????????{??
  89. ????????????????q1.head++;??
  90. ????????????}??
  91. ????????}??
  92. ????????if?(q1.tail==0)//如果隊尾指針等于0，自動指向當前主隊列的最后一個元素的下一個位置??
  93. ????????{??
  94. ????????????q1.tail=q1.length;//這樣在下次出隊時能夠返回隊列的最后一個元素。??
  95. ????????}??
  96. ????????else??
  97. ????????{??
  98. ????????????q1.tail--;//如果隊尾指針不等于0，那么當前主隊列隊尾下標指向下一個需要出隊的元素。??
  99. ????????}??
  100. ????????swap(q1,q2);//原來的主隊列轉換為輔助隊列，原來的輔助隊列轉換為主隊列。??
  101. ????????q1.tail=q2.tail;//由于轉換后，原主隊列隊尾下標變為輔助隊列隊尾下標，所以需要將當前輔助隊列隊尾下標傳遞給主隊列??
  102. ????????q2.head=q2.tail=1;//輔助隊列里的元素個數保持不變，然后其指針恢復為初始狀態。由于輔助隊列只是起到一個臨時保存隊列中數據的作用，所以每次主隊列有元素出隊，就需要初始化輔助隊列一下。??
  103. ????????q1.length--;q2.length--;//每次出隊后，需要將輔助和主隊列當前擁有的元素個數-1.??
  104. ????????return?x;//主隊列隊尾元素出隊（相當于出棧）??
  105. ????}??
  106. }??
  107. void?swap(struct?queue?&q1,struct?queue?&q2)//輔助隊列與主隊列之間轉換??
  108. {??
  109. ??struct?queue?temp;??
  110. ??temp=q1;??
  111. ??q1=q2;??
  112. ??q2=temp;??
  113. }??
  114. void?main()??
  115. {??
  116. ????int?x=0;??
  117. ????Init_queue(q1);??
  118. ????Init_queue(q2);??
  119. ????srand(?(unsigned)time(?NULL?)?);??
  120. ????cout<<"數組中的數據入棧中。。。";??
  121. ????for(?int?j=0;?j?<=?100;?j++?)??????//?這個循環就是一個看起來很酷的小程序，其實實際作用沒有。^_^??
  122. ????{??
  123. ????????cout.width(3);??
  124. ????????cout?<<?j?<<?"%";??
  125. ????????Sleep(40);??
  126. ????????cout?<<?"\b\b\b\b";//\b退格符號??
  127. ????}??
  128. ????cout?<<?"\n\n";??
  129. ????cout<<"Array=";??
  130. ????for?(int?i=0;i<MAX;i++)//對于開始q1和q2兩個空棧來說，設置q1為主棧，q2為輔助棧??
  131. ????{??
  132. ????????x=rand()%100;??
  133. ????????int?t=push(q1.Array,x);??
  134. ????????if?(t==-1)//既然隊列已滿，那么提示不能入棧后，自動跳出循環。??
  135. ????????{??
  136. ????????????break;??
  137. ????????}??
  138. ????????if?(q1.tail==0)??
  139. ????????{??
  140. ????????????cout<<q1.Array[q1.tail]<<"?";??
  141. ????????}???
  142. ????????else??
  143. ????????{??
  144. ????????????cout<<q1.Array[q1.tail-1]<<"?";??
  145. ????????}??
  146. ????}??
  147. ????cout<<endl;??
  148. ????cout<<"所有數據入棧完畢！"<<endl;??
  149. ????cout<<endl;??
  150. ????cout<<"數組中的數據出棧中。。。";??
  151. ????for(??j=0;?j?<=?100;?j++?)??????//?打印百分比???
  152. ????{??
  153. ????????cout.width(3);??
  154. ????????cout?<<?j?<<?"%";??
  155. ????????Sleep(40);??
  156. ????????cout?<<?"\b\b\b\b";//\b退格符號??
  157. ????}??
  158. ????cout?<<?"\n\n";??
  159. ????cout<<"Array=";??
  160. ????for?(?i=0;i<MAX;i++)??
  161. ????{??
  162. ????????cout<<pop()<<"?";??
  163. ????}??
  164. ????cout<<endl;??
  165. ????cout<<"所有數據出棧完畢！"<<endl;??
  166. ????cout<<endl;??
  167. }??
運行時間：由于需要將主隊列循環倒入到輔助隊列中，所以總時間為O(n).



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

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

相關文章

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.…
閱讀更多...
本原勾股數組

本原勾股數組

勾股數我們都很熟悉&#xff0c;a2b2c2&#xff0c;可是如何快速找到所有的勾股數組呢&#xff1f; 本原勾股數組a2b2c2性質&#xff1a; 1. a,b奇偶不同&#xff0c;c一定是奇數 2. 若b為偶數&#xff0c;c-b和cb一定是完全平方數 3. 設t>s>1,且均為奇數&#xff0c;則…
閱讀更多...
C++靜態成員函數訪問非靜態成員的幾種方法

C++靜態成員函數訪問非靜態成員的幾種方法

https://www.cnblogs.com/rickyk/p/4238380.html 大家都知道C中類的成員函數默認都提供了this指針&#xff0c;在非靜態成員函數中當你調用函數的時候&#xff0c;編譯器都會“自動”幫你把這個this指針加到函數形參里去。當然在C靈活性下面&#xff0c;類還具備了靜態成員和靜…
閱讀更多...
費馬大定理

費馬大定理

當n>3時方程 xnynzn沒有正整數解 結論很簡潔&#xff0c;剛才看了一下證明的歷史&#xff0c;我勒個去。。。。
閱讀更多...
類中的靜態成員函數訪問非靜態成員變量

類中的靜態成員函數訪問非靜態成員變量

http://blog.csdn.net/u011857683/article/details/52294353 1.思路&#xff1a; 靜態成員函數屬于類(通過類訪問&#xff0c;調用函數時沒有提供this指針)&#xff0c; 非靜態成員函數屬于實例&#xff08;通過對象訪問&#xff09;&#xff08;默認都提供了this指針&#xf…
閱讀更多...
Pollar Rho算法

Pollar Rho算法

原本是想把這個算法搞懂的&#xff0c;然后在網上看了又看&#xff0c;覺得&#xff0c;還是有時間再來看吧&#xff0c;我錯了。 看到了一個大佬的博客&#xff0c;順帶收集一下板子 這個板子可以求大數的最大的因子。 #define LL long long bool IsPrime(LL);//返回素性測…
閱讀更多...
最新文章

Copyright @ 2022~2023