【数据结构算法经典题目刨析（c语言）】使用栈实现队列（图文详解）
💓 博客主页：C-SDN花园GGbond
⏩ 文章专栏：数据结构经典题目刨析(c语言)
目录
一.题目描述
二.解题思路
三.代码实现
一.题目描述
题目链接: 用栈实现队列
二.解题思路
此题可以用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作
出队操作： 当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作上一章节, 我们使用了队列来实现栈, 本次我们使用栈来实现队列, 两道题的思路都是差不多的, 本题使用两个栈实现队列, 我们可以让一个栈进行插入操作, 另一个栈进行出队列操作, 插入元素到pushst中, 如果需要删除元素, 先判断popst是否为空, 为空的话把pushst中所有元素导入到popst中, 只需要导一次, 然后如果不为空, 只需要pop出栈顶元素.
画图演示:
三.代码实现
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* pst)
{assert(pst);pst->a = NULL;//指向栈顶数据的下一个位置pst->top = 0;pst->capacity = 0;
}
void Destroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//入栈和出栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->capacity == pst->top){int newCapacity = pst->capacity==0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("malloc fail");return;}pst->a = tmp;pst->capacity = newCapacity;}pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst)
{assert(pst);assert(pst->top>0);pst->top--;
}//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}typedef struct {ST pushst;ST popst;} MyQueue;MyQueue* myQueueCreate() {MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);}int myQueuePop(MyQueue* obj) {if(STEmpty(&obj->popst)){while(STSize(&obj->pushst)>0){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}int ret=STTop(&obj->popst);STPop(&obj->popst);return ret;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(STSize(&obj->pushst)>0){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}int ret=STTop(&obj->popst);return ret;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {Destroy(&obj->pushst);Destroy(&obj->popst);free(obj);
}