1. 题目描述

problem link

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

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

2. 解题

用两个队列解决这个问题，入栈的时候无脑往其中一个队列入，如下图所示：

可知此时如果需要出栈，就要得到4，那么可以这么做：把左队列先出3个元素同时依次入到右队列，再取出左队列的最后一个元素即为4，如下图所示：

可知这种方法每次Pop和Top的时候都需要把所有元素搬运一遍，所以可知在任意时刻至少有一个队列为空队列。所以实现这个栈的时候可以用两个队列queueEmpty和queueFull，每次搬运完数据改变一下两个指针的指向即可。

3. 代码

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef struct QueueNode {
    struct QueueNode *next;
    int data;
} Node;

typedef struct Queue {
    Node *head;
    Node *rear;
} Queue;

// ---------- implement queue -------------

void QueueInit(Queue *pQ) {
    assert(pQ);

    pQ->head = NULL;
    pQ->rear = NULL;
}

void QueueDestroy(Queue *pQ) {
    assert(pQ);

    Node *cur, *tmp;
    cur = pQ->head;
    while (cur) {
        tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    pQ = NULL;
}

Node* getNode(int data) {
    Node* res = (Node *)malloc(sizeof(Node));
    res->next = NULL;
    res->data = data;

    return res;
}

void QueuePush(Queue *pQ, int data) {
    assert(pQ);

    Node* newNode = getNode(data);
    if (pQ->head == NULL) {  // empty queue
        pQ->head = pQ->rear = newNode;

    }
    else {
        pQ->rear = pQ->rear->next = newNode;
    }
}

void QueuePop(Queue *pQ) {
    assert(pQ);

    if (pQ->head != NULL) {  // if not empty queue
        Node *tmp = pQ->head;
        if (pQ->head == pQ->rear) {  // only one node
            pQ->head = pQ->rear = NULL;
        }
        else {
            pQ->head = pQ->head->next;
        }
        free(tmp);
    }
}

int QueueHead(Queue *pQ) {
    assert(pQ);
    assert(pQ->head);

    return pQ->head->data;
}

int QueueRear(Queue *pQ) {
    assert(pQ);
    assert(pQ->rear);

    return pQ->rear->data;
}

int QueueEmpty(Queue *pQ) {
    assert(pQ);

    return pQ->head == NULL;
}

int QueueSize(Queue *pQ) {
    assert(pQ);

    Node* cur = pQ->head;
    int count = 0;

    while (cur) {
        cur = cur->next;
        count++;
    }

    return count;
}

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

typedef struct {
    Queue *qFull;
    Queue *qEmpty;
} MyStack;

typedef int bool;
#define true 1;
#define false 0;

/** Initialize your data structure here. */

MyStack* myStackCreate() {
    Queue *pFull = (Queue *)malloc(sizeof(Queue));
    Queue *pEmpty = (Queue *)malloc(sizeof(Queue));
    QueueInit(pFull);
    QueueInit(pEmpty);

    MyStack *myStack = (MyStack *)malloc(sizeof(MyStack));
    myStack->qFull = pFull;
    myStack->qEmpty = pEmpty;

    return myStack;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    QueuePush(obj->qFull, x);
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    while (QueueSize(obj->qFull) != 1) {
        QueuePush(obj->qEmpty, QueueHead(obj->qFull));
        QueuePop(obj->qFull);
    }
    int res = QueueHead(obj->qFull);
    QueuePop(obj->qFull);

    Queue *tmp = obj->qFull;
    obj->qFull = obj->qEmpty;
    obj->qEmpty = tmp;

    return res;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    while (QueueSize(obj->qFull) != 1) {
        QueuePush(obj->qEmpty, QueueHead(obj->qFull));
        QueuePop(obj->qFull);
    }
    int res = QueueHead(obj->qFull);
    QueuePush(obj->qEmpty, QueueHead(obj->qFull));
    QueuePop(obj->qFull);

    Queue *tmp = obj->qFull;
    obj->qFull = obj->qEmpty;
    obj->qEmpty = tmp;

    return res;
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    return QueueSize(obj->qFull) == 0;
}

void myStackFree(MyStack* obj) {
    QueueDestroy(obj->qEmpty);
    QueueDestroy(obj->qFull);
}