【不太正常的题】LeetCode.232:用栈的函数接口实现队列

个人主页：我们的五年

系列专栏：初阶数据结构刷题

欢迎大家点赞评论收藏⭐文章

  1.问题描述：

 题目中说了只能使用两个栈实现队列，并且只能使用基本的栈操作。比如：在栈顶进行入栈操作，在栈顶进行出栈，取栈顶元素，还有判空这些基本的栈操作函数。然后使用这些函数实现队列的基本操作，队列的特点就是在队尾插入数据，在队头删除数据，在对头取数据。

题中说使用两个栈实现，也给了我们提示。

  2.问题分析：

假如先在一个栈中插入三元素1.2.3。

当使用StackPush函数在PushST进行三次插入以后，就变成了上面的情形，但是如果我们要进行队列取队头的数据，进行队列删除队头的数据，我们就要先把上面的3和2拿走。从而我们就想到了把左边栈里面的元素的放到右边去。

进行上面的操作以后，我们就调用栈的取栈顶的函数就可以拿到元素1，也可以进行取删除元素1，就可以达到和队列一样的性质：先进先出。

插入数据的时候，我们还是在PushST中插入数据，加入先插入4，5.

如果要进行删除操作，取元素操作也是可以直接在PopST栈中直接取。也是满足队列的要求的。但是当我们把PopST的元素都取完以后，我们就要再一次把PushST栈里面的元素导到PopST栈里面。

按照上面的步骤就可以实现队列的操作。

 3.代码层面进行解析：

栈的函数接口

先给出栈的接口：

typedef int SLDataType;

typedef struct Stack{

            SLDataType* a;

            int top;

            int capacity;

}Stack;

//对栈进行初始化

void StackInit(Stack* ptr);

//对栈进行销毁

void StackDestroy(Stack* ptr);

//在栈顶插入元素

void StackPush(Stack* ptr, SLDataType x);

//获取栈顶元素

SLDataType StackTop(Stack* ptr);

//对栈进行判断，如果为空，返回true，否则返回false

bool StackEmpty(Stack* ptr);

//销毁栈的栈顶元素

void StackPop(Stack* ptr);

用栈的函数实现队列

先定义我自己结构体的类型：

根据上面分析也是用两个栈实现队列，也就是说我的队列类型中保护了两个栈，并且我把这两个队列命名为PushST和PopST

typedef struct {     Stack PushST;        //把元素新的元素放在这个栈，也就是在这个栈里面实现插入操作     Stack PopST;         //在这个栈中取数据，删除数据} MyQueue;

创建队列，在堆区上申请一块空间，并且对队列里面的栈进行初始化

MyQueue* myQueueCreate() {     MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));     StackInit(&obj->PushST);      //对PushST和PopST栈进行初始化       StackInit(&obj->PopST);     return obj;}

取队头元素

int myQueuePeek(MyQueue* obj) {    if(StackEmpty(&obj->PopST))    //PopST栈为空的时候就要把PushST栈里面的元素导过来    {        while(!StackEmpty(&obj->PushST))    //导元素        {            int Pop=StackTop(&obj->PushST);            StackPop(&obj->PushST);            StackPush(&obj->PopST,Pop);        }    }    return StackTop(&obj->PopST);    返回PopST栈顶的元素}

销毁队头元素，并且返回队头元素。首先应该保存PopST栈的栈顶元素，然后销毁栈顶元素。

一个特别巧妙的点就是，我们在进行取队头元素的时候，如果PopST为空，取队头元素函数就会把PushST里面的元素导到PopST里面，这样我们在myQueuePop中就避免了导元素这一步骤。

int myQueuePop(MyQueue* obj) {    int top=myQueuePeek(obj);    //取队头元素    StackPop(&obj->PopST);    return top;}

 最后的push函数和判空函数还有销毁函数也是比较简单的

//直接在PushST队列中进行插入void myQueuePush(MyQueue* obj, int x) {    StackPush(&obj->PushST,x);}//队列判空，当队列里面的两个队列都为空时才为空bool myQueueEmpty(MyQueue* obj) {    return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);}//销毁队列void myQueueFree(MyQueue* obj) {    StackDestroy(&obj->PopST);    StackDestroy(&obj->PushST);}

 最终代码:

typedef int SLDataType;typedef struct Stack{SLDataType* a;int top;int capacity;}Stack;//对栈进行初始化void StackInit(Stack* ptr);//对栈进行销毁void StackDestroy(Stack* ptr);//在栈顶插入元素void StackPush(Stack* ptr, SLDataType x);//获取栈顶元素SLDataType StackTop(Stack* ptr);//对栈进行判断，如果为空，返回true，否则返回falsebool StackEmpty(Stack* ptr);void StackPop(Stack* ptr);//栈的初始化void StackInit(Stack* ptr){assert(ptr);ptr->a = NULL;ptr->capacity = ptr->top = 0;}//销毁栈void StackDestroy(Stack* ptr){assert(ptr);free(ptr->a);ptr->a = NULL;ptr->capacity = ptr->top = 0;//初始化时，top=0，表示指向栈顶的下一个元素}//在栈顶插入元素void StackPush(Stack* ptr, SLDataType x){assert(ptr);if (ptr->top == ptr->capacity){int newcapacity = ptr->capacity == 0 ? 4 : ptr->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ptr->a, newcapacity*sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");return;}ptr->a = tmp;ptr->capacity = newcapacity;}ptr->a[ptr->top++] = x;}//取栈顶元素SLDataType StackTop(Stack* ptr){assert(ptr);assert(!StackEmpty(ptr));return ptr->a[ptr->top - 1];}//栈判空bool StackEmpty(Stack* ptr){assert(ptr);return ptr->top == 0;}//销毁栈顶元素void StackPop(Stack* ptr){assert(ptr);assert(!StackEmpty(ptr));ptr->top--;}typedef struct {    Stack PushST;    Stack PopST;} MyQueue;MyQueue* myQueueCreate() {    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));    StackInit(&obj->PushST);    StackInit(&obj->PopST);    return obj;}void myQueuePush(MyQueue* obj, int x) {    StackPush(&obj->PushST,x);}int myQueuePop(MyQueue* obj) {    int top=myQueuePeek(obj);    StackPop(&obj->PopST);    return top;}int myQueuePeek(MyQueue* obj) {    if(StackEmpty(&obj->PopST))    {        while(!StackEmpty(&obj->PushST))        {            int Pop=StackTop(&obj->PushST);            StackPop(&obj->PushST);            StackPush(&obj->PopST,Pop);        }    }    return StackTop(&obj->PopST);}bool myQueueEmpty(MyQueue* obj) {    return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);}void myQueueFree(MyQueue* obj) {    StackDestroy(&obj->PopST);    StackDestroy(&obj->PushST);}/** * 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);*/