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

#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;
}