用栈实现队列
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
思路分享
栈是先进后出的，但是队列是先进先出。
用栈实现队列，就是在俩个栈之间不断倒元素来实现队列的先进先出。
我们先用一个栈来存入元素（这时最先进入的元素在栈底），然后再将第一个栈中的元素移动到新栈中，此时最先进入的元素就在栈顶了。
之后我们再用第二个栈出栈时，整个执行的顺序就变成了先进先出。
定义一个Pushst专门用来入栈，一个Popst专门用来出栈。
需要注意的是，每次栈Popst出栈时都要把所有的元素都出完之后，才能从Pushst中追加新数据，当Popst的数据没有全部出栈完成时，不能将Pushst的元素入栈到Popst，这样会导致元素的执行顺序混乱。
源码
#include<stdlib.h> #include<assert.h> #include<stdio.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void STInit(ST* pst); void STPush(ST* pst, STDataType x); void STPop(ST* pst); void STDestroy(ST* pst); STDataType STTop(ST* pst); bool STEmpty(ST* pst); void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0;//top指向栈顶数据的下一个位置 //pst->top=-1;top指向栈顶数据 pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; } bool STEmpty(ST* pst) { return pst->top == 0; } void STPush(ST* pst, STDataType x) { if (pst->capacity == pst->top) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity); pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } int STSize(ST* pst) { assert(pst); assert(!(STEmpty(pst))); return pst->top; } typedef struct { ST Pushst; ST Popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue * obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL) { perror("malloc fail"); return NULL; } STInit(&obj->Pushst); STInit(&obj->Popst); return obj; } bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->Popst)&&STEmpty(&obj->Pushst); } void myQueuePush(MyQueue* obj, int x) { assert(&obj); STPush(&obj->Pushst,x); } int myQueuePop(MyQueue* obj) { int front=myQueuePeek(obj); STPop(&obj->Popst); return front; } int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->Popst)) { while(!STEmpty(&obj->Pushst)) { STPush(&obj->Popst,STTop(&obj->Pushst)); STPop(&obj->Pushst); } } return STTop(&obj->Popst); } void myQueueFree(MyQueue* obj) { STDestroy(&obj->Pushst); STDestroy(&obj->Popst); free(obj); } /** * 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); */
用队列实现栈
思路分享
队列是先进先出，栈是先进后出。
先进先出的特性决定了当一个队列向另一个队列倒元素时，被导入的元素顺序不变。
原先的队列是什么样子，被导入的另一个队列就是什么样子。
那么，删除元素的思路就很明显了，将队列1中的数据挨个导入队列2，直到队列1剩下最后一个元素。
我们知道，这个元素实际上是队尾元素，而对应到栈就是栈顶元素。
我们将其删除，就模拟实现了出栈操作。
入栈操作就更为简单，进入不为空的那个队列，不然会影响数据的排列顺序。
源码
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }Node; typedef struct Queue { Node* phead; Node* ptail; int size; }Queue; bool QueueEmpty(Queue* pq) { assert(pq); //return pq->phead == NULL && pq->ptail == NULL; return pq->size==0; } void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); Node* cur = pq->phead; while (cur!=NULL) { Node* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); Node* newnode = (Node*)malloc(sizeof(Node)); if (newnode == NULL) { perror("malloc fail\n"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead==NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//也可以直接用phead if (pq->phead->next==NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { Node* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack *obj=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Node*pEmptyQ=&obj->q1; Node*pNonEmptyQ=&obj->q2; if(!QueueEmpty(&obj->q1)) { pEmptyQ=&obj->q2; pNonEmptyQ=&obj->q1; } while(QueueSize(pNonEmptyQ)>1) { QueuePush(pEmptyQ,QueueFront(pNonEmptyQ)); QueuePop(pNonEmptyQ); } int top=QueueFront(pNonEmptyQ); QueuePop(pNonEmptyQ); 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->q2); free(obj); } /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */
后记
哎，成为大牛任重而道远，小僧仍需继续努力。。。
各位施主共勉。。。
