1. 题目描述

problem link

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

2. 解题

用两个栈解决这个问题。

首先入队列操作无脑往左栈入栈，如下图，依次入栈1，2，3，4：

由于要实现的是队列，所以可知道出队列的顺序应该是1，2，3，4。所以为了达到这一目标，出队列的时候，如果右栈是空的（等会才能知道为什么有这个前提），就把左栈元素依次出栈然后入到右栈，完成后变成了下图：

然后现在右栈出栈的顺序就是整个队列出队列的顺序！所以每次出队列的时候都要先检查一次右栈是否为空，如果不为空直接出右栈就ok了。如果右栈是空的，就先把左栈元素依次出栈再入栈到右栈，然后出一个右栈元素就好了。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// --------- implement stack ----------

typedef struct Stack {
    int* arr;
    int capacity;
    int top;
} Stack;

void StackInit(Stack* ps) {
    assert(ps);

    int* tmp = (int *)malloc(sizeof(int) * 10);
    if (tmp == NULL) {
        assert(0);
    }

    ps->arr = tmp;
    ps->capacity = 10;
    ps->top = 0;
}

void StackDestroy(Stack* ps) {
    assert(ps);

    free(ps->arr);
    ps = NULL;
}

void CheckCap(Stack* ps) {
    assert(ps);

    if (ps->capacity == ps->top) {  // full
        int* tmp = (int *)realloc(ps->arr, ps->capacity * 2);
        assert(tmp);

        ps->arr = tmp;
        ps->capacity *= 2;
    }
}

void StackPush(Stack* ps, int data) {
    assert(ps);

    CheckCap(ps);

    ps->arr[ps->top++] = data;
}

void StackPop(Stack* ps) {
    assert(ps);

    if (ps->top != 0) {
        ps->top--;
    }
}

int StackTop(Stack* ps) {
    assert(ps);
    assert(ps->top);

    return ps->arr[ps->top - 1];
}

int StackEmpty(Stack* ps) {
    assert(ps);

    return ps->top == 0;
}

int StackSize(Stack* ps) {
    assert(ps);

    return ps->top;
}

// ------------ implement queue ------------
typedef struct {
    Stack* s1;
    Stack* s2;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* res = (MyQueue *)malloc(sizeof(MyQueue));
    res->s1 = (Stack *)malloc(sizeof(Stack));
    res->s2 = (Stack *)malloc(sizeof(Stack));
    StackInit(res->s1);
    StackInit(res->s2);

    return res;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    StackPush(obj->s1, x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    if (StackEmpty(obj->s2)) {
        while (!StackEmpty(obj->s1)) {
            StackPush(obj->s2, StackTop(obj->s1));
            StackPop(obj->s1);
        }
    }

    int res = StackTop(obj->s2);
    StackPop(obj->s2);
    return res;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if (StackEmpty(obj->s2)) {
        while (!StackEmpty(obj->s1)) {
            StackPush(obj->s2, StackTop(obj->s1));
            StackPop(obj->s1);
        }
    }

    int res = StackTop(obj->s2);

    return res;
}

/** Returns whether the queue is empty. */
typedef int bool;
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(obj->s1) && StackEmpty(obj->s2);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(obj->s1);
    StackDestroy(obj->s2);
}