操作系统 —— 信号

article/2025/8/16 3:02:57

文章目录

      • 1. 信号的感性理解
      • 2. 发送信号的方式
        • 2.1 键盘发送信号
        • 2.2 进程异常产生信号
        • 2.3 调用系统函数发送信号
        • 2.4 触发软件条件,发送信号
      • 3. 信号的控制
        • 3.1 先来学习几个概念
        • 3.2 信号发送的本质
        • 3.3 信号的阻塞
        • 3.4 信号的捕捉初识
        • 3.5 信号捕捉的本质
        • 3.6 信号集操作函数
      • 4. 信号的递达
        • 4.1 用户态和内核态理解
        • 4.2 操作系统,发出信号 到 进程执行信号 全过程
      • 5. 信号的总结
      • 6.补充知识 关键字 volatile

前言: 生活中有各种信号,需要我们去识别并做出相应的反应。进程也是如此,操作系统给进程发信号,进程会根据信号来做出相应的动作。信号是有多个的,比如老板现在打电话过来,让提交一下PPT,同时外卖小哥也打来电话,说下楼取一下外卖;这就需要人去衡量一下轻重缓急了,当然是吃饭重要,所以忽略老板的信号,直接去执行外卖小哥给的信号。本章呢,会很细节的带大家了解信号,控制信号,解密信号的处理原理。灰常银杏。


1. 信号的感性理解

  • 信号的产生,是操作系统发给进程的。
  • 进程在没收到信号前,是否可以做到识别以及处理将要来到的信号?当然可以,就好比人,看到红灯知道要停车,这是人通过学习而掌握的常识,进程也一样,对于如何处理信号,是它们的常识,本质上大佬在写进程源代码时,就设置好了对信号的识别。
  • 信号不会被立即处理,而是在合适的时候,去处理信号。就好比:上午母亲说记得收衣服,我收到这个信号了,我不会立即去收衣服,而是等衣服晾干了(合适的时机),才去收的衣服。当然这是感性的理解,后面会将到什么时候对于处理信号才是合适的时机。
  • 进程收到信号后,会保存起来,以备在合适的时机,去处理。
  • 保存在哪呢?进程控制块 struct task_struct 之中,所以信号本质也是一个数据。
  • 信号发送的本质:向进程控制块中,写入信号数据。
  • 信号发送的方式是多样的,但是本质都是操作系统向进程发送的。

我们可以先使用kill -l ,来查看信号列表:

在这里插入图片描述

本章只研究 1~31信号,这是写时信号, 43 ~ 64不是写时信号,先不考虑。其实如果想要了解所有这些信号的细节可以使用 man 7 signal ,来查看一下:

在这里插入图片描述

2. 发送信号的方式

  • 通过键盘发送信号,只针对前台进程
  • 进程异常,产生信号
  • 通过调用系统调用接口函数,向进程发送信号
  • 满足某些软件条件,也可以产生信号

2.1 键盘发送信号

常见的有 ctrl + c ,ctrl + z ,ctrl + ;都是用来终止进程的。

比如: 我写一个 死循环打印”hollow ly“

#include<stdio.h>
#include<unistd.h>int main()
{while(1){printf("hollow ly\n");sleep(1);}return 0;
}

接下来,运行我使用键盘,终止进程:

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


2.2 进程异常产生信号

当进程出现异常时,会产生信号,一般这种情况我们叫做程序崩溃,其实说白了,程序崩溃的本质就是操作系统,通过发送信号,来干掉这个程序。具体崩溃的原因,也可以通过获取信号的方式,来知晓;大家在学习进程等待中,不知道,是否还记得Core Dump 标志位 ?

在这里插入图片描述
就这个,code_dump标志位,这次来好好讲解一下它:

程序崩溃,一般情况下,我们不只想要知道它崩溃的原因,还想要知道它崩溃在哪行代码上,这就需要设置
core dump ,如果进程出现异常,它会接收到信号,从而设置 进程退出 收到的信号信息 在上图status 中的 0~7位,存的就是接收的信号信息;如果,想要知道程序,崩溃在哪行代码就需要设置 core dump。code_dump标志位表示的就是: 有core dump 信息为 1,没有core dump 信息为 0。

我来举个例子: 3 / 0 ,用 0作除数,肯定会导致进程异常退出。

#include<stdio.h>int main()
{int a =3;a /=0; return 0;
}

编译时会报错,不过没关系,编译好了运行时,异常退出,我们看一下运行结果:

在这里插入图片描述

好了,明显是程序崩溃了,我先要知道崩溃在何处?利用 core dump ,默认情况下,core dump 是 0,没有被设置,可以用 ulimit -a 查看:

在这里插入图片描述

所以先得设置 core dump,使用 ulimit -c 1024,再次查看一下:

在这里插入图片描述

我们再次运行程序,是这样的结果:

在这里插入图片描述

表明,已经有了core dump信息,而且当前目录下,还会有一个core. 文件:

在这里插入图片描述
可以查看一下,这个core. 文件,里面全是二进制,其实是调试信息:

使用gdb来调试可执行程序,然后 输入 core -file core文件名,得到程序崩溃在哪处以及崩溃原因:

在这里插入图片描述

所以综上: 进程异常退出的本质是发送信号给进程,如果想要知道程序崩溃在何处?方便事后调试,我们可以设置core dump,然后再次运行程序,就会有一个core file,里面有调试信息,最后使用gdb进行调试程序,输入
core -file core文件名,就可以看到详细的进程崩溃原因。


2.3 调用系统函数发送信号

kill 命令就是用的kill函数实现的,比如要杀死某个进程 kill -9 PID:

比如:我运行起来test,用 kill -9 杀死这个进程

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


介绍发送信号的三个接口函数:

  • int kill(pid_t pid, int signo);
  • int raise(int signo);
  • void abort(void);

在这里插入图片描述
kill()可以向任意的进程发送信号:

  • kill 的参数 :第一个参数 pid -> 向某个进程发送信号的PID,第二个参数 sig -> 发送的信号
  • kill 的返回值:返回 0表示成功,返回 -1 表示失败

在这里插入图片描述
raise()只能向自己发送信号

  • raise 的参数 : 发送的信号
  • raise 的返回值 :返回 0表示成功,返回 -1 表示失败

在这里插入图片描述

abort()函数,很简单粗暴,就是让当前的进程,异常退出。


我们来验证一下:对于raise()和abort(),我姑且不验证了,太简单了。

我们来模拟实现一下 kill 指令:

#include<sys/types.h>
#include<signal.h>
#include<stdio.h>
#include<stdlib.h>int main(int argc, char *argv[])
{if(argc != 3){ printf("输入格式有误: 请输入 kill PID signal\n");return 0;}int PID = atoi(argv[1]);int sn = atoi(argv[2]);int ret = kill(PID,sn);if(ret == 0){printf("指令发送成功\n");}else {printf("指令发送失败\n");}return 0;
}

比如:我现在形成的可执行文件 是 kill 。那么我在命令行运行 ./kill PID signal 就能够发送信号了。


2.4 触发软件条件,发送信号

比如之前学到命名管道,如果读端已经关闭,写端还在写入,那么系统会发送信号 13 来终止进程。

现在主要讲:alarm函数 和SIGALRM信号。

在这里插入图片描述
alarm()函数的作用是,设置一个时间,时间一到就会发送信号SIGALRM,默认行为是终止当前进程。

  • alarm()的参数:seconds,设置一个秒数,相当于计时;如果seconds设置为0,那么取消之前设置的alarm。
  • alarm()的返回值:返回值是0或者是以前设定的闹钟时间还余下的秒数。

举个例子:我们看看 1s 可以打印多少个数字

#include<unistd.h>
#include<stdio.h>int main()
{int n = 1;alarm(1);while(1){printf("%d\n",n);n++;}return 0;
}

在这里插入图片描述


3. 信号的控制

3.1 先来学习几个概念

  • 实际执行信号的处理动作称为信号递达(Delivery)
  • 信号从产生到递达之间的状态,称为信号未决(Pending)。
  • 进程可以选择阻塞 (Block )某个信号。
  • 被阻塞的信号产生时将保持在未决状态,直到进程解除对此信号的阻塞,才执行递达的动作.
  • 注意,阻塞和忽略是不同的,只要信号被阻塞就不会递达,而忽略是在递达之后可选的一种处理动作。

信号的流程
操作系统发来信号,进程保存信号,看这个信号是否被阻塞?

阻塞那么就先保存着,不阻塞那么就在合适的时机递达信号。

递达后有三种情况:执行信号的默认行为,忽略信号,执行自定义的信号行为。

注意: 阻塞 vs 忽略

阻塞根本就没有递达,一直保存着。
忽略是已经递达,只不过进程不理会它,进程不保存此信号。

3.2 信号发送的本质

信号发送的方式多样,但是本质是操作系统向进程控制块中的信号位图,进行写入。感觉还是抽象,我们来看看这些信号:

在这里插入图片描述
为啥是 1 ~ 31号为写时信号,信号[1,31]这其实是有规律的,能想像成位图嘛?当然可以!!!

假设 有一个无符号整型 int ,默认为 0,保存在进程控制块中,那么就是:

在这里插入图片描述
操作系统,发来信号:1。

那么这个int 的第一位 变成 1。
在这里插入图片描述
操作系统,再发过来信号2,就将第二个比特位设置为 1。

在这里插入图片描述
对,进程就是这样来保存信号的。

3.3 信号的阻塞

信号的阻塞,就会导致信号,不会被递达,也就是不会被进程执行,一直被存储在进程控制块中,存储就是对应的位图设置为 1 。 昂,信号阻塞是这样,但是进程是如何判定这个信号要被阻塞呢?答案是也是靠位图,那么必定也有一个位图用来判断信号是否被阻塞,设置为 0 表示为不阻塞,设置为 1 表示阻塞。

3.4 信号的捕捉初识

信号没有被阻塞,递达到进程后,进程有三种处理:

  1. 以默认信号方式处理
  2. 忽略此信号
  3. 自定义信号来处理

如果信号的处理动作是用户自定义函数,在信号递达时就调用这个函数,这称为捕捉信号。也就是第三种情况,学习一个函数 signal() ,它是就是用来捕捉信号,并且还可以自定义信号的行为:

在这里插入图片描述

  • signal()的参数:第一个参数 signum 是要捕捉的信号,可以是宏,或者是信号值;第二个参数是一个函数指针,也就是我们要进行自定义信号的行为,看一看上面,这个参数一个 void (*)(int)型函数指针。
  • signal()的返回值:返回的是我们自定义的函数指针,如果出错就返回 -1 。

例子:我们来捕捉一下 2号信号,也就是 ctrl + c 。

#include<stdio.h>
#include<signal.h>void header(int sig)
{printf("get a sig :%d\n",sig);
}int main()
{signal(2,header);while(1);return 0;
}

header()就是我们自定义的信号行为,那么现在程序运行起来,我们按 ctrl + c,发送 2号信号,就会自定义2号信号的行为。

运行一下:

在这里插入图片描述

很明显,我按下 ctrl +c,信号2 已经被自定义了。

还有一个函数. sigaction(),可以用于捕捉信号,不过需要我们定义一个结构体:

在这里插入图片描述
结构体:

在这里插入图片描述

  • sigaction()的参数:第一个参数 signum是我们要捕捉的信号;第二个参数 act是输入型参数,在这个结构体中,我们关注第一个结构体成员和第三个结构体成员,很明显sa_handler是一个函数指针,sa_mask表示要额外屏蔽的信号,函数调用结束会恢复被额外屏蔽的信号;第三个参数 oldact 是输出型参数,会保存信号之前的处理动作,不关心的话,可以设置为空。
  • sigaction()的返回值:成功返回0,出错返回 -1。

例子:捕捉 2号 信号,并额外屏蔽 3号信号

#include<stdio.h>
#include<signal.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>void header(int sig)
{printf("get a sig:%d \n",sig);
}int main()
{
// signal(2,header);
// struct sigaction at;
memset(&at, 0, sizeof(at));at.sa_handler = header;sigemptyset(&at.sa_mask);
sigaddset(&at.sa_mask, 3);sigaction(2,&at,NULL);while(1);return 0;
}

3.5 信号捕捉的本质

信号的处理可以按照默认情况,也可以忽略,也可以捕捉自定义行为。这是怎么办到的?

说明原因:信号是否阻塞,信号的保存,信号的行为其实用的是三张表

在这里插入图片描述

这幅图,非常重要,大家好好理解。

其实创建进程时,handler块 就已经保存,所有的信号的默认处理方法,存的都是函数指针 ;这幅图应该横着看,假如传来 1号 信号,先看看block位图的第一个比特位是否为 1 ,为 1就是阻塞,为 0就没有阻塞;pending位图第一个比特位设置为 1,如果为阻塞态那么 此 比特位一直是 1,表示一直保存,直到解除阻塞并递达后才置为 0 ;如果不为阻塞态,那么就在递达后从 1 置0;handler可以看作一个函数指针数组,数组的下标就是对应的信号,那么信号捕捉的本质是什么?那就是 对handler指针数组中的内容进行重写,改变了这个handler数组中信号对应的函数指针,就是所谓的信号捕捉。

在这里插入图片描述


3.6 信号集操作函数

其实就是对位图的操作,我们如果能够操作 block位图,就控制好了对信号是否阻塞?我们如果可以操作 pending位图,就可以查看到当前未决的信号;如果可以修改handler表中的函数指针,就完成信号捕捉!

我们一个一个的学:

在这里插入图片描述

#include <signal.h>
int sigemptyset(sigset_t *set);
int sigfillset(sigset_t *set);
int sigaddset (sigset_t *set, int signo);
int sigdelset(sigset_t *set, int signo);
int sigismember(const sigset_t *set, int signo); 
int sigprocmask(int how, const sigset_t *set, sigset_t *oset);
int sigpending(sigset_t *set);
int sigaction(int signum, const struct sigaction *act,struct sigaction *oldact);

首先,先看参数中有 sigset_t 类型,这个类型,我们是不能够 自己来进行操作的,比如 赋值,算术运算等都不可以,它只能通过函数接口,来进行初始化,或者是赋值等,这个类型,可以看作是 位图。

(1) sigemptyset(sigset_t *set) 是 用于初始化位图的

初始化set所指向的信号集,使其中所有信号的对应bit清零,表示该信号集不包含 任何有效信号。

(2) sigfillset(sigset_t *set)也用于初始化位图

函数sigfillset初始化set所指向的信号集,使其中所有信号的对应bit置为 1 ,表示 该信号集的有效信号包括系统支持的所有信号。

(3) sigaddset (sigset_t *set, int signo)int sigdelset(sigset_t *set, int signo) 是用于添加信号,删除信号,使用前需要对此信号集初始化

sigaddset和sigdelset在该信号集中添加或删除某种有效信号。

(4) sigismember(const sigset_t *set, int signo) 是用于判断的

sigismember是一个布尔函数,用于判断一个信号集的有效信号中是否包含某种 信号,若包含则返回1,不包含则返回0,出错返回-1。

以上的操作,相当于操作 位图 结构。

(5) int sigprocmask(int how, const sigset_t *set, sigset_t *oset) 用于查看 block表或者修改 block表

先看参数:

  • 第一个参数 how :表示要如何对当前进程的block操作,有三个宏定义,可供传参

在这里插入图片描述

SIG_BLOCK : 包含了要添加当前信号屏蔽字的信号,相当于 mask |= set 。
SIG_UNBLOCK :包含了我们希望从当前信号屏蔽字中解除阻塞的信号,相当于 mask = mask& ~set。
SIG_SERMASK : 设置当前信号屏蔽字为set所指向的值,相当于 mask = set。

  • 第二个参数 set : 是我们传进来的位图结构,根据how的指示来进行 对 block的操作。
  • 第三个参数 oset :如果oset是非空指针,则读取进程的当前信号屏蔽字通过oset参数传出,是对以前屏蔽字的记录,屏蔽字就可以理解成记录阻塞的位图结构。

其返回值: 成功返回 0,失败返回 -1。

(6) int sigpending(sigset_t *set)

参数 set 是一个输出型参数:

读取当前进程的未决信号集,通过set参数传出。调用成功则返回0,出错则返回-1。

(7)int sigaction(int signum, const struct sigaction *act,struct sigaction *oldact) 这个函数上文有讲解

需要对以上强调一点 :并不是所有的信号都是可以被屏蔽和捕捉的,这是好理解的,如果所有的信号都能被屏蔽,被捕捉,那么就能够搞出一个金刚不坏的进程,这是操作系统不想看到的,所以 像 9号信号,它是无法被屏蔽,捕捉的。

例子:现在我要屏蔽一下 2号信号:

#include<stdio.h>
#include<signal.h>
#include<unistd.h>int main()
{sigset_t set;//初始化 set sigemptyset(&set);
//添加2号信号,被block阻塞sigaddset(&set,2);sigprocmask(SIG_SETMASK,&set,NULL);int count =10;while(count){printf("count is: %d\n",count);sleep(1);count--;}// 解除阻塞sigprocmask(SIG_UNBLOCK,&set,NULL);while(1);return 0;
}

运行时,我们可以看到,2信号确实被屏蔽了,但是10s后,我们之前发送的 2 信号,不被屏蔽了,就会被抵达,并执行2信号的默认行为:

在这里插入图片描述

现在要求,不是说过,信号被阻塞,无法递达,但是会在pending位图中保存吗?我想要看一看,到底有没有被保存,所以我们需要利用 函数接口 sigpending(),以及sigismember() 。

我们实现一下,还是刚才的例子,只不过要查看一些 pending位图:

#include<stdio.h>
#include<signal.h>
#include<unistd.h>void show_pending(sigset_t *set)
{printf("curr process pending: ");int i=0;while(++i){ if(sigismember(set, i)){printf("1");}else{printf("0");}if(i == 31){break;}}printf("\n");
}int main()
{sigset_t set;//初始化 set sigemptyset(&set);
//添加2号信号,被block阻塞sigaddset(&set,2);sigprocmask(SIG_SETMASK,&set,NULL);int count = 0;sigset_t pending;while(1){sigemptyset(&pending);sigpending(&pending);show_pending(&pending);sleep(1);count++;if(count == 10){sigprocmask(SIG_SETMASK, &set, NULL);//2号信号的默认动作是终止进程,所以看不到现象printf("恢复2号信号,可以被递达了\n");break;}} return 0;
}

在这里插入图片描述


4. 信号的递达

上文讲过,信号是怎么传送的?本质是操作系统想进程发送信号。信号是如何控制的?有三张表,分别控制 阻塞,保存,信号行为。信号是怎么递达的?上面说过,在合适的时候,信号会递达(进程执行信号),什么是合适的时候?递达后,可以处理默认信号行为,捕捉后的行为,或者忽略,这个通过学习信号捕捉,大家都懂了,就是通过替换 handler表中的函数指针,现在的问题就是 : 进程如何判断 现在是处理信号的合适时机!!!

先给出结论: 信号递达的合适时机 -> 从内核态 切换回 用户态 就会进行信号检测和信号处理,也就是 检查那三个表


4.1 用户态和内核态理解

可以复习一下,我们知道进程都是有虚拟地址空间的,在高低出有内核空间,所以内核的数据代码在内核空间。毕竟是虚拟的,每个进程都有独立的的页表,但是我想说的是,所有的进程都是共享的同一份内核页表,为什么?因为无论进程如何切换,内核就这有一个。为什么要搞一个内核空间呢?因为要区分内核和用户,操作系统是不信任用户的,所以你只有是内核态,才能访问内核的代码和数据。

所以:

  • 内核态:使用内核级页表,只能访问内核的数据和代码
  • 用户态:使用用户级页表,只能访问用户的数据和代码

我可以简易的画图,帮助大家理解:

在这里插入图片描述


那么何时,会由用户态切到内核态呢?比如 调用系统函数
在这里插入图片描述

4.2 操作系统,发出信号 到 进程执行信号 全过程

进程在运行,操作系统发来信号,进程就会中断或者异常,从用户态切到内核态,去查看是什么信号?操作系统,你要让我做什么?有点类似,你在吃饭,公司给你打了个紧急电话,你火速从一个干饭人员,变成一个员工,跑到公司,看看发生什么事了?

在这里插入图片描述

现在开始查这三张表:
在这里插入图片描述

自定义的话,需要返回到用户态去执行自定义的函数,然后返回到内核态,从内核态再返回。这有点有始有终的感觉,你开始是从内核进来的,那么也从内核态出去。

画图就是:

在这里插入图片描述

那么我有个疑问:这个过程有多少次用户和内核的切换?

来个妙招:

在这里插入图片描述


5. 信号的总结

以上就是操作系统中,信号的讲解。

我们从信号的发送,信号发送中,信号发送后,种种细节都说了说。

在这里插入图片描述
就是这样的逻辑,走下来的。当然,其中也穿插了不少补充知识。


6.补充知识 关键字 volatile

volatile 在C语言中有所学习,到那时可能有点小懵,在这里学习,就感觉很轻松了。

我先编写一个简单的程序:

#include<stdio.h>
#include<signal.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>int flag =0;
void header(int sig)
{printf("get a sig:%d \n",sig);flag =1;printf("flag 0 -> 1\n");
}int main()
{signal(2,header);while(!flag);printf("进程退出\n");return 0;
}

这个程序,捕捉2号信号后,将flag 由0 置为 1,从而退出循环,进程退出。

看看运行结果:
在这里插入图片描述

没什么问题,但是如果编译的时候,优化了呢?有影响吗?我们来看看,编译的时候 加上选项 -3 就是编译优化。

在这里插入图片描述
运行结果是:无法进行程序退出了,说明flag还是 0,那么它的值没有被修改吗?答案是修改了,只不过因为优化编译,它在cpu中的寄存器中的值是1,而内存中的值还是 0。 所以就有了 volatile。flag用它修饰后,表示不要对此变量作任何优化,而是保持它在内存中的一贯性。


结尾语: 以上就是本篇内容,觉得有帮助的老铁可以点一个小赞!!!


http://chatgpt.dhexx.cn/article/TiZAk5Sn.shtml

相关文章

信号与系统--信号以及系统的介绍(一)

文章目录 一、绪论1、概述2、信号及其分类3、系统及其分类 总结 一、绪论 1、概述 课程内容 两大对象 &#xff1a; 信号、系统 三种分析方法&#xff1a;时域分析方法、频域分析方法、复频域分析方法 三大变换&#xff1a;傅里叶变换、拉普拉斯变换、Z变换 我们会用这些方法去…

第一章:绪论与信号系统概述

在学习通信原理之前&#xff0c;我们先回顾一下通信原理的数学理论基础——信号与系统讲了些什么&#xff0c;有哪些难以理解的问题。 下面开始第一章&#xff08;以吴大正主编的第五版教材为依据&#xff0c;以下简称《信号》&#xff09; PS:这是我复习知识时整理的&#x…

我彻底服了,大牛讲解信号与系统(通俗易懂)

我彻底服了,大牛讲解信号与系统(通俗易懂) (2015-10-13 21:22:36) 转载▼ 分类&#xff1a; 电力电子技术 第一课什么是卷积卷积有什么用什么是傅利叶变换什么是拉普拉斯变换 引子 很多朋友和我一样&#xff0c;工科电子类专业&#xff0c;学了一堆信号方面的课&#xff0c;…

3.16(杨神)

分组背包搞树形dp多叉转二叉 原理存储进行输出方案 分组背包搞树形dp 多叉转二叉 原理 左儿子&#xff0c;右兄弟 存储 for(int i1;i<n;i){xxread();yyread();vvread();//xx为yy的son。 b[xx]s[yy];s[yy]xx;value[i]vv;} 进行 不选 f[i][j]f[rr][j] 选 f[i][j]f[ll][…

一些社会运行的底层规律,和你的利益息息相关

点击上方蓝字关注「中产之路」 任志强是房地产行业为数不多敢讲真话的大佬&#xff0c;早期因为坚持讲真话&#xff0c;孜孜不倦&#xff0c;开启民智&#xff0c;观点尚未被大众认可&#xff0c;一度成为全民公敌&#xff0c;也有了“任大炮”的称号。退休后的他&#xff0c;依…

数据结构—共享栈

数据结构-栈(Ⅳ) 共享栈 利用栈底位置相对不变的特性&#xff0c;可让两个顺序栈共享一个一维数组空间&#xff0c;将两个栈的栈底分别设置在共享空间的两端&#xff0c;两个栈顶向共享空间的中间延伸。 共享栈是为了更有效地利用存储空间&#xff0c;两个栈的空间相互调节&a…

数据结构遍历顺序栈_数据结构:顺序栈的实现

数据结构&#xff1a;顺序栈的实现 1、快速开始 栈是一种遵循元素后进(Push)先出(Pop)规则的线性表&#xff0c;即最后加入的元素最先出来&#xff0c;它的实现可以用数组或者链表。 它的特点如下&#xff1a; 后入先出&#xff0c;先入后出。 除了头尾节点之外&#xff0c;每一…

Java数据结构-栈的应用

第1关&#xff1a;利用栈实现整数的十进制转八进制 本关任务&#xff1a;基于栈stack数据结构解决整数十进制转八进制的问题。 第2关&#xff1a;利用栈判断字符串括号是否匹配 本关任务&#xff1a;基于栈stack数据结构判断字符串中的括号是否匹配&#xff0c;字符串中仅包含…

【数据结构——栈篇】

【数据结构——栈篇】 目录 【数据结构——栈篇】一、栈的顺序存储——顺序栈1、顺序栈的表示和实现2、顺序栈的定义2、顺序栈初始化3、顺序栈入栈4、顺序栈出栈5、取顺序栈栈顶元素6、输出栈内容 二、栈的链式存储——链栈1、链栈的存储结构2、栈链的初始化3、链栈的入栈4、链…

数据结构遍历顺序栈_数据结构和算法-栈结构

栈的定义 栈是一种后进先出的数据结构。 栈是限制插入和删除只能在一个位置上的线性表。允许删除和插入的一端位于表的末端,叫做栈顶。不允许删除和插入的另一端叫做栈底。对栈的基本操作有push(压栈)和pop(出栈)。 图示: 栈的实现 栈的实现主要包括两种方式:顺序栈和链表栈…

数据结构之栈以及栈的基本操作

栈 文章目录 栈前言进栈出栈的变化形式栈的实现栈的顺序存储结构&#xff1a;栈的链式存储结构&#xff1a;文件的创建栈结构的定义栈的初始化入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空销毁栈 括号匹配问题 前言 栈是限定仅仅在表尾进行插入和删除操作的线性表。…

【数据结构二】栈

数组是一种线性结构&#xff0c;并且可以在任意位置插入和删除数据。但是有时候&#xff0c;为了实现某些功能&#xff0c;必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。 栈&#xff1a;Stack&#xff0c;也是一种常见的数据结构。它是一种受限的线性结构…

数据结构 栈 入栈 输出 出栈

数据结构 栈 入栈 输出 出栈 #include<bits/stdc.h> /* #include<iostream> #include<> */ using namespace std; //pA->p(Next)pB->p(top)含义是pA指向pB typedef struct Node//有节点的数据类型 {int data;//数据域struct Node * pNext; }NODE,*PN…

数据结构-栈

栈的定义 栈是一种特殊的线性表&#xff0c;仅允许在表的一端进行插入和删除运算。这一端被称为栈顶&#xff08;top&#xff09;&#xff0c;相对地&#xff0c;把另一端称为栈底&#xff08;bottom&#xff09;。向一个栈插入新元素又称作进栈、入栈或压栈&#xff08;push&…

数据结构-栈及栈的应用

目录 栈的概述 部分算法分析 顺序栈的表示和实现 global.h Stack.h StackTest.cpp 运行结果 栈的应用 数的任意进制转换 括号匹配检验 栈的概述 栈是一种重要的线性结构&#xff0c;属于一种操作受限的线性表栈(stack) 是限定仅在表尾进行插入或删除操作的线性表表尾端…

java数据结构-栈

栈 1、栈的定义 栈&#xff08;Stack&#xff09;&#xff1a;是只允许在一端进行插入或删除的线性表。首先栈是一种线性表&#xff0c;但限定这种线性表只能在某一端进行插入和删除操作。 栈顶&#xff08;Top&#xff09;&#xff1a;线性表允许进行插入删除的那一端。 栈底…

数据结构栈(顺序栈、链栈、插入push、删除pop)、队(循环队,链队、入队push,出队pop)知识点梳理

数据结构栈知识点梳理 一 栈的定义 栈&#xff08;stack&#xff09;是限定仅在表尾进行插入和删除操作的线性表 不含任何元素的栈称为空栈 允许插入和删除的一端成为栈顶&#xff08;top&#xff09;&#xff0c;另一端称为栈底&#xff08;bottom&#xff09; 具有LIFO&a…

数据结构栈和队列

整本书的知识点&#xff0c;点击右方链接&#xff1a;整本书笔记知识点 文章目录 三、栈和队列3.1、栈和队列的定义和特点3.1.1、栈的定义和特点3.1.2、队列的定义和特点 3.2、案例引入3.3、栈的表示和操作的实现3.3.1、栈的类型定义3.3.2、顺序栈的表示和实现3.3.3、链栈的表示…

C++数据结构——栈

C数据结构——栈 最近计划再复习一遍数据结构&#xff0c;看到一篇博客&#xff1a;https://www.cnblogs.com/QG-whz/p/5170418.html#_label0。 1、栈(Stack)是一种线性存储结构&#xff0c;它具有如下特点&#xff1a; &#xff08;1&#xff09;栈中的数据元素遵守“先进后…

数据结构 栈-链栈及基本操作

目录 一.栈的定义二.栈的特点三.栈的理解四.链栈引入五.链栈定义六.链栈的结构体设计七.链栈的基本操作7.1链栈的初始化7.2链栈判空7.3链栈入栈7.4链栈出栈7.4取栈顶元素 八.总结 一.栈的定义 栈是限定仅在表尾进行插入和删除操作的数据结构&#xff08;受到限制的线性表&…