数据结构之栈和队列

🕗 发布于 2024-10-04 09:08 数据结构

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.栈与递归

先介绍递归的定义：

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

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

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

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

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

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

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

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);
}

原文地址：https://blog.csdn.net/2303_80883523/article/details/142645463

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：TS （object，tuple）总结
下一篇：什么是 Web 应用中的 Facet 控件

ubuntu * 表达的应用
在使用 ln -s 软连接、cp -r， rm -r等操作指令时，一般都是对整个文件夹操作，但是有些时候只想复制文件夹中的文件，而不是整个文件夹，就需要*表达来进行筛选了。例如，将/home/no1/
阅读更多2024-10-05
mysql学习教程，从入门到精通，SQL 创建视图(CREATE VIEW 语句)（34）
在 SQL 中，`CREATE VIEW` 语句用于创建一个视图（View），视图是一种虚拟表，它基于 SQL 查询的结果集。视图并不存储实际数据，而是存储定义视图的查询。当您查询视图时，数据库会动态
阅读更多2024-10-05
KNN算法
机器学习是区别于明确编程,它通过算法训练数据学习内容,最终得到可靠的模型.今天先介绍其中一种模型训练算法KNN.
阅读更多2024-10-05
C++教程一口气讲完！（万字讲解）(￣y▽￣)╭ Ohohoho... 下
使用#define预处理器。使用const关键字。C++ 中的函数定义的一般形式如下：在 C++ 中，函数由一个函数头和一个函数主体组成。一个函数可以返回一个值。是函数返回的值的数据类型。有些函数执行
阅读更多2024-10-05
PowerShell脚本在自动化Windows开发工作流程中的应用
PowerShell是微软开发的一款基于任务的自动化和配置管理框架，它运行在.NETFramework之上，提供了丰富的命令行界面和脚本编写能力。与传统的CMD或Bash相比，PowerShell支持
阅读更多2024-10-05
C初阶（八）选择结构（分支结构）--if、else、switch
👉在本博文中，将有对 if 、else、switch使用场景的举例，还有关键字 case 、break的使用。
阅读更多2024-10-05
基于ScriptableObject设计游戏数据表
本文将针对运行时的只读数据表的应用进行探索，并且结合自定义的本地持久化存储方式使得基于ScriptableObject开发的数据表能够在运行时进行读写。
阅读更多2024-10-05
CentOS 替换 yum源经验分享
CentOS 替换 yum源经验分享
阅读更多2024-10-05
Stable Diffusion绘画 | 插件-Deforum：动态视频生成（中篇）
本篇文章重点讲解参数最多的关键帧模块。
阅读更多2024-10-05
函数的概念
函数是一组语句的集合，这些语句在某个条件下被执行。定义函数时，可以指定输入参数，并可以返回结果。
阅读更多2024-10-05

数据结构之栈和队列

目录

1、栈的简介

2、栈的术语

3、栈的基本操作

1.顺序栈的实现

2.链栈的实现

4、栈的应用

1.栈与递归

2.括号匹配问题

3.表达式计算

5、队列

1.顺序队列

2.链式队列

相关文章