栈和队列的OJ题——14.用栈实现队列

本文介绍: 出队操作：当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作。此题可以用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作。

14.用栈实现 队列

/*
解题思路：
此题可以用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作
出队操作： 当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作
*/

typedef struct {
    //入队栈
    Stack pushST;
    //出队栈
    Stack popST;
} MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {
    MyQueue* pqueue = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&amp;pqueue-&gt;pushST, maxSize);
    StackInit(&amp;pqueue-&gt;popST, maxSize);
    return pqueue;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    //入队栈进行入栈操作
    StackPush(&amp;obj-&gt;pushST, x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    //如果出队栈为空，导入入队栈的元素
    if(StackEmpty(&amp;obj-&gt;popST) == 0)
    {
        while(StackEmpty(&amp;obj-&gt;pushST) != 0)
        {
            StackPush(&amp;obj-&gt;popST, StackTop(&amp;obj->pushST));
            StackPop(&amp;obj->pushST);
        }
    }
    
    int front = StackTop(&amp;obj->popST);
    //出队栈进行出队操作
    StackPop(&amp;obj->popST);
    return front;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    //类似于出队操作
    if(StackEmpty(&amp;obj->popST) == 0)
    {
        while(StackEmpty(&amp;obj->pushST) != 0)
        {
            StackPush(&amp;obj->popST, StackTop(&amp;obj->pushST));
            StackPop(&amp;obj->pushST);
        }
    }
    
    return StackTop(&obj->popST);
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST) == 0
        &&  StackEmpty(&obj->popST) == 0;
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    
    free(obj);
}