一、实现原理
栈：后进先出
队列：先进先出
从栈和队列的特性就可以发现，一个栈是无法实现队列的功能的，这里我们需要两个栈来模拟实现。接下来就进行一步一步的分析其实现过程和原理：
首先可以将一个栈用来模拟入队列功能，假设已经有一些数据入队，即进入到一个栈中，如图：
那么根据队列先进先出的特点，此时队头应该是a1，当我们要进行出队操作时，就需要先将a2、a3、a4出栈再入栈到s2中，才能获取到队头元素a1：
此时只需队栈s1进行出栈操作即可完成队列的出队操作，后续若还需出队，则只需对栈s2进行出栈即为队列出队。
后续若再有入队的的元素，则只需入栈到s1中即可。
两个栈都为空时，即队列为空，两个栈都为满时，即队列为满（但对于入队元素时的判满，只能根据栈s1来判断，即s1为满，即队列为满，不可再插入，因为这里的模拟实现入队只能进入到内部的栈s1中。
若对其原理和过程还是不太熟悉，可以根据下面的结论自己进行画图模拟，即可很容易理解。
结论：
1.队空：栈s1、s2都为空。
2.队满：栈s1为满，即队满（s1为模拟队列入队的栈）。
3.入队：直接入栈到s1中。
3.出队：
若栈s2为空，将栈s1内前n-1个元素依次出栈在入栈到s2中，s1内最后一个元素即为队头元素，只进行出栈操作即出队完成；
若s2不为空，只直接对s2进行出栈操作，即队列出队操作完成。（前提：队列不为空）。
4.获取队头元素：
若s2不为空，则直接返回s2的栈顶，即队头元素；
若s2为空，则直接返回s1的栈底元素，即队头元素。（前提：队列不为空）
5.获取队尾元素：与获取队头相反即可。
6.获取队列有效元素个数：两个栈内元素个数之和（top1+top2）或（size1+size2）。
7.队列销毁：销毁掉队列内部两个栈，然后再销毁队列即可。
二、结构体定义
typedef int ElemType; typedef struct {//栈 ElemType* array; int top; int size;//有效元素个数 }myStack; typedef struct {//两个栈模拟实现队列 myStack* q1;//入队 myStack* q2;//出队 } MyQueue;
三、接口模拟实现
MyQueue* myQueueCreate();//队列初始化 void myQueuePush(MyQueue* obj, int x);//入队 int myQueuePop(MyQueue* obj);//出队并返回队头元素 int myQueuePeek(MyQueue* obj);//获取队头元素 bool myQueueEmpty(MyQueue* obj);//判空 void myQueueFree(MyQueue* obj);//销毁 void test_Stack_Queue();//测试函数
1.队列初始化
MyQueue* myQueueCreate() {//队列初始化 MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); if (obj == NULL) {//申请失败 assert(0); return NULL; } obj->q1 = (myStack*)malloc(sizeof(myStack)); obj->q2 = (myStack*)malloc(sizeof(myStack)); if (obj->q1 == NULL || obj->q2 == NULL) {//申请失败 assert(0); return NULL; } obj->q1->array = (ElemType*)malloc(sizeof(ElemType) * 10); obj->q2->array = (ElemType*)malloc(sizeof(ElemType) * 10); if (obj->q1->array == NULL || obj->q2->array == NULL) {//申请失败 assert(0); return NULL; } obj->q1->top = 0; obj->q2->top = 0; obj->q1->size = 0; obj->q2->size = 0; return obj; }
2.队列入队
void myQueuePush(MyQueue* obj, int x) {//入队 assert(obj); if (obj->q1->top == 10) {//队满 return; } obj->q1->array[obj->q1->top] = x;//入栈q1 obj->q1->top++; obj->q1->size++; }
3.出队并返回队头元素
int myQueuePop(MyQueue* obj) {//出队并返回队头元素 assert(obj); if (obj->q2->size == 0 && obj->q1->size > 0) {//q2为空,q1不为空时，将栈q1内的元素出栈，再入栈到q2中 while (obj->q1->size > 0) { obj->q2->array[obj->q2->top] = obj->q1->array[obj->q1->top - 1]; obj->q2->top++; obj->q2->size++; obj->q1->top--; obj->q1->size--; } } obj->q2->top--;//q2.top移到栈顶元素位置 obj->q2->size--; return obj->q2->array[obj->q2->top];//返回栈顶元素同时元素出栈 }
4.获取队头元素
int myQueuePeek(MyQueue* obj) {//获取队头元素 assert(obj); if (obj->q2->size == 0 && obj->q1->size > 0) {//q2为空,q1不为空时，将栈q1内的元素出栈，再入栈到q2中 while (obj->q1->size > 0) { obj->q2->array[obj->q2->top] = obj->q1->array[obj->q1->top - 1]; obj->q2->top++; obj->q2->size++; obj->q1->top--; obj->q1->size--; } } return obj->q2->array[obj->q2->top - 1];//返回栈顶元素 }
5.队列判空
bool myQueueEmpty(MyQueue* obj) {//判空 assert(obj); if (obj->q1->size == 0 && obj->q2->size == 0) {//两个栈都为空，队列为空 return true; } return false; }
6.队列销毁
void myQueueFree(MyQueue* obj) {//销毁 assert(obj); free(obj->q1->array); free(obj->q1); free(obj->q2->array); free(obj->q2); free(obj); }
四、接口测试
1.测试函数
void test_Stack_Queue() { MyQueue* q = myQueueCreate(); myQueuePush(q, 1); myQueuePush(q, 2); printf("front=%d\n", myQueuePop(q));//出队并打印队头元素 printf("front=%d\n", myQueuePeek(q)); printf("front=%d\n", myQueuePop(q));//出队并打印队头元素 printf("bool=%d\n", myQueueEmpty(q));//判空 myQueueFree(q); }
2.测试结果
五、完整代码
#include<stdio.h> #include<malloc.h> #include<assert.h> #include<stdbool.h> typedef int ElemType; typedef struct {//栈 ElemType* array; int top; int size;//有效元素个数 }myStack; typedef struct {//两个栈模拟实现队列 myStack* q1;//入队 myStack* q2;//出队 } MyQueue; MyQueue* myQueueCreate();//队列初始化 void myQueuePush(MyQueue* obj, int x);//入队 int myQueuePop(MyQueue* obj);//出队并返回队头元素 int myQueuePeek(MyQueue* obj);//获取队头元素 bool myQueueEmpty(MyQueue* obj);//判空 void myQueueFree(MyQueue* obj);//销毁 void test_Stack_Queue();//测试函数 int main() { test_Stack_Queue(); return 0; } void test_Stack_Queue() { MyQueue* q = myQueueCreate(); myQueuePush(q, 1); myQueuePush(q, 2); printf("front=%d\n", myQueuePop(q));//出队并打印队头元素 printf("front=%d\n", myQueuePeek(q)); printf("front=%d\n", myQueuePop(q));//出队并打印队头元素 printf("bool=%d\n", myQueueEmpty(q));//判空 myQueueFree(q); } MyQueue* myQueueCreate() {//队列初始化 MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); if (obj == NULL) {//申请失败 assert(0); return NULL; } obj->q1 = (myStack*)malloc(sizeof(myStack)); obj->q2 = (myStack*)malloc(sizeof(myStack)); if (obj->q1 == NULL || obj->q2 == NULL) {//申请失败 assert(0); return NULL; } obj->q1->array = (ElemType*)malloc(sizeof(ElemType) * 10); obj->q2->array = (ElemType*)malloc(sizeof(ElemType) * 10); if (obj->q1->array == NULL || obj->q2->array == NULL) {//申请失败 assert(0); return NULL; } obj->q1->top = 0; obj->q2->top = 0; obj->q1->size = 0; obj->q2->size = 0; return obj; } void myQueuePush(MyQueue* obj, int x) {//入队 assert(obj); if (obj->q1->top == 10) {//队满 return; } obj->q1->array[obj->q1->top] = x;//入栈q1 obj->q1->top++; obj->q1->size++; } int myQueuePop(MyQueue* obj) {//出队并返回队头元素 assert(obj); if (obj->q2->size == 0 && obj->q1->size > 0) {//q2为空,q1不为空时，将栈q1内的元素出栈，再入栈到q2中 while (obj->q1->size > 0) { obj->q2->array[obj->q2->top] = obj->q1->array[obj->q1->top - 1]; obj->q2->top++; obj->q2->size++; obj->q1->top--; obj->q1->size--; } } obj->q2->top--;//q2.top移到栈顶元素位置 obj->q2->size--; return obj->q2->array[obj->q2->top];//返回栈顶元素同时元素出栈 } int myQueuePeek(MyQueue* obj) {//获取队头元素 assert(obj); if (obj->q2->size == 0 && obj->q1->size > 0) {//q2为空,q1不为空时，将栈q1内的元素出栈，再入栈到q2中 while (obj->q1->size > 0) { obj->q2->array[obj->q2->top] = obj->q1->array[obj->q1->top - 1]; obj->q2->top++; obj->q2->size++; obj->q1->top--; obj->q1->size--; } } return obj->q2->array[obj->q2->top - 1];//返回栈顶元素 } bool myQueueEmpty(MyQueue* obj) {//判空 assert(obj); if (obj->q1->size == 0 && obj->q2->size == 0) {//两个栈都为空，队列为空 return true; } return false; } void myQueueFree(MyQueue* obj) {//销毁 assert(obj); free(obj->q1->array); free(obj->q1); free(obj->q2->array); free(obj->q2); free(obj); }
