C语言面试题之化栈为队

化栈为队

实例要求

C语言实现实现一个MyQueue类，该类用两个栈来实现一个队列；
示例：

MyQueue queue = new MyQueue();queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明：
1、只能使用标准的栈操作 ，即只有 push to top, peek/pop from top, size 和 is empty
操作是合法的；
2、所使用的语言也许不支持栈。
3、可以使用 list 或者 deque（双端队列）来模拟一个栈，
4、只要是标准的栈操作即可。
5、假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

实例分析

一、算法思想：
若实现一个队列的功能，需要用到两个栈来实现此功能，创建两个栈S1和S2；
二、入队列：
所有的数据元素都入栈到S1，即所有的数据元素在S1完成入队列；
三、出队列：
判断S2是否为空；
若S2不为空，则数据元素在S2出栈，即数据元素在S2完成出队列；
若S2为空且S1不为空，则S1中所有数据元素依次在S1出栈并依次入栈到S2，接下来，所有的数据元素在S2出栈，即所有的数据元素在S2完成出队列；
若S2为空且S1为空，即所构造的队列为空；

示例代码

#define maxSize 1024typedef struct {int stack1[maxSize];int top1; // 栈1的栈顶指针int stack2[maxSize];int top2; // 栈2的栈顶指针
} MyQueue;/** Initialize your data structure here. */
MyQueue* myQueueCreate() {MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));queue->top1 = -1; // 栈1为空queue->top2 = -1; // 栈2为空return queue;
}/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {obj->stack1[++obj->top1] = x; // 将元素压入栈1
}/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {if (obj->top2 == -1) { // 如果栈2为空while (obj->top1 != -1) { // 将栈1中的元素逐个弹出并压入栈2，以颠倒顺序obj->stack2[++obj->top2] = obj->stack1[obj->top1--];}}if (obj->top2 == -1) { // 如果栈2仍为空，说明队列为空return -1;}return obj->stack2[obj->top2--]; // 弹出栈2的栈顶元素
}/** Get the front element. */
int myQueuePeek(MyQueue* obj) {if (obj->top2 == -1) { // 如果栈2为空while (obj->top1 != -1) { // 将栈1中的元素逐个弹出并压入栈2，以颠倒顺序obj->stack2[++obj->top2] = obj->stack1[obj->top1--];}}if (obj->top2 == -1) { // 如果栈2仍为空，说明队列为空return -1;}return obj->stack2[obj->top2]; // 返回栈2的栈顶元素，但不弹出
}/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {return obj->top1 == -1 && obj->top2 == -1; // 如果栈1和栈2均为空，则队列为空
}void myQueueFree(MyQueue* obj) {free(obj);obj = NULL;
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/