0232. Implement Queue using Stac

C和Java运行时间内存的对比如下：

LC0232_01.PNG

两种语言的思路都是一样的，

1. 入队就是push(stk2)
2. 出队分三步：
   (1) 就是 所有 stk2 的元素 转移到 stk1,
   (2) pop(stk1)
   (3) stk1剩下的元素 移动到 stk2
3. peek的操作和 出队类似

C程序，链表实现Stack，两个Stack模拟Queue

typedef struct _ListNode{
    int val;
    int size;
    int max;
    struct _ListNode* next;
}ListNode;


ListNode* init(int max){
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->size=0;
    head->max=max;
    head->next=NULL;/*注意初始化否则会引起莫名奇妙的问题*/
    return head;
}

void push(ListNode* head, int val){
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if(head->next == NULL){/*分别考虑第一个node和其他node的情况*/
        node->next = NULL;
    }else{
        node->next = head->next;
    }
    node->val = val;
    head->next = node;
    head->size +=1;
}

int pop(ListNode* head){
    ListNode* trgt = head->next;
    int rst = trgt->val;
    head->next = trgt->next;
    free(trgt);
    trgt = NULL;
    head->size -=1;
    return rst;
}

int peek(ListNode* head){
    return head->next->val;
}

int empty(ListNode* head){
    if(head->size==0)
        return 1;
    return 0;
}

void stk2_to_stk1(ListNode* stk2, ListNode* stk1){
    int val;
    while(! empty(stk2)){
        val = pop(stk2);
        push(stk1,val);
    }
}

typedef struct {
    ListNode* stk1;
    ListNode* stk2;
} MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {
    MyQueue *queue = (MyQueue*)malloc(sizeof(MyQueue));
    queue->stk1 = init(maxSize);
    queue->stk2 = init(maxSize);
    return queue;
}

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

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    int ret;
    if(empty(obj->stk1) == 1)
        stk2_to_stk1(obj->stk2, obj->stk1);
    ret = pop(obj->stk1);
    while(empty(obj->stk1) == 0)
        push(obj->stk2, pop(obj->stk1));
    return ret;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    int ret;
    if(empty(obj->stk1) == 1)
        stk2_to_stk1(obj->stk2, obj->stk1);
    ret = peek(obj->stk1);
    while(empty(obj->stk1) == 0)
        push(obj->stk2, pop(obj->stk1));
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return empty(obj->stk2);
}

void myQueueFree(MyQueue* obj) {
    ListNode* tp;
    while(obj->stk1 != NULL){
        tp = obj->stk1->next;
        free(obj->stk1);
        obj->stk1 = tp;
    }
    while(obj->stk2 != NULL){
        tp = obj->stk2->next;
        free(obj->stk2);
        obj->stk2 = tp;
    }
    free(obj);
    obj = NULL;
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * struct MyQueue* obj = myQueueCreate(maxSize);
 * myQueuePush(obj, x);
 * int param_2 = myQueuePop(obj);
 * int param_3 = myQueuePeek(obj);
 * bool param_4 = myQueueEmpty(obj);
 * myQueueFree(obj);
 */

Java程序
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.

class MyQueue {
    private Stack<Integer> stk1;
    private Stack<Integer> stk2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stk1 = new Stack<Integer>();
        stk2 = new Stack<Integer>();
    }
    private void stk2ToStk1(){
        while(! stk2.isEmpty())
            stk1.push(stk2.pop());
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        stk2.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stk1.empty() == true)
            this.stk2ToStk1();
        int rst = stk1.pop();
        while(! stk1.isEmpty())
            stk2.push(stk1.pop());
        return rst;
    }

    /** Get the front element. */
    public int peek() {
        if(stk1.empty() == true)
            this.stk2ToStk1();
        int rst = stk1.peek();
        while(! stk1.isEmpty())
            stk2.push(stk1.pop());
        return rst;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stk2.empty();
    }
}