当前位置： 首页 > article >正文

数据结构之栈和队列

article 2024/10/4 11:19:54

目录

  • 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.kler.cn/news/331639.html

相关文章：

  • 深度优先搜索（DFS）解题思路解析：如何通过图论计算除法求值
  • 使用 Python 实现图形学的 GPU 编程
  • 【AI知识点】维度灾难（curse of dimensionality）
  • 【Docker】 进入容器的几种方式
  • 【源码+文档+调试讲解】基于微信小程序的医院医疗设备管理系统springboot
  • 【算法】---快速排序
  • gdb 调试 linux 应用程序的技巧介绍
  • jmeter学习（2）变量
  • Linux驱动开发(速记版)--设备树插件
  • spring boot jar 分离自动部署脚本
  • PasteForm最佳CRUD实践，实际案例PasteTemplate详解之3000问(三)
  • AI换脸技术新纪元：直播与视频创作的新利器
  • 在Git中操作失误，如何撤回
  • 微信小程序实战教程：轻松实现列表批量选择功能
  • 已解决：ImportError: cannot import name ‘get_column_letter‘
  • 51单片机应用开发（进阶）---数码管显示按键“加”“减”计数
  • PIKACHU | PIKACHU 靶场 XSS 后台配置
  • Web 网站服务（二）：深入探索 Apache 的高级功能
  • 加油站智能视频监控预警系统(AI识别烟火打电话抽烟) Python 和 OpenCV 库
  • java版基于Spring Boot + Mybatis在线招投标|评标|竞标|单一采购|询价|邀标|在线开标|招标公告发布|评审专家|招投标采购系统源码