数据结构之栈和队列

server/2024/10/9 17:27:36/

目录

  • 1、栈的简介
  • 2、栈的术语
  • 3、栈的基本操作
    • 1.顺序栈的实现
    • 2.链栈的实现
  • 4、栈的应用
    • 1.栈与递归
    • 2.括号匹配问题
    • 3.表达式计算
  • 5、队列
    • 1.顺序队列
    • 2.链式队列

1、栈的简介

栈其实是一种特殊的线性表，就是只允许在一端进行插入或删除的操作；这就导致它有一个后进先出的运算特性，例如叠盘子，制作和吃烤串
在这里插入图片描述

2、栈的术语

在这里插入图片描述

3、栈的基本操作

1.顺序栈的实现

在这里插入图片描述

#include<iostream>
#define maxsize 10
using namespace std;
//定义一个顺序栈
typedef struct
{//静态分配内存int data[maxsize];int top;//栈顶指针（逻辑指针）:指向元素下标的位置
}sqStock;//初始化顺序栈
void init_stack(sqStock& s)
{s.top = -1;//栈顶指针指向-1代表没有元素
}//判断栈空
bool isEmpty(sqStock& s)
{if (s.top == -1)return true;else return false;
}//进栈(压栈)操作
void push(sqStock& s)
{if (s.top == maxsize - 1) {cout << "进栈出错：栈满" << endl; return;}int x;cin >> x;//下两句等价于s.data[++s.top] = x;s.top += 1;s.data[s.top] = x;
}//出栈(删除)操作
void pop(sqStock& s)
{if (isEmpty) { cout << "出栈错误：栈空" << endl; return; }s.top--;//逻辑删除，数据保留
}//读取栈顶元素
int get(sqStock& s)
{if (isEmpty) { cout << "读取错误：栈空" << endl; return -1; }return s.data[s.top];
}int main()
{sqStock s;init_stack(s);push(s);cout <<get(s)<<endl;
}

2.链栈的实现

和链表其实类似，只不过我们的操作被限制了那么下面我们就对链栈进行实现
在这里插入图片描述
在我们之前学习链表的时候都创建了一个头节点，这样在进行一些基本操作的时候会更加方便，但是当我们创建链栈的时候就不需要带头节点了，因为我们一般都是直接在栈顶进行操作，带头结点反而需要额外处理头节点，所以我们进行学习时就不带头节点了

#include<iostream>
using namespace std;//定义一个链栈
typedef struct stack
{int data;stack* next;
}*lstack,lnode;//初始化
void init_lstack(lstack& l)
{l = NULL;//构建一个空栈
}//判断栈空
bool isEmpty(lstack& l)
{if (l) return false;else return true;
}//入栈(无头节点)
void push(lstack& l)
{int x;while (cin >> x && x != 0) {l = new lnode{ x,l };if (!l)cout << "入栈错误：内存不足" << endl;}
}//出栈(无头节点)
void pop(lstack& l)
{if (isEmpty(l)) { cout << "出栈错误：栈空" << endl; exit(1); }lnode* r = l;l = l->next;delete r;
}//读取栈顶元素
int get(lstack& l)
{if (isEmpty(l)) cout << "出栈错误：栈空" << endl;return l->data;
}//打印链栈
void print(lstack& l)
{if (isEmpty(l)) { cout << "出栈错误：栈空" << endl; return; }lnode* r=l;while (r){cout << r->data<<"\t";r = r->next;}cout << endl;
}int main()
{lstack l;init_lstack(l);push(l);print(l);pop(l);
}

4、栈的应用

1.栈与递归

先介绍递归的定义：

  • 若一个对象部分地包含了自己，或者用自己给自己定义则称这个对象是递归的
  • 若一个过程直接或间接地调用自己则称这个过程是递归的

递归需要满足的三个条件：

  1. 将原问题转化成一个新问题且解法相似
  2. 通过转化使问题简化，层层递进
  3. 有一个明确的递归出口（限制条件）

在函数调用的过程中，系统通常会做以下工作：

在这里插入图片描述
当我们用递归函数时就会有一个函数调用栈，用于存储以下内容：

  • 调用返回地址：每次函数被调用时，都需要在调用完成后返回到调用点继续执行。调用返回地址是函数调用结束后，程序应该继续执行的指令地址。在递归函数中，每次递归调用都会在栈上保存一个返回地址，以便在递归调用完成后能够返回到上一层递归调用的位置。
  • 实参：是调用函数时传递给函数的值。在递归函数中，每次函数调用都可能需要不同的参数。这些参数值会在函数调用时被压入栈中，以便在函数执行时能够访问这些值。
  • 局部变量：是在函数内部定义的变量，它们仅在函数执行期间存在。每次函数调用都会创建自己的局部变量副本，这些局部变量也会被存储在函数调用栈上。在递归函数中，每次递归调用都有自己的局部变量集，它们之间是相互独立的。

函数调用栈符合先进后出的特性
在这里插入图片描述在这里插入图片描述递归调用时，函数调用栈又称递归工作栈，每进入一层递归就将递归调用所需信息压入栈顶，每退出一层递归就从栈顶弹出相应信息；缺点就是太多递归有可能会导致栈溢出；所以在有需要的时候可以用类似的循环算法代替递归

2.括号匹配问题

#include<iostream>
#include<string>
using namespace std;//定义一个链栈
typedef struct stack
{char data;stack* next;
}*lstack,lnode;//判断栈空
bool isEmpty(lstack& l)
{if (l) return false;else return true;
}//入栈(无头节点)
void push(lstack& l,char a)
{l = new lnode{ a,l };if (!l)cout << "入栈错误：内存不足" << endl;
}//出栈(无头节点)
void pop(lstack& l)
{if (isEmpty(l)) { cout << "出栈错误：栈空" << endl; exit(1); }lnode* r = l;l = l->next;delete r;
}//读取栈顶元素
char get(lstack& l)
{if (isEmpty(l)) cout << "出栈错误：栈空" << endl;return l->data;
}//检查是否匹配
bool check(string&str)
{lstack l=NULL;for (char a : str){if (a == '(' || a == '[' || a == '{')push(l,a);switch (a){case ')':if (get(l) == '(')pop(l); else return false; break;case ']':if (get(l) == '[')pop(l); else return false; break;case '}':if (get(l) == '{')pop(l); else return false; break;}}if (isEmpty(l))return true;else return false;
}int main()
{string s = "{(1+1)*[(3+4)-(7*7)]}";if (check(s))cout << "匹配成功" << endl;else cout << "匹配失败" << endl;
}

3.表达式计算

在这里插入图片描述
利用后缀表达式可以做到让计算机运算地更快，因为计算机不用判断括号的优先级，其原理就是距离操作符最近的两个元素会被操作，而对于操作数的存储来说就有后进先出的特点，这就符合栈的运算特征，我们就可以利用栈来存储操作数，当我们扫描到操作符就弹出两个元素进行运算，下面是代码演示：

#include<iostream>
#include<string>
#include<sstream>
using namespace std;// 定义一个链栈
typedef struct stack {double data;stack* next;
} *lstack, lnode;// 判断栈空
bool isEmpty(lstack l) {return l == NULL;
}// 入栈(无头节点)
void push(lstack& l, double a) {lstack newNode = new lnode{a, l};if (!newNode) cout << "入栈错误：内存不足" << endl;l = newNode;
}// 出栈(无头节点)
double pop(lstack& l) {if (isEmpty(l)) { cout << "出栈错误：栈空" << endl; exit(1); }double a = l->data;lstack r = l;l = l->next;delete r;return a;
}// 计算函数，处理运算符
double calculate(double a1, double a2, char op) {switch (op) {case '+': return a1 + a2;case '-': return a1 - a2;case '*': return a1 * a2;case '/': return a2 != 0 ? a1 / a2 : throw "除数不能为0";default: throw "未知运算符";}
}// 对后缀表达式进行计算
double calculate_tail(string s) {lstack l = NULL;istringstream str(s);string token;while (str >> token) {if (token.size() == 1 && string("+-*/").find(token[0]) != string::npos) {// 操作符，出栈两个元素计算double a2 = pop(l);double a1 = pop(l);push(l, calculate(a1, a2, token[0]));} else {// 数字，转换为double后入栈push(l, stod(token));}}return pop(l);
}int main() {string s = "15 7 1 1 + - / 3 * 2 1 1 + + -";cout << calculate_tail(s) << endl;return 0;
}

在这里插入图片描述

5、队列

队列一听就比较好理解，跟排队一样，先进先出，后进后出，其中的重要术语有：队头、队尾、空队列、入队、出队
在这里插入图片描述

1.顺序队列

在这里插入图片描述
在创建顺序队列时，我们容易发现尾指针始终比实际尾部元素大1，但是头指针就没有这种情况，另外当我们出队之后后面的元素不会自动补齐，这就会导致空间浪费，所以我们需要想办法将尾部和头部连起来，这样就形成了一个逻辑循环，那么就需要综合取模运算和尾指针指向尾节点后一个位置的特点实现这种循环操作；但是为了区别判满和判空，判满不能是rear=head，那就只有牺牲一个节点空间使rear+1==head；那就结合前述特点实现循环判满：(rear+1)%maxsize==head，注意：由于我们只想rear和head在0~(maxsize-1)之间出现，所以取模才会选取maxsize

#include<iostream>
#define maxsize 10
using namespace std;typedef struct
{int data[maxsize];int head, rear;
}sqQueue;//初始化队列
void init_sq(sqQueue& s)
{s.head = s.rear = 0;
}//获取长度
int length(sqQueue& s)
{return (s.rear - s.head + maxsize) % maxsize;//防止head在rear上面
}//判断是否为空
bool isEmpty(const sqQueue & l)
{if (l.head == l.rear)return true;else return false;
}
//判断是否为满
bool isFull(const sqQueue&s)
{if (s.rear + 1 % maxsize == s.head)return true;return false;
}//入队
void insert(sqQueue& s)
{if (isFull(s)) { cout << "入队错误：队列已满" << endl; return; }int x;while (cin >> x && x != 0){s.data[s.rear ] = x;s.rear =(s.rear+1)% maxsize;}
}//出队
void del(sqQueue&s)
{if (isEmpty(s)) { cout << "出队错误：队列为空" << endl; return; }s.data[s.head] = 0;s.head++;
}//获取队头元素
int get(sqQueue& s)
{if (isEmpty(s)) { cout << "获取队头元素错误：队列为空" << endl; return 0; }return s.data[s.head];
}//清空队列
void clear(sqQueue& s)
{s.head = s.rear = 0;
}//打印队列
void print(sqQueue& s)
{int a = s.head;while (a != s.rear){cout << s.data[a] << "\t";a++;a %= maxsize;}
}int main()
{sqQueue s;init_sq(s);insert(s);print(s);
}

其实除了留一个空间来区别判满和判空，还可以借助变量来判断，第一种思路是建立一个长度变量，当长度等于maxsize时就判满，等于0时就判空；第二种是建立一个日志变量记录出队成功或者入队成功，这个变量在入队成功时=1，出队成功时=0，最后看最后一次操作成功是入队还是出队，结合rear==head就知道是队空还是队满了

2.链式队列

既然是链式队列，所以一定有后继指针，队列还有头指针和尾指针，如果把这三者定义在一起肯定不合适，因为不可能每个节点都有头指针和尾指针，所以分成两个结构体进行定义，队列才有头指针和尾指针，节点才有后继指针，而我们一定要将next连接起来才能形成链表，至于不直接使用head指针，是因为使用 front 和 rear 指针可以清楚地标识队列的头部和尾部。front 指向队列的第一个元素（在带头结点的实现中，front 指向头结点，头结点的 next 指向第一个元素），而 rear 指向队列的最后一个元素。这有助于简化入队和出队操作，因为你可以直接操作这两个指针而不必遍历链表。以下是代码实现：

#include<iostream>
#define maxsize 10
using namespace std;typedef struct node
{int data;node* next;
}node;typedef struct
{node* head;node* rear;
}lQueue;//初始化队列
void init_lq(lQueue& s)
{s.head = s.rear = new node;if (!s.head) { cout << "初始化队列错误：内存不足" << endl; exit(1); }s.head->next = NULL;
}//判断是否为空
bool isEmpty(const lQueue & s)
{return s.head == s.rear;
}//入队
void insert(lQueue& s)
{int x;while (cin >> x && x != 0){node* p = new node{ x,NULL };if (!p) { cout << "入队错误：内存不足" << endl; exit(1); }s.rear->next = p;s.rear = p;}
}//出队
void del(lQueue&s)
{if (isEmpty(s)) { cout << "出队错误：队列为空" << endl; return; }node* r = s.head->next;//哨兵指向队头元素s.head->next = r->next;//头节点指针域指向下一个元素if (s.rear == r)s.rear = s.head;//队列只剩一个队尾元素delete r;
}//获取队头元素
int get(lQueue& s)
{if (isEmpty(s)) { cout << "获取队头元素错误：队列为空" << endl; return 0; }return s.head->next->data;
}//销毁队列
void destroy(lQueue & s)
{if (isEmpty(s)) { cout << "销毁失败：队列已空" << endl; return; }while (s.head->next)del(s);delete s.head;s.head = s.rear = NULL;
}//打印队列
void print(lQueue& s)
{if (isEmpty(s)) { cout << "打印失败：队列为空" << endl; return; }node* r=s.head->next;while (r){cout << r->data<< "\t";r = r->next;}cout << endl;
}int main()
{lQueue s;init_lq(s);insert(s);print(s);destroy(s);print(s);
}

http://www.ppmy.cn/server/128751.html

相关文章

基于STM32的智能水族箱控制系统设计

基于STM32的智能水族箱控制系统设计

引言 本项目基于STM32微控制器设计一个智能水族箱控制系统。该系统能够通过传感器监测水温、照明和水位&#xff0c;并自动控制加热器、LED灯和水泵&#xff0c;确保水族箱内的环境适宜鱼类生长。该项目展示了STM32在环境监测、设备控制和智能反馈系统中的应用。 环境准备 1…
阅读更多...
Activity

Activity

文章目录 1.启停活动页面1.Activity启动和结束2.Activity生命周期3. Activity启动模式 2.在活动之间传递信息1.显示Intent和隐式Intent显示Intent隐式Intent 2.向下一个Activity发送数据3.向上一个Activity返回数据 3.为活动补充附加信息1.利用资源文件配置字符串2.利用元数据传…
阅读更多...
JSON详解

JSON详解

目录 一. JSON简述 二. XML和JSON的区别 三. JSON的语法格式 3.1 JSON语法格式 3.2 单个JSON对象 3.3 数组存储JSON数据 四. JSON数据与Java的相互转化 4.1 hutool工具包 4.2 fastjson 工具包 一. JSON简述 JSON (JavaScript Object Notation,JS对象简谱)是一种轻量级…
阅读更多...
k8s的pod的管理和优化

k8s的pod的管理和优化

资源管理介绍 在kubernetes中&#xff0c;所有的内容都抽象为资源&#xff0c;用户需要通过操作资源来管理kubernetes。 kubernetes的本质上就是一个集群系统&#xff0c;用户可以在集群中部署各种服务 所谓的部署服务&#xff0c;其实就是在kubernetes集群中运行一个个的容器…
阅读更多...
python爬虫案例——处理验证码登录网站（12）

python爬虫案例——处理验证码登录网站（12）

文章目录 前言1、任务目标2、网页分析3、代码编写4、第三方验证码识别平台（超级鹰）前言 我们在爬取某些网站数据时，可能会遇到必须登陆才能获取网页内容的情况，而大部分网站登录都需要输入验证码才能登录成功，所以接下来我将会通过实际案例来讲解如何实现验证码登录网站 1…
阅读更多...
如何使用selenium结合最新版chrome爬虫

如何使用selenium结合最新版chrome爬虫

如何使用selenium结合最新版chrome爬虫 1、下载chrome及其插件chromedriver-win64 点我下载 [百度网盘] 通过百度网盘分享的文件：chrome爬虫插件 链接：https://pan.baidu.com/s/1kqkblX_ordZsQNYR234bMg 提取码：8888 下载后，解压安装。 2、配置电脑系统环境 我的电脑-…
阅读更多...
关于jmeter性能测试和java应用性能优化总结

关于jmeter性能测试和java应用性能优化总结

在实际进行压力测试过程中，遇到了各种问题，经过不断的查找资料和尝试各种方法，最终将问题得以解决，将过程中的问题和解决的方法做一个总结，在后续遇到类似问题时，能够有一个参考和借鉴。总体上包括两类：一类是关于jmeter压力测试工具使用相关的，另一类是服务程序性能优…
阅读更多...
【分布式微服务云原生】OpenFeign：微服务通信的瑞士军刀

【分布式微服务云原生】OpenFeign：微服务通信的瑞士军刀

OpenFeign&#xff1a;微服务通信的瑞士军刀 摘要 在微服务架构中&#xff0c;服务间的通信是构建分布式系统的关键。OpenFeign&#xff0c;作为Spring Cloud生态系统中的一员&#xff0c;提供了一种声明式、简洁的方法来处理HTTP客户端的开发。本文将介绍OpenFeign的核心功能…
阅读更多...
最新文章

Copyright @ 2022~2023