栈与队列(力扣)

1. 用两个栈实现队列

题目描述(两个栈=>队列)：
剑指offer面试题第九题：用两个栈实现队列的基本操作(队尾插入，队头弹出，显示队头)

题目分析和解答:

这里借用原书中的话，他教给我们如何先用实例分析题目，然后再抽象成解法。分析过程参考原书和上图，最后总结出，
a)删除一个元素的步骤：
当stack2不为空时，在stack2的栈顶元素就是最先进入队列的元素，可以弹出。
当stack2为空时，我们把stack1的元素逐个弹出并压入stack2.由于先进入队列的元素被压到stack1的底部，经过弹出和压入操作之后，就处于stack2的顶端了，又可以直接弹出。
b)插入一个元素的步骤：
直接把它插入到stack1中。
c)显示队列头部：
当stack2不为空时，栈顶元素就是队列的头部，直接显示。
当stack2为空，我们把stack1的元素逐个弹出并压入stack2，再显示stack2的栈顶元素，如果此时stack2还是空，那说明stack1之前就是空的，抛出“队列为空”。

# include <iostream>
# include <stack>

using namespace std;

/*
暂时先定义成 接受int 类型的栈
*/

class myQueue{
    public:
        // constructure
        myQueue(stack<int> stack1, stack<int> stack2);
        ~myQueue();
        // number function: push() 将元素压入栈
        void push(int node);
        // number function: pop() 弹出栈顶的元素，且不返回改元素
        void pop(void);
        // number function: peek() 返回栈顶的元素
        int front(void);
    private:
        stack<int> stack1;
        stack<int> stack2;
};
// number function: push() 将元素压入栈
void myQueue::push(int node){
    stack1.push(node);
}
// number function: pop() 弹出栈顶的元素，且不返回改元素
void myQueue::pop(void){
    // 将stack1中的元素都压入stack2中
    if (stack2.empty()){
        while(!stack1.empty()){
        stack2.push(stack1.top());
        stack1.pop();
        }
    }
    if(stack2.empty()){
        std::cout << "Your queue is empty." << endl;
        return;
    }
    stack2.pop();
}
int myQueue::front(void){
    if (stack2.empty()){
        while(!stack1.empty()){
        stack2.push(stack1.top());
        stack1.pop();
        }
    }
    if(stack2.empty()){
        throw "Your queue is empty.";
    }
    return stack2.top();
}
myQueue::myQueue(stack<int> stack1, stack<int> stack2):stack1(stack1),stack2(stack2){

}
myQueue::~myQueue(){

}

int main(int argc, char const *argv[])
{
    stack<int> stack_1, stack_2;
    myQueue myqueue(stack_1, stack_2);
    for(int i=0; i<10; i++){
        myqueue.push(i);
    }
    for(int i=0; i<10; i++){
        cout << myqueue.front() << endl;
        myqueue.pop();
    }

    return 0;
}

2. 两个队列实现栈

剑指offer面试题第九题扩展：用两个队列实现队栈的基本操作(入栈，出栈，显示栈顶)
题目分析和解答：

如上图所示，分析过程参考原书，我们自己规定，每次插入新元素到queue1中。如果把queue1中的元素依次从队头弹出，从queue2的队尾加入，相对顺序不变。比如加入a,b,c, 最新加入的是c, 如果要弹出栈顶元素也就是弹出队尾的元素，此时可以依次把queue1的元素依次进入queue2，直到queue1中还剩一个元素(他必定是最新加入的元素，在队尾)，把它弹出。然后在依次把queue2的元素，加入到queue1中。
a)删除一个元素的步骤：
如果queue1为空，则抛出“队列为空”。
如果queue1不为空，依次把queue1的元素依次进入queue2，直到queue1中还剩一个元素(他必定是最新加入的元素，在队尾)，把它弹出。然后在依次把queue2的元素，加入到queue1中。
这样我们就保证了，每次删除数据后，数据都放在queue1，queue2只是起缓存的作用。
b)插入一个元素的步骤：
直接插入到queue1。
c)显示栈顶元素：
如果stack1不为空，直接显示队尾元素。
如果stack1为空，抛出“队列为空”。

# include <iostream>
# include <queue>

using namespace std;
class myStack{
    public:
        myStack(queue<int> queue1, queue<int> queue2);
        ~myStack();
        void push(int node);
        int top(void);
        void pop(void);
    private:
        queue<int> queue1;
        queue<int> queue2;
};
myStack::myStack(queue<int> queue1, queue<int> queue2):queue1(queue1), queue2(queue2){}

myStack::~myStack(){}

// 把元素压入队列1中
void myStack::push(int node){
    queue1.push(node);
}

// 把元素先从队列1中，从头出队依次进入队列2，直到队列1还剩一个元素，把这个元素弹出，就是栈顶的元素
// 然后再把队列2的元素依次出队放入到队列1中
void myStack::pop(void){
    if (queue1.empty()){
        cout << "Your stack is empty!" << endl;
        return;
    }
    while(queue1.size() != 1){
        queue2.push(queue1.front());
        queue1.pop();
    }
    queue1.pop();
    while(!queue2.empty()){
        queue1.push(queue2.front());
        queue2.pop();
    }
    return;
}

int myStack::top(void){
    if (queue1.empty()){
        cout << "Your stack is empty!" << endl;
        return -1;
    }else{
        return queue1.back();
    }

}
int main(int argc, char const *argv[])
{
    queue<int> queue_1, queue_2;
    myStack mystack(queue_1, queue_2);
        for(int i=0; i<10; i++){
        mystack.push(i);
    }
    for(int i=0; i<10; i++){
        cout << mystack.top() << endl;
        mystack.pop();
    }
    mystack.pop();
    mystack.pop();
    return 0;
}