用栈实现队列

举报
芒果_Mango 发表于 2022/07/31 23:15:56 2022/07/31
【摘要】 大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流作者简介:CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog掘金LV3用户 https://juejin.cn/us...

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

题目

https://leetcode-cn.com/problems/implement-queue-using-stacks/

image-20220209220403387

栈：后进先出

队列：先进先出

如何用两个栈实现队列：

  • 方法
  • 一个栈PushST 用于插入数据，一个栈PopST 用于出数据

当要入数据时：往PushST栈入数据

当要出数据时：如果PopST栈中有数据，就直接出栈顶数据，如果没有数据，就把PushST栈的数据导入到PopST栈，再出栈顶数据

  • 将数据从PushST栈导入到PopST栈，可以得到入栈顺序，从而实现队列的先进先出

image-20220209220424299

注意：PushST栈和PopST栈可以同时有数据，，但是只在PushST栈中入数据，出数据在PopST栈中出数据

当PopST栈中无数据，就把PushST栈中的数据导过去

队列结构

typedef struct {
    ST PushST;//一个栈用来入元素
    ST PopST;//一个栈用来出数据
} MyQueue;

image-20220209220430410

注意点：

//写法1
struct {
    ST PushST;//一个栈用来入元素
    ST PopST;//一个栈用来出数据
} MyQueue;
​
//写法2
typedef struct {
    ST PushST;//一个栈用来入元素
    ST PopST;//一个栈用来出数据
} MyQueue;

写法1：MyQueue是一个匿名结构体

匿名结构体 - 没有名称

MyStack就是一个变量，一次性用品

//写法1
struct {
    int a;
    int  b;
}MyQueue;
​
int main()
{
    //MyQueue是一个变量
    MyQueue.a = 1;
    MyQueue.b = 2;
    printf("%d %d\n", MyQueue.a, MyQueue.b);// 1 2
    return 0;
}

写法2：MyStack是结构体类型 ,可以定义变量

typedef struct {
    int a;
    int  b;
}MyQueue;
​
int main()
{
    //MyQueue是结构体类型
    MyQueue tmp;
    tmp.a = 1;
    tmp.b = 2;
    printf("%d %d\n", tmp.a, tmp.b);// 1 2
    return 0;
}

队列初始化

//新建队列：返回地址
MyQueue* myQueueCreate() 
{
    //动态开辟一个队列结构体，里面含两个栈
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    //初始化两个栈
    //把栈的地址传过去
    StackInit(&q->PushST);
    StackInit(&q->PopST);
    return q;
}

错误写法：

MyQueue* myQueueCreate() 
{
    MyQueue q;
    return  &q;
}

这样写是错误的，q出了作用域就销毁了(栈空间)

q是野指针，相当于返回了栈空间地址问题

入数据

image-20220209220436148

void myQueuePush(MyQueue* obj, int x)
{
    //入数据只在PushST栈中入
    StackPush(&obj->PushST,x);
}

出数据

image-20220209220445961

int myQueuePop(MyQueue* obj)
{
    //出数据在PopST栈中出
    
    //如果PopST栈中没有数据，就把PushST栈的数据导过去
    if(StackEmpty(&obj->PopST))
    {
        //把PushST的数据导过去
        while(!StackEmpty(&obj->PushST))
        {
            //得到PushST栈顶数据
            STDataType tmp = StackTop(&obj->PushST);
            //把PushST栈顶数据放到PopST栈
            StackPush(&obj->PopST,tmp);
            //PushST栈顶数据出栈
            StackPop(&obj->PushST);
        }
    }
    //题目要求：出数据要返回队头数据
    int front = StackTop(&obj->PopST);
    StackPop(&obj->PopST);
    return front;
}

题目要求出数据还要返回此时的队头数据

得到队头数据

image-20220209220455763

//思路和出数据基本一致，只是不需要Pop掉 PopST的栈顶数据
int myQueuePeek(MyQueue* obj)
{
     //出数据在PopST栈中出
    //如果PopST栈中没有数据，就把PushST栈的数据导过去
    if(StackEmpty(&obj->PopST))
    {
        while(!StackEmpty(&obj->PushST))
        {
            STDataType tmp = StackTop(&obj->PushST);
            StackPush(&obj->PopST,tmp);
            StackPop(&obj->PushST);
        }
    }
    int front = StackTop(&obj->PopST);
    return front;
}

释放空间

image-20220209220507950

注意：

image-20220209220515686

void myQueueFree(MyQueue* obj) 
{
    //先释放两个栈空间
    StackDestroy(&obj->PopST);
    StackDestroy(&obj->PushST);
    //再释放动态开辟的队列结构体
    free(obj);
}

队列是否为空

image-20220209220523461

bool myQueueEmpty(MyQueue* obj)
{
    //如果两个栈都为空->说明队列为空
    return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}

接口实现

typedef struct {
    ST PushST;//一个栈用来入元素
    ST PopST;//一个栈用来出数据
} MyQueue;

//新建队列：返回地址
MyQueue* myQueueCreate() 
{
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->PushST);
    StackInit(&q->PopST);
    return q;
}

void myQueuePush(MyQueue* obj, int x)
{
    //入数据在PushST栈中入
    StackPush(&obj->PushST,x);
}

int myQueuePop(MyQueue* obj)
{
    //出数据在PopST栈中出
    //如果PopST栈中没有数据，就把PushST栈的数据导过去
    if(StackEmpty(&obj->PopST))
    {
        while(!StackEmpty(&obj->PushST))
        {
            STDataType tmp = StackTop(&obj->PushST);
            StackPush(&obj->PopST,tmp);
            StackPop(&obj->PushST);
        }
    }
    int front = StackTop(&obj->PopST);
    StackPop(&obj->PopST);
    return front;
}

int myQueuePeek(MyQueue* obj)
{
     //出数据在PopST栈中出
    //如果PopST栈中没有数据，就把PushST栈的数据导过去
    if(StackEmpty(&obj->PopST))
    {
        while(!StackEmpty(&obj->PushST))
        {
            STDataType tmp = StackTop(&obj->PushST);
            StackPush(&obj->PopST,tmp);
            StackPop(&obj->PushST);
        }
    }
    int front = StackTop(&obj->PopST);
    return front;
}

bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->PopST);
    StackDestroy(&obj->PushST);
    free(obj);
}

总代码

//现在栈存放的是字符
typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0; // ps->top = -1;
	ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return ps->top == 0;
}



typedef struct {
    ST PushST;//一个栈用来入元素
    ST PopST;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));

    StackInit(&q->PushST);
    StackInit(&q->PopST);

    return q;
}

void myQueuePush(MyQueue* obj, int x)
{
    //入数据在PushST栈中入
    StackPush(&obj->PushST,x);
}

int myQueuePop(MyQueue* obj)
{
    //出数据在PopST栈中出
    //如果PopST栈中没有数据，就把PushST栈的数据导过去
    if(StackEmpty(&obj->PopST))
    {
        while(!StackEmpty(&obj->PushST))
        {
            STDataType tmp = StackTop(&obj->PushST);
            StackPush(&obj->PopST,tmp);
            StackPop(&obj->PushST);
        }
    }
    int front = StackTop(&obj->PopST);
    StackPop(&obj->PopST);
    return front;
}

int myQueuePeek(MyQueue* obj)
{
     //出数据在PopST栈中出
    //如果PopST栈中没有数据，就把PushST栈的数据导过去
    if(StackEmpty(&obj->PopST))
    {
        while(!StackEmpty(&obj->PushST))
        {
            STDataType tmp = StackTop(&obj->PushST);
            StackPush(&obj->PopST,tmp);
            StackPop(&obj->PushST);
        }
    }
    int front = StackTop(&obj->PopST);
    return front;
}

bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->PopST);
    StackDestroy(&obj->PushST);
    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);
*/

\

【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入