刚讲完栈和队列，LeetCode上有两题栈与队列的互相实现，简单地讲讲思路和实现吧。
1.用队列实现栈
原题地址：225.用队列实现栈
题目要求我们用两个队列来实现一个栈，我们知道队列的性质是先进先出，而栈是后进先出，假设随便给我们要的这个栈之中添加几个数，便能画出这样的图
增删
那这样接下来若要出栈，输出的便是 5 ，但是队列出队的话只能输出 1 。所以我们就要用到另一个队列，把队列1最后一个数前面的数据导入到队列2之后再输出队列1的唯一数。这样就完成了出栈的模拟。
之后把队列1第一个数据删除，一定保证一个队列为空 ，即第二次出栈还是要把非空的队列的数据导入空队列里去。
若是要入栈操作的话就是直接再非空队列队尾插入数据就可以了，最后面的值不会被导入到另一队列里。所以下次出栈就会将其输出。
求栈顶元素
找栈顶元素其实与出栈的唯一不同就是，出栈要删除栈顶元素，而求栈顶元素不一样，其要求要有返回值。偷懒的话可以先写求栈顶元素，之后出栈只要复用函数就可以完成了。
判断栈为空
前面讲过，必定有一个队列为空，因此不能只检查一个队列而是两个队列都要检查，即两个队列都为空则证明栈为空。
2.用栈实现队列
原题地址：232.用栈实现队列
其实只要熟悉了队列和栈的基本性质，其实这两题也并不会很难，思路正确了剩下的就只需要注意编写程序时的小细节就可以了。
增删
仔细分析题目，要求用两个栈实现一个队列，既然题目都这样要求了只用一个栈明显是不可能的，上一题的经验告诉我，要把数据导入到另一个栈里。
把数据导到另一个栈后我们惊奇的发现，数据恰好就成了我们想要的样子。这段数据就可以直接输出了。
这下我们就可以让一个栈专门承载输入数据，另一个栈专门输出数据，输出栈为空时再从输入栈把数据导入到输出栈里面。
返回队列开头的数据
也是跟删除是一个道理，不过只是返回值并不删除数据。即输出栈没有值就导入输入栈的值进去就可以了。
判断队列为空
两个栈如果都为空，队列就为空，只有其中一个栈为空是不算的。
尾言
好了，这样今天我们两道题的思路与实现到这里就讲完了，说实在的用C语言写确实是麻烦了一点，但是之前写过栈和队列的话直接把代码复制过去，之后用自己之前写的函数写就可以了。有问题的话一定私信或者评论区指出，一定第一时间回复！！！
源码
队列实现栈
typedef int Qdatatype; typedef struct Qnode { Qdatatype data; struct Queue* next; }Qnode; typedef struct Queue { Qnode* head; Qnode* tail; int size; }Queue; void Queueinit(Queue* p) { p->head = NULL; p->tail = NULL; p->size = 0; } bool QueueEmpty(Queue* p) { assert(p); return p->head == NULL || p->tail == NULL; } void Queuepush(Queue* p, Qdatatype x) { assert(p); Qnode* newnode = (Qnode*)malloc(sizeof(Qnode)); if (newnode == NULL) { perror(malloc); exit(-1); } newnode->data = x; newnode->next = NULL; if (p->head == NULL) { p->head = p->tail = newnode; p->size++; } else { p->tail->next = newnode; p->tail = newnode; p->size++; } } void Queuepop(Queue* p) { assert(p); assert(!QueueEmpty(p)); Qnode* next = p->head->next; free(p->head); p->head = next; p->size--; } Qdatatype Queuefront(Queue* p) { assert(p); return p->head->data; } void QueueDestroy(Queue* p) { assert(p); Qnode* cur = p->head; while (cur) { Qnode* next = cur->next; free(cur); cur = next; } p->head = p->tail = NULL; p->size = 0; } Qdatatype Queueback(Queue* p) { assert(p); assert(!QueueEmpty(p)); return p->tail->data; } int Queuesize(Queue* p) { assert(p); return p->size; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* stack = (MyStack*)malloc(sizeof(MyStack)); //开辟栈的空间，动态开辟才不是局部变量 Queueinit(&stack->q1); //两个队列的初始化 Queueinit(&stack->q2); return stack; } void myStackPush(MyStack* obj, int x) { assert(obj); if (!QueueEmpty(&obj->q1)) //在非空队列里插入数据，两个都为空则默认插入在第一个里面 { return Queuepush(&obj->q1, x); } else { return Queuepush(&obj->q2, x); } } int myStackPop(MyStack* obj) { assert(obj); Queue* emptyqueue = &obj->q1; //一定有一个空队列 Queue* queue = &obj->q2; //一个是有数据的队列 if (QueueEmpty(&obj->q2)) //判断为空的队列 { emptyqueue = &obj->q2; queue = &obj->q1; } while (Queuesize(queue) > 1) { Queuepush(emptyqueue, Queuefront(queue)); //导入后删除原队列里的数据 Queuepop(queue); } int ret = Queuefront(queue); Queuepop(queue); return ret; } int myStackTop(MyStack* obj) { assert(obj); if (!QueueEmpty(&obj->q1)) { return Queueback(&obj->q1); } else { return Queueback(&obj->q2); } } bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); }
栈实现队列
typedef int STdatatype; typedef struct Stack { STdatatype* data; int top; int capacity; }Stack; void checkcapacity(Stack* p) { STdatatype* newp; if (p->top == p->capacity) { newp = (STdatatype*)realloc(p->data, sizeof(Stack) * p->capacity * 2); if (newp == NULL) { perror(realloc); exit(-1); } p->data = newp; p->capacity *= 2; } if (p == NULL) { perror(realloc); exit(-1); } } void StackInit(Stack* p) { STdatatype* np = (STdatatype*)malloc(sizeof(STdatatype) * 4); if (np) { p->data = np; } p->top = 0; p->capacity = 4; } void StackPush(Stack* p, STdatatype x) { assert(p); checkcapacity(p); (p->data)[p->top] = x; p->top++; } void Stackprint(Stack* p) { int i = p->top - 1; while (i >= 0) { printf("%d ", (p->data)[i--]); } printf("\n"); } void StackPop(Stack* p) { assert(p); assert(p->top); p->top--; } STdatatype StackTop(Stack* p) { assert(p); int top = p->top - 1; return (p->data)[top]; } int StackEmpty(Stack* p) { assert(p); if (p->top != 0) { return 0; } return 1; } void StackDestroy(Stack* p) { assert(p); assert(p->data); free(p->data); p->data = NULL; p->top = 0; p->capacity = 0; } typedef struct //两个队列一个输出一个输入，输出栈里没数据了之后就从输入里面倒数据过去 { Stack S; //输入 Stack nullS; //输出 } MyQueue; bool myQueueEmpty(MyQueue* obj); int myQueuePeek(MyQueue* obj); MyQueue* myQueueCreate() //创建队列 { MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue)); //开辟队列空间 StackInit(&queue->S); //对两个栈初始化 StackInit(&queue->nullS); return queue; //返回开辟的队列 } void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->S, x); //直接在插入的队列里插入数据 } int myQueuePop(MyQueue* obj) { assert(obj); assert(!myQueueEmpty(obj)); //判断队列不为空 int ret = myQueuePeek(obj); //取最上面的值返回 StackPop(&obj->nullS); //pop在peek的基础上增加数据的删除 return ret; } int myQueuePeek(MyQueue* obj) { //拿最前面的数据 assert(obj); assert(!myQueueEmpty(obj)); //队列不为空 if (StackEmpty(&obj->nullS)) //输出栈为空则倒入数据 { while (!StackEmpty(&obj->S)) //直到输入栈为空，必定一个栈为空 { StackPush(&obj->nullS, StackTop(&obj->S)); //取输入栈最上面导入到输出栈的最下面 StackPop(&obj->S); //清除输入栈的数据 } } return StackTop(&obj->nullS); //返回最上面的值 } bool myQueueEmpty(MyQueue* obj) { assert(obj); return StackEmpty(&obj->nullS) && StackEmpty(&obj->S); //两个栈都为空则队列为空 } void myQueueFree(MyQueue* obj) { assert(obj); StackDestroy(&obj->nullS); //销毁两个栈 StackDestroy(&obj->S); free(obj); //销毁队列 }
