栈和队列算法题 - 用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/
代码:
typedef int STDataType;
typedef struct Stack
{
//底层是数组,动态的
STDataType* arr;
//记录栈当前的容量
int capacity;
//记录栈里面数据的有效个数
int top;//栈顶
}ST;
//初始化
void StackInit(ST* ps)
{
//不能传空指针
assert(ps);
//指向栈的指针置为空
ps->arr = NULL;
//内存大小以及有效元素个数
ps->capacity = ps->top = 0;
}
//判断栈是否为空
//布尔类型要记得加头文件,stdbool.h
bool StackEmpty(ST* ps)
{
//不能传空指针
assert(ps);
//当有效元素个数为0是表示栈为空,返回true
return ps->top == 0;
}
//销毁
void StackDestroy(ST* ps)
{
//不能传空指针
assert(ps);
//判断指向栈的指针是否为空
if (ps->arr != NULL)
{
//销毁动态申请的空间
free(ps->arr);
//将该指针置为空指针,防止变为野指针
ps->arr = NULL;
}
//将空间大小和有效元素格式置为0
ps->capacity = ps->top = 0;
}
//栈顶入数据
void StackPush(ST* ps, STDataType x)
{
//不能传空指针
assert(ps);
//判断是否需要增容，当空间大小和有效元素个数相等时,就需要增容
if (ps->capacity == ps->top)
{
//计算需要增容多大空间,初始capacity是0,所以要判断
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//增容
STDataType* newArr = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
//判断增容是否成功
if (newArr == NULL)
{
//打印错误信息并且退出
perror("realloc fail!\n");
exit(1);
}
//代码执行到这说明空间增容成功
ps->capacity = newCapacity;
ps->arr = newArr;
}
//将arr指向的空间的第top位置赋值x,top自增,因为栈顶要往上走
*(ps->arr + ps->top++) = x;
}
//栈顶出数据
void StackPop(ST* ps)
{
//不能传空指针
assert(ps);
//栈不能为空
assert(!StackEmpty(ps));
--ps->top;
}
//取栈顶元素
/*
取栈顶的元素就可以循环打印出栈里面的数据
*/
STDataType StackTop(ST* ps)
{
//不能传空指针已经栈为u空不能取数据
assert(ps && !StackEmpty(ps));
//返回栈中的top减一位置的数据
return *(ps->arr + ps->top - 1);
}
//获取栈中有效元素个数
int StackSize(ST* ps)
{
//不能传空指针
assert(ps);
return ps->top;
}
/*******************************************************************************/
typedef struct {
//创建两个栈
ST s1;
ST s2;
} MyQueue;
MyQueue* myQueueCreate() {
//申请空间
MyQueue* ptr = (MyQueue*)malloc(sizeof(MyQueue));
//初始化栈
StackInit(&ptr->s1);
StackInit(&ptr->s2);
//返回地址
return ptr;
}
//入队列
void myQueuePush(MyQueue* obj, int x) {
//哪个栈不为空往哪个栈里面插入数据
if(!StackEmpty(&obj->s1))
{
//插入s1栈
StackPush(&obj->s1,x);
}
else
{
//插入s2栈
StackPush(&obj->s1,x);
}
}
//出队列
int myQueuePop(MyQueue* obj) {
//找不为空的队列
//假设s2为非空的队列,s1为空队列
ST* empQ = &obj->s1;
ST* noneQ = &obj->s2;
//判断是否为空队列
if(!StackEmpty(&obj->s1))
{
empQ = &obj->s2;
noneQ = &obj->s1;
}
//将非空栈中的全部元素导入到空栈空
while(StackSize(noneQ) > 0)
{
StackPush(empQ,StackTop(noneQ));
//栈顶出数据
StackPop(noneQ);
}
int ret = StackTop(empQ);
//栈顶出数据
StackPop(empQ);
while(StackSize(empQ) > 0)
{
StackPush(noneQ,StackTop(empQ));
//栈顶出数据
StackPop(empQ);
}
return ret;
}
//取队头元素
int myQueuePeek(MyQueue* obj) {
//找不为空的队列
//假设s2为非空的队列,s1为空队列
ST* empQ = &obj->s1;
ST* noneQ = &obj->s2;
//判断是否为空队列
if(!StackEmpty(&obj->s1))
{
empQ = &obj->s2;
noneQ = &obj->s1;
}
//将非空栈中的全部元素导入到空栈空
while(StackSize(noneQ) > 0)
{
StackPush(empQ,StackTop(noneQ));
//栈顶出数据
StackPop(noneQ);
}
int ret = StackTop(empQ);
while(StackSize(empQ) > 0)
{
StackPush(noneQ,StackTop(empQ));
//栈顶出数据
StackPop(empQ);
}
return ret;
}
//判空
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}
//队列的销毁
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->s1);
StackDestroy(&obj->s2);
free(obj);
obj = NULL;
}
/**
* 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);
*/提交结果:
思路2:
代码:
typedef struct {
//创建两个栈
ST pushST;
ST popST;
} MyQueue;
MyQueue* myQueueCreate() {
//创建指针,指向队列
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
//对两个栈初始化
StackInit(&pst->pushST);
StackInit(&pst->popST);
//返回地址
return pst;
}
//往pushST中插入数据
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->pushST,x);
}
//1.检查popST是否为空
// 1) 不为空,直接出数据
// 2) 为空,pushST导入到popST中,然后出数据
int myQueuePop(MyQueue* obj) {
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST,StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
//取栈顶,删除栈顶元素并返回栈顶数据
int ret = StackTop(&obj->popST);
StackPop(&obj->popST);
return ret;
}
//取队头元素
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST) )
{
StackPush(&obj->popST,StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
//指向队列的指针也是需要销毁的
free(obj);
obj = NULL;
}提交结果:
原文地址：https://blog.csdn.net/m0_74271757/article/details/140587633
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！