Leetcode-用队列实现栈

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

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流
作者简介:
CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
掘金LV3用户 https://juejin.cn/user/1381426159953960
阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

https://leetcode-cn.com/problems/implement-stack-using-queues/

image-20220209220120880

思路：

栈：先进后出

队列：先进先出

保持一个队列为空，另一个队列存放数据

image-20220209220137722

image-20220209220203475

队列中的数据导入到另一个队列：元素插入的顺序不变

接口1：栈的结构

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

里面包含两个队列

image-20220209220212272

接口2：初始化

MyStack* myStackCreate() {
    //动态开辟一个栈结构体
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
	//使用我们自己实现的接口初始化两个队列
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

错误写法

MyStack* myStackCreate() {
    MyStack st ；
    return &st;
}

st是局部变量，出了函数，空间就被销毁了。st的地址是野指针，返回了已经销毁的栈空间的地址

接口3：插入数据

永远保持一个队列为空

image-20220209220221923 
// 入数据
void myStackPush(MyStack* obj, int x) {
       //往不为空的队列中入数据
        if(!QueueEmpty(&obj->q1))
        {
            QueuePush(&obj->q1,x);
        }
        else
        {
            QueuePush(&obj->q2,x);
        }
}

接口4： 删除数据

image-20220209220233097

//出数据
int myStackPop(MyStack* obj) 
{
    //把有数据的队列的数据导入到空队列

    //先假设某一个队列不为空，假设队列q1不为空，q2为空
    Queue* noemptyQ = &obj->q1; 
    Queue* emptyQ = &obj->q2;

    //如果q2不为空，说明假设反了
    if(!QueueEmpty(&obj->q2))
    {
        emptyQ = &obj->q1;
        noemptyQ = &obj->q2;
    }
    //把不空队列的数据导入到空队列，直到不空队列只剩一个元素
    while(QueueSize(noemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(noemptyQ));
        QueuePop(noemptyQ);
    }
    int top = QueueFront(noemptyQ);
    QueuePop(noemptyQ);
    return top;
}

接口5：返回栈顶数据

image-20220209220243112 
int myStackTop(MyStack* obj) 
{
    //那个队列有数据，就返回哪个队列的队尾数据
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

接口6：判断栈是否为空

如果两个队列都为空->栈为空

image-20220209220305198 
bool myStackEmpty(MyStack* obj) {
    //如果两个队列都为空->栈为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 
}

接口7：释放空间

image-20220209220319311

先调用我们自己写的接口：释放两个队列

然后再释放我们动态开辟的栈结构体

image-20220209220332641 
void myStackFree(MyStack* obj)
{
    //先释放两个队列
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    //再释放动态开辟的栈结构体
    free(obj);
}

实现的接口

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));

    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

// 入数据
void myStackPush(MyStack* obj, int x) {
       //往不为空的队列中入数据
        if(!QueueEmpty(&obj->q1))
        {
            QueuePush(&obj->q1,x);
        }
        else
        {
            QueuePush(&obj->q2,x);
        }
}
//出数据
int myStackPop(MyStack* obj) 
{
    //把有数据的队列的数据导入到空队列

    //先假设某一个队列不为空，假设队列q1不为空，q2为空
    Queue* noemptyQ = &obj->q1; 
    Queue* emptyQ = &obj->q2;

    //如果q2不为空，说明假设反了
    if(!QueueEmpty(&obj->q2))
    {
        emptyQ = &obj->q1;
        noemptyQ = &obj->q2;
    }
    //把不空队列的数据导入到空队列，直到不空队列只剩一个元素
    while(QueueSize(noemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(noemptyQ));
        QueuePop(noemptyQ);
    }
    int top = QueueFront(noemptyQ);
    QueuePop(noemptyQ);
    return top;

}

int myStackTop(MyStack* obj) 
{
    //那个队列有数据，就返回哪个队列的队尾数据
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    //如果两个队列都为空->栈为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 
}

void myStackFree(MyStack* obj)
{
    //先释放两个队列
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    //再释放动态开辟的栈结构体
    free(obj);
}

总代码


typedef int QDataType;
//队列中的结构体
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

//存放指向结构体的两个指针
typedef struct Queue
{
	QueueNode* head;//指向链表的头
	QueueNode* tail;//指向链表的尾
}Queue;

//初始化
void QueueInit(Queue* pq);

//销毁
void QueueDestory(Queue* pq);

//队尾入数据
void QueuePush(Queue* pq, QDataType x);

//队头出数据
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);

//取队尾数据
QDataType QueueBack(Queue* pq);

//队列的长度
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;

}

//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	//链表要遍历销毁结点，不能直接销毁
	QueueNode* cur = pq->head;
	while (cur)
	{
		//保存下一个结点
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}

//队尾入数据
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//相当于尾插
	
	//构建新结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->next = NULL;
	newnode->data = x;
	//情况1：链表为空
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}

	//情况2：
	//tail newnode 
	else
	{
		pq->tail->next = newnode; //尾插
	//注意如果一开始没有数据，pq->tail = NULL，此时会出错，相当于对空指针解引用
	//所以没有数据时需要单独判断
		pq->tail = newnode;//指向新的尾
	}
	
}

//队头出数据
void QueuePop(Queue* pq)
{
	assert(pq);
	//情况1：链表为空
	/*if (pq->head == NULL)
	{
		return -1;
	}*/
	assert(!QueueEmpty(pq));

	//情况2
	QueueNode* next = pq->head->next;//保存下一个结点
	free(pq->head);//释放队头
	pq->head = next;//next成为新的队头

	//注意！！！！如果一直删，删最后一个时候 此时next为NULL的,如果不把tail也置空，就会造成野指针
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//链表为空
	/*if (pq->head == NULL)
	{
		return -1;
	}*/
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

//队列的长度
int QueueSize(Queue* pq)
{
	assert(pq);
	//方法1：遍历统计
	//方法2：定义结构体时添加一个size变量，入数据：size++ 出数据size -- 用size标志队列长度

	//遍历统计
	QueueNode* cur = pq->head;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	/*if (pq -> head == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pq->head == NULL;
}


typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));

    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

// 入数据
void myStackPush(MyStack* obj, int x) {
       //往不为空的队列中入数据
        if(!QueueEmpty(&obj->q1))
        {
            QueuePush(&obj->q1,x);
        }
        else
        {
            QueuePush(&obj->q2,x);
        }
}
//出数据
int myStackPop(MyStack* obj) 
{
    //把有数据的队列的数据导入到空队列

    //先假设某一个队列不为空，假设队列q1不为空，q2为空
    Queue* noemptyQ = &obj->q1; 
    Queue* emptyQ = &obj->q2;

    //如果q2不为空，说明假设反了
    if(!QueueEmpty(&obj->q2))
    {
        emptyQ = &obj->q1;
        noemptyQ = &obj->q2;
    }
    //把不空队列的数据导入到空队列，直到不空队列只剩一个元素
    while(QueueSize(noemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(noemptyQ));
        QueuePop(noemptyQ);
    }
    int top = QueueFront(noemptyQ);
    QueuePop(noemptyQ);
    return top;

}

int myStackTop(MyStack* obj) 
{
    //那个队列有数据，就返回哪个队列的队尾数据
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    //如果两个队列都为空->栈为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 
}

void myStackFree(MyStack* obj)
{
    //先释放两个队列
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    //再释放动态开辟的栈结构体
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

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

全部回复

上滑加载中

设置昵称

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

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

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

确认 取消

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

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