数据结构复习之用两个栈模拟队列操作

电玩女神 2022-06-18 08:52 107阅读 0赞

![复制代码][copycode.gif]

#include<iostream> 
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #define MAXSIZE 100
    using namespace std;
    
    struct Stack{
        int s[MAXSIZE];
        int top=0;
        bool stackOverFlow(){
            if(top >= MAXSIZE)
                return true;
            return false; 
        }
        bool push(int x){
            if(stackOverFlow())
                return false;
            s[top++] = x;
        } 
        bool isEmpty(){
            return top==0 ? true : false;
        }
        bool pop(int &x){
            if(isEmpty()) return false;
            x = s[--top];
            return true;
        }
        
        int size(){
            return top;
        } 
    };
    
    struct Queue{
      //这种实现方式也是最容易想到的 
        Stack s1, s2;//s1用于队列的push和pop， s2用于是的缓冲（将s1中的数据进行反转，就成了队列的顺序） 
        bool push(int x){
            if(s1.stackOverFlow()) return false;
            int e;
            while(!s1.isEmpty()){
                s1.pop(e);
                s2.push(e);
            } 
            s1.push(x);
            while(!s2.isEmpty()){
                s2.pop(e);
                s1.push(e);
            }
            return true;
        }
        bool pop(int &x){
            if(s1.isEmpty()) return false;
            s1.pop(x);
            return true;
        }
        
        bool isEmpty(){
            return s1.size() == 0 ? true : false;
        }
        
        int size(){
            return s1.size();
        }
    };
    
    struct Queue_x{
      //这种方式的空间利用率更大一些 
        Stack s1, s2;//s1用于队列的push， s2用于队列的pop 
        bool push(int x){
            if(!s1.stackOverFlow()) {
                s1.push(x);
                return true;
            }
            if(s1.stackOverFlow() && !s2.isEmpty()) return false;
            int e;
            while(!s1.isEmpty()){
                s1.pop(e);
                s2.push(e);
            }
            s1.push(x);
            return true;
        }
        bool pop(int &x){
            if(!s2.isEmpty()){
                s2.pop(x);
                return true;
            }
            if(s1.isEmpty()) return false;
            int e;
            while(!s1.isEmpty()){
                s1.pop(e);
                s2.push(e);
            }
            s2.pop(x);
            return true;
        }
        
        bool isEmpty(){
            return s1.size() == 0 && s2.size() == 0;
        }
        
        int size(){
            return s1.size() + s2.size();
        }
    };
    
    int main(){
        Queue q;
        for(int i=0; i<10; ++i)
            q.push(i);
        int x;
        for(int i=0; i<10; ++i){
            q.pop(x);
            cout<<x<<endl;
            q.push(100);
        }
        cout<<"队列的当前大小:"<<q.size()<<endl;
        while(!q.isEmpty()){
            q.pop(x);
            cout<<x<<endl;
        }
        
        cout<<"******************************************************"<<endl;
        Queue_x qx;
        for(int i=0; i<10; ++i)
            qx.push(i);
        for(int i=0; i<10; ++i){
            qx.pop(x);
            cout<<x<<endl;
            qx.push(100);
        }
        cout<<"队列的当前大小:"<<qx.size()<<endl;
        while(!qx.isEmpty()){
            qx.pop(x);
            cout<<x<<endl;
        }
        return 0;
    }

![复制代码][copycode.gif]

[copycode.gif]: /images/20220618/434b142d09f240afbc767322588c506b.png