用队列实现栈
题目描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
解题思路：
栈的特性是先入后出，而队列的特性是先入先出
先让一个队列入数据，另一个队列不入数据
出数据时，先出队列到最后一个数据，而之前的数据都入到另一个空队列
最后将队列最后一个数据给出队列
以后再入数据时，都入到有数据的队列
出数据时，都现将最后一个数据之前的数据入到另一个空队列，再将最后一个数据给出队列
总之永远保持有一个队列为空
图示：
参考代码：
typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack*st=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&st->q1); QueueInit(&st->q2); return st; } void myStackPush(MyStack* obj, int x) { //入栈时入空队列 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { //出栈时，先将有数据的队列出队到最后一个元素，并将数据入队到空队列，最后将最后一个数据出队达到出栈的效果 Queue* emptyQ=&obj->q1; Queue* noemptyQ=&obj->q2; if(QueueEmpty(&obj->q2)) { emptyQ=&obj->q2; noemptyQ=&obj->q1; } while(QueueSize(noemptyQ)>1) { QueuePush(emptyQ,QueueFront(noemptyQ)); QueuePop(noemptyQ); } int top=QueueFront(noemptyQ); QueuePop(noemptyQ); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q1); free(obj); }
队列源码
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; // size_t _size; }Queue; //void QueueInit(QueueNode** pphead, QueueNode** pptail); void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); //if (pq->head == NULL) // return; assert(!QueueEmpty(pq)); QueueNode* next = pq->head->next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur) { ++n; cur = cur->next; } return n; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
