首页 > 代码库 > 每天一个小算法（6）---- 通过两个栈实现一个队列

每天一个小算法（6）---- 通过两个栈实现一个队列

2024-07-08 14:45:13   225人阅读

这个算法也很简单，定义两个栈m_aStack、m_bStack，m_aStack负责push()数据，m_bStack负责front()数据。

思路：每一次front()取数据都会检查一下m_bStack是否为空，为空则把m_aStack的所有数据pop()出来push()到m_bStack中。

 

 

因为STL里有stack，直接拿来用了，代码使用C++，在linux/g++下编译运行成功：

  1 #include <stack>  2 #include <stdio.h>  3 #include <stdlib.h>  4 #include <time.h>  5   6 class Fifo  7 {  8 public:  9     const int size() const; 10     const bool empty() const; 11     const int front(); 12     void push(int element); 13     void print() const; 14 private: 15     std::stack<int> m_aStack; 16     std::stack<int> m_bStack; 17 }; 18  19 const int Fifo::size() const 20 { 21     return m_aStack.size() + m_bStack.size(); 22 } 23  24 const bool Fifo::empty() const 25 { 26     return m_aStack.empty() & m_bStack.empty(); 27 } 28  29 const int Fifo::front() 30 { 31     if( empty() ) 32         return 0; 33  34     if ( m_bStack.empty() ) 35     { 36         while ( !m_aStack.empty() ) 37         { 38             m_bStack.push(m_aStack.top()); 39             m_aStack.pop(); 40         } 41     } 42  43     int tmp = m_bStack.top(); 44     m_bStack.pop(); 45     return tmp; 46 } 47  48 void Fifo::push(int element) 49 { 50     m_aStack.push(element); 51 } 52  53 void Fifo::print() const 54 { 55     if ( empty() ) 56         return; 57  58     std::stack<int> tAStack = m_aStack; 59     std::stack<int> tBStack = m_bStack; 60  61     printf("the elements of the m_aStack:\t"); 62     while ( !tAStack.empty() ) 63     { 64         printf("%d ", tAStack.top()); 65         tAStack.pop();         66     } 67     printf("\n"); 68      69     printf("the elements of the m_bStack:\t"); 70     while ( !tBStack.empty() ) 71     { 72         printf("%d ", tBStack.top());         73         tBStack.pop();         74     } 75     printf("\n"); 76  77 } 78  79 int main(int argc, char const *argv[]) 80 { 81     Fifo fifo; 82     srand((int)time(0)); 83     for ( int i=0; i< 100; ++i ) 84     { 85         if ( (rand() & 1) == 0 ) 86         { 87             int tmp = rand()%100; 88             printf("\npush %d to fifo\n", tmp); 89             fifo.push(tmp); 90             fifo.print(); 91         } 92         else 93         { 94             printf("\nthe front of the fifo: %d\n", fifo.front());             95             fifo.print(); 96         } 97     } 98  99     return 0;100 }
View Code

 


联系
我们