1. 题目描述
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
, andis 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);
}