队列与栈的相互实现

曾经终败给现在 2022-10-02 15:55 109阅读 0赞

**Problem:**  
　　如何仅用队列结构实现栈结构？

**Solution:**  
　　队列是先进先出，而栈是先进后出

故使用两个队列来实现一个栈的功能

一个存放原来的数据，

另一个做数据倒腾的容器

**Code：**

**　　**

1 class QueueToStack
     2 {
     3 private:
     4     queue<int>Data, Temp;
     5 
     6 public:
     7     void Push(int a)
     8     {
     9         Data.push(a);
    10     }
    11     int Top()
    12     {
    13         int DataSize = Data.size();
    14         for (int i = 0; i < DataSize - 1; ++i)//将data的数据倒腾进temp,留一个就是top了
    15         {
    16             Temp.push(Data.front());
    17             Data.pop();
    18         }
    19         int res = Data.front();
    20         Temp.push(Data.front());
    21         Data.pop();
    22 
    23         auto tem = Data;
    24         Data = Temp;
    25         Temp = Data;//交换回来，始终保持数据在Data中
    26 
    27         return res;//返回top值
    28     }
    29 
    30     void Pop()
    31     {
    32         int DataSize = Data.size();
    33         for (int i = 0; i < DataSize - 1; ++i)//将data的数据倒腾进temp,留一个就是top了
    34         {
    35             Temp.push(Data.front());
    36             Data.pop();
    37         }
    38         Data.pop();//删除top值
    39 
    40         auto tem = Data;
    41         Data = Temp;
    42         Temp = Data;//交换回来，始终保持数据在Data中
    43     }
    44     
    45 };

**Problem2:**  
　　 如何仅用栈结构实现队列结构？

**解题思路：**  
 　　同样的，使用两个栈Data,Temp来实现列表功能  
　　 Data用来存放数据，Temp用来倒腾数据

**Code:**

**　　**

1 class StackToQueue
     2 {
     3 private:
     4     stack<int>Data, Temp;
     5 
     6 public:
     7     void Push(int a)
     8     {
     9         Data.push(a);
    10     }
    11     int Front()
    12     {
    13         while (!Data.empty())
    14         {
    15             Temp.push(Data.top());
    16             Data.pop();
    17         }
    18         int res = Temp.top();
    19         while (!Temp.empty())
    20         {
    21             Data.push(Temp.top());
    22             Temp.pop();
    23         }
    24         return res;
    25     }
    26 
    27     void Pop()
    28     {
    29         while (!Data.empty())
    30         {
    31             Temp.push(Data.top());
    32             Data.pop();
    33         }
    34         Temp.pop();
    35         while (!Temp.empty())
    36         {
    37             Data.push(Temp.top());
    38             Temp.pop();
    39         }
    40     }
    41 };

**测试代码：**

**　　**

1 void Test()
     2 {
     3     QueueToStack myStack;
     4     myStack.Push(1);
     5     myStack.Push(2);
     6     myStack.Push(3);
     7     myStack.Push(4);
     8     myStack.Push(5);
     9     myStack.Push(6);
    10 
    11     cout << myStack.Top() << endl;
    12     myStack.Pop();
    13     cout << myStack.Top() << endl;
    14     myStack.Pop();
    15     cout << myStack.Top() << endl;
    16     myStack.Push(10);
    17     myStack.Push(12);
    18     cout << myStack.Top() << endl;
    19 
    20 
    21 
    22     cout << "=========================" << endl;
    23     cout << "=========================" << endl;
    24     cout << "=========================" << endl;
    25 
    26     StackToQueue myQueue;
    27     myQueue.Push(1);
    28     myQueue.Push(2);
    29     myQueue.Push(3);
    30     myQueue.Push(4);
    31     myQueue.Push(5);
    32     myQueue.Push(6);
    33 
    34     cout << myQueue.Front() << endl;
    35     myQueue.Pop();
    36     cout << myQueue.Front() << endl;
    37     myQueue.Pop();
    38     cout << myQueue.Front() << endl;
    39 
    40     myQueue.Push(7);
    41     myQueue.Push(8);
    42 
    43     cout << myQueue.Front() << endl;
    44 
    45 }

转载于:https://www.cnblogs.com/zzw1024/p/10988243.html