915栈和队列部分参考代码，完整见PPT

2023-10-29 14:10
文章标签 代码 队列 部分 参考 ppt 完整 915

本文主要是介绍915栈和队列部分参考代码，完整见PPT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

栈

顺序栈的定义

int stk[N], top = -1;

具体操作见PPT。

链栈

1. 节点定义

链栈的节点通常定义如下:

struct Node 
{int val;Node *next; Node(int x) : val(x), next(NULL) {}
};

其中:

  • val 字段保存节点存储的数据
  • next 字段指向下一个节点,实现链式存储结构

链栈的基本操作需要使用链表的基本操作,如:

  • 初始化一个链栈常用头结点法,建立一个头结点,它的next指针初始化为NULL
  • 插入节点时,新建一个节点,将它的next指向原来栈顶节点,然后将栈顶指针指向新节点
  • 删除节点时,将栈顶指针指向原栈顶的next节点,释放原栈顶节点空间
  • 访问栈顶元素直接通过栈顶指针访问其val字段
  • 判断是否为空使用栈顶指针是否为NULL等

总之,通过next指针链接节点,实现链式存储,同时使用栈顶指针指向实际栈顶节点,就可以实现链栈的基本操作。

2. 初始化

链栈的初始化主要有两种方式:

  1. 初始化一个头结点
Node *init()    
{Node *dummy = new Node(-1);return dummy;
}

此时头结点仅代表栈的头,不存储实际数据,next指针初始化为NULL表示栈为空。

  1. 不使用头结点
Node *init() 
{return NULL;
}

此时为空栈直接返回NULL。

使用头结点的优点是:

  • 代码实现更简单,操作时直接使用 head指针代表栈 Head
  • 判断栈空时用head->next判断,避免每次都对NULL指针进行判断

不使用头结点可以减少一个额外的结点开销。

一般来说,使用头结点法是较为常见的链栈初始化实现方式。它简化了空栈的判断及后续的插入、删除等操作。

所以使用头结点法初始化一个链栈一般是最佳实践。

接下来的写法都是基于带头节点的链表来实现。

3. 判栈空
bool empty(Node *dummy)
{return dummy->next == NULL;
}
4. 进栈
void push(Node *dummy, int x)
{Node *node = new Node(x);node->next = dummy->next;dummy->next = node;
}
5. 出栈
// 为了使代码简洁突出原理，以下所有操作默认都是合法的
void pop(Node *dummy)
{dummy->next = dummy->next->next;
}
6. 读栈顶元素
int top(Node *dummy)
{return dummy->next->val;
}
完整代码
#include <iostream>using namespace std;struct Node
{int val;Node *next;Node(int x) : val(x), next(NULL) {}
};// 链栈初始化
Node *init()    
{Node *dummy = new Node(-1);return dummy;
}bool empty(Node *dummy)
{return dummy->next == NULL;
}void push(Node *dummy, int x)
{Node *node = new Node(x);node->next = dummy->next;dummy->next = node;
}// 为了使代码简洁突出原理，以下所有操作默认都是合法的
void pop(Node *dummy)
{dummy->next = dummy->next->next;
}int top(Node *dummy)
{return dummy->next->val;
}// 出栈链表剩余元素并输出
void print(Node *dummy)
{while (!empty(dummy)){cout << top(dummy) << ' ';pop(dummy);}cout << endl;
}int main()  
{// 测试链栈各操作Node *dummy = init();push(dummy, 1);push(dummy, 2);push(dummy, 3);push(dummy, 4);printf("栈顶元素：%d\n", top(dummy));pop(dummy);printf("栈顶元素：%d\n", top(dummy));printf("栈是否为空：%d\n", empty(dummy));print(dummy);return 0;
}

栈顶元素：4
栈顶元素：3
栈是否为空：0
3 2 1

在这里插入图片描述

在这里插入图片描述

class MyQueue {
private:stack<int> in, out;void in2out() {while (!in.empty()) {out.push(in.top());in.pop();}}
public:MyQueue() {}void push(int x) {in.push(x);}int pop() {if (out.empty()) {in2out();}int res = out.top();out.pop();return res;}int peek() {if (out.empty()) {in2out();}return out.top();}bool empty() {return out.empty() && in.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

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

class MyStack {
private:queue<int> q1, q2;public:MyStack() {}void push(int x) {q2.push(x);while (!q1.empty()) {q2.push(q1.front());q1.pop();}swap(q1, q2);}int pop() {int res = q1.front();q1.pop();return res;}int top() {return q1.front();}bool empty() {return q1.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

在这里插入图片描述

class MyStack {
private:queue<int> q;public:MyStack() {}void push(int x) {int n = q.size();q.push(x);while (n --) {q.push(q.front());q.pop();}}int pop() {int res = q.front();q.pop();return res;}int top() {return q.front();}bool empty() {return q.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

括号匹配

这个代码利用STL的stack来实现:

  • 遍历字符串,遇到开括号入栈
  • 遇到闭括号出栈与之比对
  • 最后判断栈是否为空,为空则括号匹配

通过给出具体代码,可以更清晰体现栈在括号匹配中的应用。

#include <iostream>
#include <stack>using namespace std;bool bracketMatch(string str)
{stack<char> s;for (char c: str){if (c == '(' || c == '[' || c == '{') s.push(c);else{if (s.empty()) return false;char top = s.top();s.pop();if ((c==')' && top!='(') ||(c==']' && top!='[') ||(c=='}' && top!='{')) return false;}}return s.empty();
}int main()
{string s1 = "((()))";string s2 = "([{{}])";if(bracketMatch(s1))cout << "s1 matched" << endl;elsecout << "s1 not matched" << endl;if(bracketMatch(s2))cout << "s2 matched" << endl;elsecout << "s2 not matched" << endl;return 0;
}

AcWing.3302中缀表达式求值：

2种解法：

  1. 直接求解

  2. 将中缀表达式转换为后缀表达式后进行解决

完整代码链接：https://www.acwing.com/activity/content/code/content/1466076/

冲击高分的同学需要掌握具体代码的实现

冲击平均分的同学只需理解算法

这里给出第二种解法的参考代码：

在这里插入图片描述

#include <iostream>
#include <stack>
#include <string>using namespace std;// 操作符优先级
int priority(char op) {if(op == '+' || op == '-')return 1;else if(op == '*' || op == '/') return 2;else return 0;
}string infixToPostfix(string infix) {stack<char> st;string postfix;for(char c: infix) {if(c == ' ') continue; //跳过空格if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) { // c是字母// if(isdigit(c)) {  // c是具体的数字postfix += c; //操作数直接加入后缀表达式}else if(c == '(') {st.push(c); //左括号入栈}else if(c == ')') {while(!st.empty() && st.top() != '(') {postfix += st.top();st.pop();}if(!st.empty() && st.top() != '(') {return "Invalid Expression"; }st.pop(); //弹出左括号}else { //运算符while(!st.empty() && priority(c) <= priority(st.top())) {postfix += st.top();st.pop();  }st.push(c);}}while(!st.empty()) {if(st.top() == '(') return "Invalid Expression";postfix += st.top();st.pop();}return postfix;
}int main() {string infix;cin >> infix;string postfix = infixToPostfix(infix);cout << postfix << endl;return 0;
}

输入：

(a+b)*(c+d)

输出：

ab+cd+*

这篇关于915栈和队列部分参考代码，完整见PPT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/301178。

相关文章

Python使用Tenacity一行代码实现自动重试详解

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门：一行代码实现优雅重试精细控制：让重试按我
阅读更多...
Python极速搭建局域网文件共享服务器完整指南

Python极速搭建局域网文件共享服务器完整指南

《Python极速搭建局域网文件共享服务器完整指南》在办公室或家庭局域网中快速共享文件时,许多人会选择第三方工具或云存储服务,但这些方案往往存在隐私泄露风险或需要复杂配置,下面我们就来看看如何使用Py... 目录一、android基础版：HTTP文件共享的魔法命令1. 一行代码启动HTTP服务器2. 关键参
阅读更多...
OpenCV在Java中的完整集成指南分享

OpenCV在Java中的完整集成指南分享

《OpenCV在Java中的完整集成指南分享》本文详解了在Java中集成OpenCV的方法,涵盖jar包导入、dll配置、JNI路径设置及跨平台兼容性处理,提供了图像处理、特征检测、实时视频分析等应用... 目录1. OpenCV简介与应用领域1.1 OpenCV的诞生与发展1.2 OpenCV的应用领域2
阅读更多...
使用Go实现文件复制的完整流程

使用Go实现文件复制的完整流程

《使用Go实现文件复制的完整流程》本案例将实现一个实用的文件操作工具：将一个文件的内容完整复制到另一个文件中,这是文件处理中的常见任务,比如配置文件备份、日志迁移、用户上传文件转存等,文中通过代码示例... 目录案例说明涉及China编程知识点示例代码代码解析示例运行练习扩展小结案例说明我们将通过标准库 os
阅读更多...
Python实现MQTT通信的示例代码

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器（Broker）‌‌3. pytho
阅读更多...
Java堆转储文件之1.6G大文件处理完整指南

Java堆转储文件之1.6G大文件处理完整指南

《Java堆转储文件之1.6G大文件处理完整指南》堆转储文件是优化、分析内存消耗的重要工具,：本文主要介绍Java堆转储文件之1.6G大文件处理的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言文件为什么这么大？如何处理这个文件？分析文件内容（推荐）删除文件（如果不需要）查看错误来源如何避
阅读更多...
MySQL进行数据库审计的详细步骤和示例代码

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java
阅读更多...
创建Java keystore文件的完整指南及详细步骤

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键（私钥）的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与
阅读更多...
Linux中压缩、网络传输与系统监控工具的使用完整指南

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压：数据存储与传输的优化核心1. zip/unzip：通用压缩格式的便捷操作2.
阅读更多...
Spring Security中用户名和密码的验证完整流程

Spring Security中用户名和密码的验证完整流程

《SpringSecurity中用户名和密码的验证完整流程》本文给大家介绍SpringSecurity中用户名和密码的验证完整流程,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定... 首先创建了一个UsernamePasswordAuthenticationTChina编程oken对象，这是S
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2