前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧

速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧

作者头像
鸽芷咕
发布于 2023-12-25 15:00:26
980
发布于 2023-12-25 15:00:26
举报
文章被收录于专栏：C++干货基地C++干货基地
在这里插入图片描述
在这里插入图片描述

🎬 鸽芷咕：个人主页 🔥个人专栏:《Linux深造日志》《C++干货基地》

⛺️生活的理想，就是为了理想的生活!

📋 前言

🌈hello！ 各位铁铁们大家好啊，栈和队列我们都学过了那么试试用队列实现栈你会嘛？。 ⛳️本篇文章就来给大家来篇如何用队列来实现栈的全部解析让你彻底拿捏队列。 📚本期文章收录在《数据结构&算法》，大家有兴趣可以看看呐！ ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝！

文章目录
  • 📋 前言
  • 一、队列实现栈的具体功能
  • 二、队列实现栈的具体思路
    • 2.1 实现栈区的具体方法
    • 2.1 栈区的插入思路
    • 2.1 栈区的删除思路
  • 三、队列实现栈（具体代码）
    • 3.1 队列的准备
    • 3.2 栈区的初始化
    • 3.3 栈区的插入
    • 3.4 栈区的删除
    • 3.5 栈区的判空
    • 3.6 获取栈区的头元素
    • 3.7 栈区的销毁
  • 三、全部实现代码
  • 📝全篇总结

一、队列实现栈的具体功能

在这里插入图片描述
在这里插入图片描述

二、队列实现栈的具体思路

我们先来总结一下队列的特点 先进先出 ，队列的特点 是 后进先出 ：

  • 具体我们可以看一下下图来快速了解
在这里插入图片描述
在这里插入图片描述
  • 队列的特点是先进先出
  • 我们要实现栈的功能是后进先出

2.1 实现栈区的具体方法

我们是不是可以具体这样想，队列既然是先进先出，栈是后进先出，的意识就是我们需要每次获取的栈区数据是队列的最后一个：

  • ⁉️那可以不可以这样呢？
  • 开辟俩个队列空间，每次让其中一个为空
  • 另外一个不为空，这样就可以解决删除的问题了。
在这里插入图片描述
在这里插入图片描述

2.1 栈区的插入思路

这思路就很简单如果使用俩个指针来管理队列，那么插入就非常简单了，只需要考虑俩种情况：

  • 第一种当然是俩个栈区都为空的情况，还没开始插数据
  • 第二种就是已经插入数据了，那么插入的时候直接往不为空的栈区插入就好了。

2.1 栈区的删除思路

大家看如何我们使用俩个指针来管理队列，来实现栈的话那么来删除就非常简单了为什么这样说呢？

  • 既然一个队列永远为空，一个不为空
  • 那么删除的时候直接把不为空的队列插入到为空的队列
  • 留下最后一个元素用来删除就好了
在这里插入图片描述
在这里插入图片描述

三、队列实现栈（具体代码）

好了以上就是队列实现栈的核心思想了，只要核心思想掌握了，那么其他就是小菜了。下面我们就来快速实现一下吧：

3.1 队列的准备

这里是队列的实现代码，由于C语言库里面并没有队列这个数据结构我们就只能手动实现了：

  • 如果有想了解队列的可以看这篇文章：
代码语言：javascript
复制
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QueDataType;

typedef struct QueueType {
	QueDataType data;
	struct QueueType* next;
}QueueNode;

typedef struct Queue {
	struct QueueType* head;
	struct QueueType* tail;
	int size;
}Que;

//初始化队列
void QueueInit(Que* ps);
//销毁队列
void QueueDestroy(Que* ps);
//插入数据
void QueuePush(Que* ps, QueDataType x);
//删除数据
void QueuePop(Que* ps);
//获取头数据
QueDataType QueueFront(Que* ps);
//获取尾数据
QueDataType QueueBack(Que* ps);
//获取队列长度
int QueueSize(Que* ps);
//判断是否为空
bool QueueEmpty(Que* ps);


//初始化队列
void QueueInit(Que* ps)
{
	assert(ps);

	ps->head = NULL;
	ps->tail = NULL;
	ps->size = 0;
}

//销毁队列
void QueueDestroy(Que* ps)
{
	assert(ps);
	QueueNode* cur = ps->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->size = 0;
}

//插入数据
void QueuePush(Que* ps, QueDataType x)
{
	assert(ps);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}

	ps->size++;
}


//删除数据
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

//获取头数据
QueDataType QueueFront(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

//获取尾数据
QueDataType QueueBack(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));


	return ps->tail->data;
}

//获取队列长度
int QueueSize(Que* ps)
{
	assert(ps);
	
	return ps->size;
}

//判断是否为空
bool QueueEmpty(Que* ps)
{
	assert(ps);

	return ps->head == NULL;
}

3.2 栈区的初始化

好了思路我们理清楚了接下来就是看看具体队列实现栈的代码到底如何实现：

  • 前面我们说过了使用俩个指针来管理队列就好了
  • 然后进行 malloc 申请空间就好了

📚 代码演示：

代码语言：javascript
复制
typedef struct {
    Que q1;
    Que q2;

} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);

    return obj;
}

3.3 栈区的插入

插入的话我们思想已经都知道，下面就是考验你的代码能力了：

  • 如果俩个队列为空随便插入一个就好了
  • 否则就插入另一个队列

📚 代码演示：

代码语言：javascript
复制
void myStackPush(MyStack* obj, int x) {
    assert(obj);

    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }

}

3.4 栈区的删除

删除的思想很简单，每次搬运一下队列就好了：

  • 这里使用了一个非常实用的判定方法大家可以去看看
  • 先假设一个为空一个不为空
  • 然后如果错了就换过来

📚 代码演示：

代码语言：javascript
复制
int myStackPop(MyStack* obj) {
    assert(obj);

    Que* empty = &obj->q1;
    Que* noempty = &obj->q2;
    if(!QueueEmpty(empty))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }

    while(QueueSize(noempty) > 1)
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }

    int top = QueueFront(noempty);
    QueuePop(noempty);
    
    return top;
}

3.5 栈区的判空

这个就简单了只要栈中管理俩个队列的的都为空那当然都没有数据了：

  • QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2)

📚 代码演示：

代码语言：javascript
复制
bool myStackEmpty(MyStack* obj) {

    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

3.6 获取栈区的头元素

既然我们使用了俩个队列来实现栈，并且只有一个队列存放数据。

  • 那么只需要看哪个队列不为取出队尾数据就好了。

📚 代码演示：

代码语言：javascript
复制
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

3.7 栈区的销毁

老样子了，先把栈区里面的 malloc 里面的空间释放了，然后再释放栈就好了。

📚 代码演示：

代码语言：javascript
复制
void myStackFree(MyStack* obj) {  
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    

    free(obj);

}

三、全部实现代码

📚 代码演示：

代码语言：javascript
复制
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QueDataType;

typedef struct QueueType {
	QueDataType data;
	struct QueueType* next;
}QueueNode;

typedef struct Queue {
	struct QueueType* head;
	struct QueueType* tail;
	int size;
}Que;

//初始化队列
void QueueInit(Que* ps);
//销毁队列
void QueueDestroy(Que* ps);
//插入数据
void QueuePush(Que* ps, QueDataType x);
//删除数据
void QueuePop(Que* ps);
//获取头数据
QueDataType QueueFront(Que* ps);
//获取尾数据
QueDataType QueueBack(Que* ps);
//获取队列长度
int QueueSize(Que* ps);
//判断是否为空
bool QueueEmpty(Que* ps);


//初始化队列
void QueueInit(Que* ps)
{
	assert(ps);

	ps->head = NULL;
	ps->tail = NULL;
	ps->size = 0;
}

//销毁队列
void QueueDestroy(Que* ps)
{
	assert(ps);
	QueueNode* cur = ps->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->size = 0;
}

//插入数据
void QueuePush(Que* ps, QueDataType x)
{
	assert(ps);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}

	ps->size++;
}


//删除数据
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

//获取头数据
QueDataType QueueFront(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

//获取尾数据
QueDataType QueueBack(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));


	return ps->tail->data;
}

//获取队列长度
int QueueSize(Que* ps)
{
	assert(ps);
	
	return ps->size;
}

//判断是否为空
bool QueueEmpty(Que* ps)
{
	assert(ps);

	return ps->head == NULL;
}

typedef struct {
    Que q1;
    Que q2;

} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);

    return obj;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);

    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }

}

int myStackPop(MyStack* obj) {
    assert(obj);

    Que* empty = &obj->q1;
    Que* noempty = &obj->q2;
    if(!QueueEmpty(empty))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }

    while(QueueSize(noempty) > 1)
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }

    int top = QueueFront(noempty);
    QueuePop(noempty);

    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) {  
    QueueDestroy(&obj->q1);
    QueueDestroy(&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);
*/

📝全篇总结

☁️ 好了以上就是队列实现栈的全部细节与过程来，大家不要忘记练习哦！ 看到这里了还不给博主扣个： ⛳️ 点赞☀️收藏 ⭐️ 关注！ 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要！ 你们的点赞就是博主更新最大的动力！ 有问题可以评论或者私信呢秒回哦。

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-11-05，如有侵权请联系 cloudcommunity@tencent.com 删除
数据结构
ps
队列
技巧
数据

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数据结构
ps
队列
技巧
数据
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 📋 前言
    • 文章目录
    • 一、队列实现栈的具体功能
    • 二、队列实现栈的具体思路
      • 2.1 实现栈区的具体方法
        • 2.1 栈区的插入思路
          • 2.1 栈区的删除思路
          • 三、队列实现栈（具体代码）
            • 3.1 队列的准备
              • 3.2 栈区的初始化
                • 3.3 栈区的插入
                  • 3.4 栈区的删除
                    • 3.5 栈区的判空
                      • 3.6 获取栈区的头元素
                        • 3.7 栈区的销毁
                        • 三、全部实现代码
                        • 📝全篇总结
                        领券

                        腾讯云开发者

                        扫码关注腾讯云开发者

                        扫码关注腾讯云开发者

                        领取腾讯云代金券

                        热门产品

                        热门推荐

                        更多推荐

                        Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

                        深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

                        腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

                        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

                        Copyright © 2013 - 2024 Tencent Cloud.

                        All Rights Reserved. 腾讯云 版权所有

                        登录 后参与评论