【数据结构】用栈实现队列

💯💯💯

⏰1.用栈实现队列

思路：
一个栈专门用来插入数据
一个栈专门用来出数据

比如如果栈里有5个数据，而要根据队列的特性，出队列肯定出的是队头数据，也就是1，而在栈里，怎么才能将数据1删除掉呢？

我们的做法是：将栈1的数据全部导入到栈2去。这样由原来的数据就倒过来了，那删除栈顶元素即可。

删除栈顶元素之后，我们分析发现，这时的栈2如果再进行删除，就和队列的删除操作是一致的了，不需要再导回去，如果要再删除队头数据2，直接让栈2删除即可。
所有我们发现经过一次导数据之后，栈2就完全可以当成pop数据的。
那我们如果想插入数据，该怎么插入呢？
根据队列特性，我们只能从队尾插入，也就是元素5的后面插入数据。该怎么插呢？将数据插入栈2里？那可不行，将数据插入栈2中后，原来的顺序就乱了。所以我们将数据插入到栈1去，比如我们要插入数据6，7，8.直接插入到栈1即可。

这样就不会影响栈2出数据的顺序了，并且插入的顺序也不受出数据的影响。
唯一需要注意的是，当栈2的数据都删除空了，这时就需要将栈1的数据再导入到栈2中，这样就能接着删除队列中的数据了。

所以我们可以直接定义两个栈，一个栈用来插入数据，一个栈用来删除数据。

typedef struct 
{  ST pushst;ST popst;
} MyQueue;

不过在定义之前我们需要写一个栈的数据结构，因为C语言是没有自己的栈的。

typedef int STData;
typedef struct Stack
{int* a;int top;int capicty;
}ST;
void STInit(ST*ps);//初始化栈表
void STDestroy(ST* ps);//销毁栈表
void STpush(ST* ps,STData x);//压栈，在栈顶压入一个元素
void STpop(ST* ps);//出栈，在栈顶弹出一个元素。
STData STTop(ST* ps);//访问栈顶元素
int STSize(ST* ps);
int STEmpty(ST*ps);//
void STInit(ST* ps)//初始化栈表
{assert(ps);//判断结构体指针不为NULL；//一上来可以给栈表初始化容量ps->a = (STData*)malloc(sizeof(STData) * 4);if (ps->a == NULL)//判断是否开辟成功{perror("malloc");}//初始话容量为4ps->capicty = 4;ps->top = 0;//top=0 表示的是指向栈顶元素的下一个位置//top如果为-1，则表示栈顶元素的位置
}
void STDestroy(ST* ps)//销毁栈表
{assert(ps);free(ps->a);ps->a = NULL;ps->capicty = 0;ps->top = 0;}
void STpush(ST* ps, STData x)//压栈，在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{assert(ps);//断言判断if (ps->top == ps->capicty){//增容STData* tmp = (STData*)realloc(ps->a, sizeof(STData) * ps->capicty * 2);if (tmp == NULL){perror("realloc");}ps->a = tmp;ps->capicty *= 2;}ps->a[ps->top] = x;//将元素压入栈顶，一开始top是0，当元素进去后，再让top指向该栈顶元素后一个位置ps->top++;
}
int STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STpop(ST* ps)//出栈，在栈顶弹出一个元素。
{assert(ps);//删除元素之前要检查栈表是否还有元素可删assert(!STEmpty(ps));//当栈表为NULL是断言ps->top--;}
int STSize(ST* ps)//计算栈表长度
{assert(ps);return ps->top;//top的长度就是栈表的长度
}
STData STTop(ST* ps)//访问栈顶元素
{assert(ps);return ps->a[ps->top - 1];
}

接下来就是获取一个指向 MyQueue队列的指针。

MyQueue* myQueueCreate() //发现没有传入参数并且返回值是指向栈的指针说明里面是用malloc开辟的内存而不是在栈上开辟的
{MyQueue *q=(MyQueue*)malloc(sizeof(MyQueue));if(q==NULL){perror("malloc");}STInit(&q->pushst);//一开始需要对两个栈进行初始化STInit(&q->popst);return q;
}

🕐"入队列"

入队列，即插入数据，直接在push栈进行插入即可，不用担心顺序什么的，因为当pop栈没有数据时，就会让push栈导数据过来，这时的顺序就符合队列的要求了

void myQueuePush(MyQueue* obj, int x) 
{//只管往pushst里插入即可，不需要管其他STpush(&obj->pushst,x);
}

🕑"出队列"

出队列呢就指望pop栈即可，不过在出队列之前，我们需要检查一下pop栈里是否为空，如果为空，就需要将push栈里的数据导过来，如果不为空，那就可以进行删除操作了。

int myQueuePop(MyQueue* obj) 
{//需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可{STpush(&obj->popst,STTop(&obj->pushst));STpop(&obj->pushst);//删除push栈里的这个数据}}//走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空int top=STTop(&obj->popst);//将这个栈顶元素记录下来，最后需要返回STpop(&obj->popst);return top;
}

🕒"获取队头元素"

获取队头数据，这个操作与刚刚的删除操作基本一样，只不过该操作不需要将数据删除，直接返回栈顶元素即可，所以大部分代码是一样的。

int myQueuePeek(MyQueue* obj) 
{//这里跟pop数据很像,直接return 栈顶元素即可//需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可{STpush(&obj->popst,STTop(&obj->pushst));STpop(&obj->pushst);}}//走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空return STTop(&obj->popst);}

🕔"判断队列是否为空"

判断队列是否为空其实很简单，因为该队列是由两个栈构成，当两个栈都为空时，则该队列肯定为空。

bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}

🕕"销毁队列"

销毁队列也简单，要想真正的释放该队列，需要理解该队列的结构是如何构成的。
该队列是由两个栈构成，栈是由数组构成。

释放空间从里到外释放，先释放两个栈空间，再释放队列空间。

void myQueueFree(MyQueue* obj) 
{STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}

⏰2.完整代码

typedef int STData;
typedef struct Stack
{int* a;int top;int capicty;
}ST;
void STInit(ST*ps);//初始化栈表
void STDestroy(ST* ps);//销毁栈表
void STpush(ST* ps,STData x);//压栈，在栈顶压入一个元素
void STpop(ST* ps);//出栈，在栈顶弹出一个元素。
STData STTop(ST* ps);//访问栈顶元素
int STSize(ST* ps);
int STEmpty(ST*ps);//
void STInit(ST* ps)//初始化栈表
{assert(ps);//判断结构体指针不为NULL；//一上来可以给栈表初始化容量ps->a = (STData*)malloc(sizeof(STData) * 4);if (ps->a == NULL)//判断是否开辟成功{perror("malloc");}//初始话容量为4ps->capicty = 4;ps->top = 0;//top=0 表示的是指向栈顶元素的下一个位置//top如果为-1，则表示栈顶元素的位置
}
void STDestroy(ST* ps)//销毁栈表
{assert(ps);free(ps->a);ps->a = NULL;ps->capicty = 0;ps->top = 0;}
void STpush(ST* ps, STData x)//压栈，在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{assert(ps);//断言判断if (ps->top == ps->capicty){//增容STData* tmp = (STData*)realloc(ps->a, sizeof(STData) * ps->capicty * 2);if (tmp == NULL){perror("realloc");}ps->a = tmp;ps->capicty *= 2;}ps->a[ps->top] = x;//将元素压入栈顶，一开始top是0，当元素进去后，再让top指向该栈顶元素后一个位置ps->top++;
}
int STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STpop(ST* ps)//出栈，在栈顶弹出一个元素。
{assert(ps);//删除元素之前要检查栈表是否还有元素可删assert(!STEmpty(ps));//当栈表为NULL是断言ps->top--;}
int STSize(ST* ps)//计算栈表长度
{assert(ps);return ps->top;//top的长度就是栈表的长度
}
STData STTop(ST* ps)//访问栈顶元素
{assert(ps);return ps->a[ps->top - 1];
}
typedef struct 
{  ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue *q=(MyQueue*)malloc(sizeof(MyQueue));if(q==NULL){perror("malloc");}STInit(&q->pushst);STInit(&q->popst);return q;
}void myQueuePush(MyQueue* obj, int x) 
{//只管往pushst里插入即可，不需要管STpush(&obj->pushst,x);
}int myQueuePop(MyQueue* obj) 
{//需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可{STpush(&obj->popst,STTop(&obj->pushst));STpop(&obj->pushst);}}//走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空int top=STTop(&obj->popst);STpop(&obj->popst);return top;
}int myQueuePeek(MyQueue* obj) 
{//这里跟pop数据很像,直接return 栈顶元素即可//需要讨论下，当pop这个栈为空时，需要将push栈中的数据导过来if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst))//将push栈中的所有数据都导过去即可{STpush(&obj->popst,STTop(&obj->pushst));STpop(&obj->pushst);}}//走到这里有两种情况，可能push栈里的数据导光了，也可能是pop栈里本来就有数据，不为空return STTop(&obj->popst);}bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&obj->pushst)&&STEmpty(&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);
*/