队列实现栈：
首先分析两者特性，栈和队列都是线性结构。栈的特点是先进后出，队列的特点是先进先出。要想用队列实现栈，必然需要两个队列，因为我们出栈的时候要出的是最后一个元素，而队列的最后一个元素是在最后出栈的，所以我们需要把最后一个元素之前的元素全部放入另一个栈，然后才能将队列中的最后一个元素当做第一个元素取出。
题目链接：
代码实现：
typedef struct QListNode { struct QListNode* next; int data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QueueInit(Queue* q) { q->head = q->tail = NULL; q->size = 0; } void QueuePush(Queue* q, int x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if(q->tail == NULL) { q->head = q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } q->size++; } int QueuePop(Queue* q) { int ret = q->head->data; if(q->tail == q->head) { free(q->head); q->head = q->tail = NULL; } else { QNode* del = q->head; q->head = q->head->next; free(del); } q->size++; return ret; } int QueueTop(Queue* q) { return q->head->data; } int QueueBack(Queue* q) { return q->tail->data; } bool QueueEmpty(Queue* q) { return q->head == NULL && q->tail == NULL; } void QueueDestory(Queue* q) { while(q->head) { QNode* del = q->head; q->head = q->head->next; free(del); } } 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) { QueuePush(&obj->q1, x); } int myStackPop(MyStack* obj) { while(obj->q1.head->next) { QueuePush(&obj->q2, QueuePop(&obj->q1)); } int ret = QueuePop(&obj->q1); while(!QueueEmpty(&obj->q2)) { QueuePush(&obj->q1, QueuePop(&obj->q2)); } return ret; } int myStackTop(MyStack* obj) { return QueueBack(&obj->q1); } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestory(&obj->q1); } /** * 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); */
用栈实现队列：
还是根据两者的特性来实现代码，栈是先进后出，队列是先进先出。要用栈实现队列必然也是需要两个栈的。我们出队列需要取到栈底的元素，作为队头的元素pop出去。但是和队列实现栈不同的是，队列是先进先出，所以顺序不会变化，但是栈是先进后出，这就会导致每一次将元素转入到另一个栈中时，元素会逆序，我们可以利用这一点优化代码。我们不难发现，每次将数据从初始存储的栈移入另一个栈时，在这个栈中，出栈的顺序和队列出队的顺序是一样的，所以我们可以一个用入队存元素，一个用来出队出元素。即只要入队，我们就将元素全放在一个栈1里面；只要出队，我们就先将元素全移入栈2再出队。
题目链接：
代码实现：
typedef struct Stack { int* a; int top; int capacity; }Stack; void StackInit(Stack* ps) { ps->a = (int*)malloc(sizeof(int) * 4); if(ps->a == NULL) { printf("malloc fail"); exit(-1); } ps->top = 0; ps->capacity = 4; } void StackPush(Stack* ps, int x) { if(ps->top == ps->capacity) { int* tmp = (int*)realloc(ps->a, ps->capacity * 2 * sizeof(int)); if(tmp == NULL) { printf("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } void StackPop(Stack* ps) { ps->top--; } int StackTop(Stack* ps) { return ps->a[ps->top - 1]; } int StackSize(Stack* ps) { return ps->top + 1; } bool StackEmpty(Stack* ps) { return ps->top == 0; } void StackDestory(Stack* ps) { free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } typedef struct { Stack PushSt; Stack PopSt; } MyQueue; bool myQueueEmpty(MyQueue* obj); MyQueue* myQueueCreate() { MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&pq->PushSt); StackInit(&pq->PopSt); return pq; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->PushSt, x); } int myQueuePop(MyQueue* obj) { int peek = myQueuePeek(obj); StackPop(&obj->PopSt); return peek; } int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->PopSt)) { while(!StackEmpty(&obj->PushSt)) { StackPush(&obj->PopSt, StackTop(&obj->PushSt)); StackPop(&obj->PushSt); } } return StackTop(&obj->PopSt); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->PushSt) && StackEmpty(&obj->PopSt); } void myQueueFree(MyQueue* obj) { StackDestory(&obj->PushSt); StackDestory(&obj->PopSt); } /** * 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); */
