【数据结构】有关栈和队列相互转换问题

文章目录

  • 用队列实现栈
    • 思路
    • 实现
  • 用栈实现队列
    • 思路
    • 实现

用队列实现栈

Leetcode-225 用队列实现栈
在这里插入图片描述

思路

建立队列的基本结构并实现队列的基本操作

这部分这里就不多说了，需要的可以看笔者的另一篇博客
【数据结构】队列详解(Queue)
就简单带过一下需要实现的功能

#define _CRT_SECURE_NO_WARNINGS 1

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(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);

使用两个队列实现
一个空的来实现操作，一个装数据来存储

我们以几个简单操作来理解一下

  • 栈的以队列实现的基本结构及初始化

因为队列的结构及功能是初始化的条件，在上一步中我们已经实现完成了
所以关于栈的结构只需要一个能够存储两个队列的结构体就行了

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

对于栈的初始化，因为我们要实现离开初始化操作后，两个队列和栈都需要存在，所以我们需要使用malloc为其创建内存

而两栈也是需要额外开辟空间的，这同样是在第一步中完成，这里笔者就不多说了，同样也是由malloc来创建内存的

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}
  • 尾插

因为要进行一系列操作，所以我们必须确保其中的一个队列为空。在这个基础上，我们可以对已有数据的队列进行操作，去实现功能。

所以我们就只需要判断两个队列中哪个为空，往另一个不为空的队列里加数据就行了

void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    } else
        QueuePush(&obj->q2, x);
}
  • 尾删

作为一个栈，我们需要实现的是先进后出，所以这里是尾删，关于尾删，我们的想法应该是利用队列中带有的尾插操作，将有数据的队列的数据一个个传到空队列中，最后一个传出的数据就是我们要删的数

我们可以理解下图为尾插过5个数的队列
在这里插入图片描述
利用队列的尾插及头删操作，每将队列1的队头尾插给队列2后，头删队列1，知道队列1仅剩一个数据，两个队列的状态就会如下
在这里插入图片描述
此时我们需要做的是利用队列中自带的取队头数据操作，就可以获得栈所需的栈顶元素，

栈顶对应队尾

然后就是需要理解的重点，我们可以发现如果把上图队列1的队头删除后，队列2就是进行尾删的队列1，这样就实现了栈顶删除的操作

如此一来，也呼应了刚刚我们尾插中，找不为空的队列进行尾插的操作

实现

整个队列实现栈的操作中最难理解的就是尾插和尾删的联系与衔接，这两者的关系一旦理清，别的就是信手拈来，这里笔者就不赘述了，跟栈的原始操作大同小异，代码就放在下面了

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
typedef int QDataType;
typedef struct QueueNode {
    struct QueueNode* next;
    QDataType val;
} QNode;

typedef struct Queue {
    QNode* phead;
    QNode* ptail;
    int size;
} Queue;
// 初始化
void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
// 销毁
void QueueDestroy(Queue* pq) {
    assert(pq);

    QNode* cur = pq->phead;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

// 队尾插入
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);

    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc newnode fail");
    }
    newnode->val = x;
    newnode->next = NULL;

    if (pq->ptail == NULL) {
        pq->phead = newnode;
        pq->ptail = newnode;
    } else {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    pq->size++;
}
// 队头删除
void QueuePop(Queue* pq) {
    assert(pq);
    assert(pq->size != 0);

    if (pq->size == 1) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    } else {
        QNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    pq->size--;
}

// 取队头和队尾的数据
QDataType QueueFront(Queue* pq) {
    assert(pq);
    assert(pq->phead);
    return pq->phead->val;
}
QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(pq->ptail);
    return pq->ptail->val;
}

int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;
}
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}



//从这里开始用队列实现栈
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//初始化
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

//尾插
void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    } else
        QueuePush(&obj->q2, x);
}

//尾删
int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* notempty = &obj->q2;
    if (!QueueEmpty(&obj->q1)) {
        empty = &obj->q2;
        notempty = &obj->q1;
    }

    while (QueueSize(notempty) > 1) {
        QueuePush(empty, QueueFront(notempty));
        QueuePop(notempty);
    }
    int top = QueueFront(notempty);
    QueuePop(notempty);

    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);
*/

用栈实现队列

Leetcode-232 用栈实现队列

在这里插入图片描述

思路

同理，先实现栈的结构设计及相关操作

关于用栈实现队列，我们要做的不同方向是，利用两个栈实现，这两个栈不想上面一样，通过判空来使用，而是直接进行分区，一个用来输入，一个用来输出

栈的相关实现，看笔者的另一篇博客也一样，这里也不多说了

【数据结构】栈详解

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);
  • 初始化

同样，我们需要做的也是利用内存分配的方法来实现队列和两个栈的基本结构

初始化两个栈ininin和outoutout，出队直接就往ininin压栈，出队先检查outoutout里面有没有元素，有的话outoutout的栈顶就是队首，否则就先把ininin里面的元素弹出压入到outoutout中。这样就能保证outoutout的栈顶始终都是队首，ininin的栈顶始终都是队尾。


typedef struct {
    ST instack;
    ST outstack;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->instack);
    STInit(&pq->outstack);
    return pq;
}
  • 尾插及头删

在上面我们提到过了，我们需要建立一个输入栈和一个输出栈，所以关于尾插，没什么好多讲的，就往输入队列里一直加新元素就行了

至于头删这就很关键了，我们用图来理解，假设尾插几个数据后队列如下
在这里插入图片描述

因为头删我们需要拿到的数据是A，所以我们利用栈的尾插将每个数据插到输出栈中，即
在这里插入图片描述

此时A在栈顶我们可以提取出来或者删除

如果只是一般逻辑的话，我们大可将这个输出栈的数据倒回输入栈，然后重复原来操作，这其实是可以的，但是这会大大提高原来的时间复杂度，从而降低效能

那么怎么改呢

假设我们不倒回，而是直接往输入栈中加入数据，其实可以发现，输出栈的栈底其实连着的输入栈的栈底，即

在这里插入图片描述
因此，我们不用再倒回输出栈，只需要在需要利用栈顶元素时判断输出栈是否为空，如果为空就将输入栈的数据补充给输出栈就行了

实现

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);

// 初始化和销毁
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	// top指向栈顶数据的下一个位置
	pst->top = 0;

	// top指向栈顶数据
	//pst->top = -1;

	pst->capacity = 0;
}

void STDestroy(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->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc 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;
}

//初始化两个栈ininin和outoutout，出队直接就往ininin压栈，出队先检查outoutout里面有没有元素，有的话outoutout的栈顶就是队首，否则就先把ininin里面的元素弹出压入到outoutout中。这样就能保证outoutout的栈顶始终都是队首，ininin的栈顶始终都是队尾。
typedef struct {
    ST instack;
    ST outstack;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->instack);
    STInit(&pq->outstack);
    return pq;
}

void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->instack, x);
}

void inTOout(MyQueue* obj)
{
    while(!STEmpty(&obj->instack))
    {
        STPush(&obj->outstack, STTop(&obj->instack));
        STPop(&obj->instack);
    }
}
int myQueuePop(MyQueue* obj) {
    if(STEmpty(&obj->outstack))
    {
        inTOout(obj);
    }
    int ret = STTop(&obj->outstack);
    STPop(&obj->outstack);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->outstack))
    {
        inTOout(obj);
    }
    int ret = STTop(&obj->outstack);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->instack) && STEmpty(&obj->outstack);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->instack);
    STDestroy(&obj->outstack);
    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);
*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/621012.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

分布式光伏管理系统的意义与核心技术

分布式光伏管理系统的意义与核心技术

分布式光伏管理系统遵循安全可靠、经济合理原则&#xff0c;满足电力系统自动化总体规划要求&#xff0c;且充分考虑光伏发电的因素&#xff0c;对分布式光伏发电、用电进行集中监控、统一调度、统一运维。为用户提供运维服务&#xff0c;实现能源互联&#xff0c;信息互通&…
阅读更多...
从使用教程、实现原理、差异对比全方面带你玩转业务系统中高频使用的过滤器与拦截器

从使用教程、实现原理、差异对比全方面带你玩转业务系统中高频使用的过滤器与拦截器

1.概述 在Java Web开发中&#xff0c;**过滤器&#xff08;Filter&#xff09;和拦截器&#xff08;Interceptor&#xff09;**是两种常见的组件&#xff0c;用于在请求到达目标资源之前或之后执行一些操作&#xff0c;如日志记录、权限控制、字符编码处理等。虽然它们的作用有…
阅读更多...
【Qt】demo示例--通过定时器实现时间刷新

【Qt】demo示例--通过定时器实现时间刷新

【Qt】demo示例--通过定时器实现时间刷新 1.背景2.代码3.运行 1.背景 Qt Creator版本&#xff1a;4.2.0 &#xff0c;如下图&#xff1a; 即安装qt-opensource-windows-x86-msvc2013_64-5.7.1.exe 后自带得Qt编程IDE&#xff1b; 2.代码 项目结构如下&#xff1a; mydial…
阅读更多...
Navicat Premium数据库新建函数报错问题

Navicat Premium数据库新建函数报错问题

1.问题产生原因&#xff1a; (1)可能是软件 Navicat Premium 的版本不一样 (2)可能是与某些字符集不一样 2.找出解决办法&#xff1a; (1)参考对照系统自带sys数据库表的函数找出的区别&#xff08;后面遇到同样问题可以这样排查&#xff09; (2)不加 DETERMINISTIC 声明&a…
阅读更多...
js图片回显的方法

js图片回显的方法

直接上代码&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title></head><body>// HTML部分<input type"file" id"fileInput"><button onclick"show…
阅读更多...
Nginx内网环境开启https

Nginx内网环境开启https

文章目录 前言一、open-ssl1. 验证2. 安装3.生成ssl证书 一、nginx1. 验证支持模块2. 安装必要模块2.1 重新编译nginx2.2 替换原文件 3. 配置https 总结 前言 nginx开启https前提&#xff1a; 服务器支持open-sslnginx 包含--with-http_ssl_module --with-stream --with-stre…
阅读更多...
融知财经：期货和现货的区别是什么？哪个风险大？

融知财经：期货和现货的区别是什么？哪个风险大？

期货和现货在交易对象等方面存在明显的区别。期货交易是一种衍生金融工具&#xff0c;主要用于价格发现、风险管理和投机&#xff0c;而现货交易则是商品和服务的实际买卖。在选择进行期货交易还是现货交易时&#xff0c;投资者需要根据自己的需求和市场情况来决定。 期货和现货…
阅读更多...
In Context Learning（ICL）个人记录

In Context Learning（ICL）个人记录

In Context Learning&#xff08;ICL&#xff09;简介 In Context Learning&#xff08;ICL&#xff09;的关键思想是从类比中学习。上图给出了一个描述语言模型如何使用 ICL 进行决策的例子。首先&#xff0c;ICL 需要一些示例来形成一个演示上下文。这些示例通常是用自然语言…
阅读更多...
C++牛客周赛题目分享（2）小红叕战小紫，小红的数组移动，小红的素数合并，小红的子序列求和

C++牛客周赛题目分享（2）小红叕战小紫，小红的数组移动，小红的素数合并，小红的子序列求和

目录 ​编辑 1.前言 2.四道题目 1.小红叕战小紫 1.题目描述 2.输入描述 3.输出描述 4.示例 5.题解与思路 2.小红的数组移动 1.题目描述 2.输入描述 3.输出描述 4.示例 5.题解与思路 3.小红的素数合并 1.题目描述 2.输入描述 3.输出描述 4.示例 5.题解与思…
阅读更多...
华东政法大学公布2024《负面清单期刊目录》，附目录

华东政法大学公布2024《负面清单期刊目录》，附目录

近日&#xff0c;华东政法大学公布2024《负面清单期刊目录》&#xff0c;包括《齐齐哈尔大学学报(哲学社会科学版)》《景德镇学院学报(社科)》《九江学院学报(社科)》《北京印刷学院学报》《江西电力职业技术学院学报》《中国多媒体与网络教学学报》《吉林省教育学院学报》《开…
阅读更多...
pyqt动画效果放大与缩小

pyqt动画效果放大与缩小

pyqt动画效果放大与缩小 QPropertyAnimation介绍放大与缩小效果代码 QPropertyAnimation介绍 QPropertyAnimation 是 PyQt中的一个类&#xff0c;它用于对 Qt 对象的属性进行动画处理。通过使用 QPropertyAnimation&#xff0c;你可以平滑地改变一个对象的属性值&#xff0c;例…
阅读更多...
【新手入门】Github与Git使用教程

【新手入门】Github与Git使用教程

Github与Git 一、Github基础教程 1.1 基本操作 点击代码文件可以直接查看文件的内容&#xff0c;支持在线修改文件&#xff0c;只需要点击(文件内容)右上角的编辑按钮即可进行编辑。 README.md一般介绍项目的功能&#xff0c;用法&#xff0c;注意事项&#xff1b;有时还有…
阅读更多...
二、安装、使用Grafana

二、安装、使用Grafana

目录 一、安装Grafana 二、使用grafana 一、安装Grafana 官网&#xff1a;https://grafana.com/ 账号&#xff1a;admin 密码&#xff1a;xxxxxx [rootrabbitmq_2 prometheus]# [rootrabbitmq_2 prometheus]# wget https://dl.grafana.com/enterprise/release/grafana-enter…
阅读更多...
kubernetes集群开启ipvs模式

kubernetes集群开启ipvs模式

1&#xff09; 需要在所有节点机器安装ipvsadm&#xff1a; apt install ipvsadm 2) 加载ipvs模块 modprobe ip_vs modprobe ip_rr modprobe ip_wrr modprobe ip_sh修改k8s集群内的kube-proxy cm kubectl edit cm kube-proxy -n kube-system修改模式为ipvs&#xff1a; 如图 …
阅读更多...
重大升级 | OpenSCA SaaS全面接入供应链安全情报！

重大升级 | OpenSCA SaaS全面接入供应链安全情报！

结合社区用户反馈及研发小伙伴的积极探索&#xff0c; OpenSCA 项目组再次发力&#xff0c;SaaS版本重大升级啦&#xff01; 用户的需求是OpenSCA前进的动力&#xff0c;欢迎更多感兴趣的朋友们积极试用和反馈~ 更 新 内 容 1.全面接入云脉XSBOM供应链安全情报 2.强大的资产…
阅读更多...
太速科技-基于VU3P的双路100G光纤加速计算卡

太速科技-基于VU3P的双路100G光纤加速计算卡

基于VU3P的双路100G光纤加速计算卡 一、板卡概述 基于Xilinx UltraScale16 nm VU3P芯片方案基础上研发的一款双口100 G FPGA光纤以太网PCI-Express v3.0 x16智能加速计算卡&#xff0c;该智能卡拥有高吞吐量、低延时的网络处理能力以及辅助CPU进行网络功能卸载的能力…
阅读更多...
【董晓算法】竞赛常用知识之字符串2

【董晓算法】竞赛常用知识之字符串2

前言&#xff1a; 本系列是学习了董晓老师所讲的知识点做的笔记 董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com) 动态规划系列&#xff08;还没学完&#xff09; 【董晓算法】动态规划之线性DP问题-CSDN博客 【董晓算法】动态规划之背包DP问题&#xff…
阅读更多...
通往糊涂之路 The road to serfdom

通往糊涂之路 The road to serfdom

最近被推送了一本书&#xff0c;哈耶克的............ 试一试&#xff0c;看看能不能看懂&#xff0c;也许是通往糊涂之路。
阅读更多...
AI游戏外挂为何违法？

AI游戏外挂为何违法？

尊敬的读者们&#xff0c;大家好&#xff01;今天我想和大家探讨一个备受争议的话题——AI游戏外挂的合法性。近年来&#xff0c;随着人工智能技术的飞速发展&#xff0c;AI外挂逐渐成为游戏领域的一大毒瘤。那么&#xff0c;为什么AI游戏外挂会被视为违法行为呢&#xff1f;本…
阅读更多...
vue3延迟加载(异步组件​)defineAsyncComponent

vue3延迟加载(异步组件​)defineAsyncComponent

最简单用法 Index.vue: <script setup> import { onMounted, defineAsyncComponent } from vue import ./index.cssconst Child defineAsyncComponent(() > import(./Child.vue))onMounted(() > {}) </script><template><div class"m-home-w…
阅读更多...
最新文章

Copyright @ 2022~2023