栈和队列
做这题首先需要明确
- 栈：是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。栈的元素不允许下标直接访问，且元素遵循先入后出原则
- 如图
- 队列：是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表。队列的元素不允许下标直接访问，且元素遵循先进先出原则。
- 如图
思路
- 由于栈的元素遵循先入后出原则，因此只能优先弹出后插入的元素，队列的元素遵循先入先出原则，因此只能优先弹出先插入的元素，此时要想利用栈来实现队列，就需要先将栈的元素全部取出，并依次存入辅助栈中，再出栈，这样就实现了先进先出的功能。
- 同理，返回队头元素以及队列的判空时也要进行相同的操作。
具体步骤
- 首先定义两个栈stackIn和stackOut，以及他们的栈顶指针topIn，topOut并初始化为0。
- 进行入队操作push时，先利用栈的操作存储在stackIn中，每次存储过后栈顶指针topIn加一，即栈顶上移
- 进行出队操作pop时，首先需要判断实现这个操作的辅助栈stackOut是否还有元素，如果没有，则利用循环，将stackIn的所有元素全部取出并依次存入stackOut中，然后再利用stackOut的出栈操作实现出队；如果stackOut还有元素未出栈，则直接对这个元素出队，保留stackIn的元素（若是仍用循环将stackIn的元素继续移入stackOut中，则会打乱元素顺序，实现不了先入先出）
实现代码
typedef struct { int StackIn[100]; int StackOut[100]; int topIn; int topOut; } MyQueue; MyQueue* myQueueCreate() { MyQueue *obj = (MyQueue *)malloc(sizeof(MyQueue)); obj->topIn = 0; obj->topOut = 0; return obj; } void myQueuePush(MyQueue* obj, int x) { obj->StackIn[obj->topIn] = x; obj->topIn++; } int myQueuePop(MyQueue* obj) { if(obj->topOut == 0) { while(obj->topIn > 0) obj->StackOut[(obj->topOut)++] = obj->StackIn[--(obj->topIn)]; } return obj->StackOut[--(obj->topOut)]; } int myQueuePeek(MyQueue* obj) { if(obj->topOut == 0) { while(obj->topIn > 0) obj->StackOut[(obj->topOut)++] = obj->StackIn[--(obj->topIn)]; } return obj->StackOut[(obj->topOut) - 1]; } bool myQueueEmpty(MyQueue* obj) { if(obj->topOut == 0) { while(obj->topIn > 0) obj->StackOut[(obj->topOut)++] = obj->StackIn[--(obj->topIn)]; } if(obj->topOut == 0) return true; else return false; } void myQueueFree(MyQueue* obj) { 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); */
