您的位置: 首页  >  文章  >  【数据结构】（面试题）使用两个栈实现一个队列(详细介绍)

【数据结构】（面试题）使用两个栈实现一个队列(详细介绍)

分类: 文章 • 2023-11-18 10:01:28

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

使用两个栈实现一个队列


思路一：

我们设定s1是入栈的，s2是出栈的。


入队列，直接压到s1即可


出队列，先把s1中的元素倒入到s2中，弹出s2中的栈顶元素；再把s2的剩余元素全部倒回s1中。


【数据结构】（面试题）使用两个栈实现一个队列(详细介绍)

缺点：

每次只要出栈一个元素就要将元素倒来倒去，麻烦！！！



思路2：

入队列时：
如果s1为空，把s2中所有的元素倒出压到s1中。否则直接压入s1   

出队列时：
如果s2不为空，把s2中的栈顶元素直接弹出。否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素


【数据结构】（面试题）使用两个栈实现一个队列(详细介绍)



思路1无条件地每次都要将元素倒来倒去，思路2出队时较思路1简单



思路3：

我们设定s1是入栈的，s2是出栈的

入队列：直接压入元素至s1即可

出队列：如果s2不为空，把s2中的栈顶元素直接弹出。否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素


【数据结构】（面试题）使用两个栈实现一个队列(详细介绍)


相比于方法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


相关推荐