一、栈的介绍

1.1 系统栈（内存布局中的栈）

这是操作系统在管理进程内存时划分出的一块具体物理内存区域（通常位于虚拟地址空间的高地址，向下增长）。

  • 核心作用：专门用来管理函数调用。

  • 存储内容：存放局部变量、函数参数、返回地址、栈帧（Stack Frame）信息。

  • 行为依据：它遵循“先进后出”的规则

1.2 栈结构（数据结构中的栈）

① 这是数据结构中的一种线性存储结构，只允许从一端进行数据插入和删除的线性存储结构，是一种逻辑模型/抽象数据类型。

  • 核心规则：先进后出（FILO，Firstt In Las Out）

② 栈结构分类：顺序栈（空间连续）、链式栈（非连续空间）

③ 顺序栈分类：满增栈，满减栈，空增栈，空减栈

     满栈/空栈：栈顶所在位置是否存有元素
     增栈/减栈：根据栈的生长方向决定

  • 满栈（Full Stack）：栈顶指针 指向最后一个被压入栈的有效数据（即栈顶元素）。此时，如果直接向 P 指向的地址写数据，会覆盖掉现有数据。
  • 空栈（Empty Stack）：栈顶指针 指向最后一个有效数据之上的下一个空闲位置（即栈顶元素的下一个空白单元）。此时，P 指向的地址是空的，可以直接写入数据。
  • 增栈（Ascending Stack）：栈底在低地址，栈顶在高地址。压栈时，栈顶指针 向高地址方向移动（地址越来越大）。
  • 减栈（Descending Stack）：栈底在高地址，栈顶在低地址。压栈时，栈顶指针 向低地址方向移动（地址越来越小）。
类型 压栈（PUSH）执行顺序 示意图理解
满增栈 ① 先移动指针（+1） → ② 再写入数据 指针先指向下一个高地址空白处，把数据填进去。此时指针指向有效数据。
空增栈 ① 先写入数据 → ② 再移动指针（+1） 指针原本就指向空白处，先把数据填进去，然后指针向上移动到下一个空白位置。此时指针指向空位。
满减栈 ① 先移动指针（-1） → ② 再写入数据 （x86常用）指针先减1指向低地址的空位，填入数据。此时指针指向有效数据。
空减栈 ① 先写入数据 → ② 再移动指针（-1） 指针原本指向空白处，先填入数据，然后指针向下移动到下一个低地址空白处。此时指针指向空位。

二、链式栈的实现

2.1  链式栈介绍

① 链式栈是一种采用单链表来实现栈的抽象数据类型（ADT）。其中，栈顶指针（Top）通常指向链表的头结点（或第一个数据节点），所有的入栈（Push）和出栈（Pop）操作都限制在链表的表头这一端进行。

 ② 链式栈在内存中由一系列不连续的节点（Node）组成，每个节点包含两个域：

  • 数据域：存储元素的值。

  • 指针域：存储下一个节点的地址（next）。

2.2   栈的声明

typedef int DataType_t;
typedef struct node // 定义节点结构
{
	DataType_t data; // 数据域
	struct node *pnext; // 指针域
}SNode_t;

typedef struct stack // 定义链式栈
{
	SNode_t *ptop; // 栈顶指针
	int clen;  // 栈中元素个数
}Stack_t;

2.3 创建链式栈对象和节点

//创建链式栈
Stack_t *create_link_stack()
{
	//pstack 一个指针变量，用来接收 malloc 返回的内存首地址
    Stack_t *pstack = malloc(sizeof(Stack_t)); //在堆区申请内存
	if (NULL == pstack) //内存分配失败处理
	{
		printf("malloc error\n");
		return NULL;
	}
	pstack->ptop = NULL; //初始化，栈顶指针指向 NULL
	pstack->clen = 0;
	return pstack;
}

//创建链式栈中节点
SNode_t *create_node(DataType_t data)
{
	SNode_t *pnode = malloc(sizeof(SNode_t));
	if (NULL == pnode)
	{
		printf("malloc error\n");
		return NULL;
	}
    //将函数参数传入的数据存入节点的数据域，完成值的拷贝
	pnode->data = data;
	pnode->pnext = NULL;
	return pnode;
}

2.4 判断是否为空栈

//链式栈中判空函数
int is_empty_stack(Stack_t *pstack)
{
    //返回 1（真）表示空栈，返回 0（假）表示非空
	return NULL == pstack->ptop; 
}

2.5 入栈

//链式栈的入栈（Push）
int push_stack(Stack_t *pstack, DataType_t data)
{
	SNode_t *pnode = create_node(data); //创建新节点
	if (NULL == pnode) //堆内存耗尽
	{
		return -1;
	}	
	pnode->pnext = pstack->ptop; //新节点的 pnext 指向当前栈顶节点
	pstack->ptop = pnode; //将栈顶指针 ptop 更新为新节点
	pstack->clen++; //更新栈长度
	return 0; 
}

2.6 出栈 

① 函数传参：

  • 入参：函数内部需要使用的条件
  • 出参：通过参数向被调函数传递结果

② 二级指针：

  • 被调函数中修改主调函数中的指针变量，需要传递该变量的地址，形参使用二级指针
  • 指针数组，数组的数组名是二级指针
//链式栈的出栈（Pop）
int pop_stack(Stack_t *pstack, DataType_t *pdata)
{
	if (is_empty_stack(pstack))
	{
		return -1;
	}	
    //定义一个临时指针 ptmp，保存当前栈顶节点的地址
	SNode_t *ptmp = pstack->ptop;
    //将栈顶指针更新为原栈顶节点的下一个节点
	pstack->ptop = ptmp->pnext;
	if (pdata != NULL) //判断调用者是否提供了有效的接收指针
	{
		*pdata = ptmp->data; //将备份节点中的数据赋值给调用者传入的变量
	}
	free(ptmp); //调用 free 函数，将备份节点占用的堆内存归还给操作系统
	pstack->clen--; //更新栈长度
	return 0;
}

2.7 遍历栈

void show_stack(Stack_t *pstack)
{
	SNode_t *ptmp = pstack->ptop;
	while (ptmp)
	{
		printf("%d ", ptmp->data);
		ptmp = ptmp->pnext;
	}
	printf("\n");
}

2.8 获取栈顶元素

int get_stack_top(Stack_t *pstack, DataType_t *pdata)
{
	if (is_empty_stack(pstack))
	{
		return -1;
	}
	if (pdata != NULL)
	{
        //通过栈顶指针 ptop 直接访问栈顶节点的数据域
		*pdata = pstack->ptop->data; 
	}
	return 0;
}

2.9 销毁栈

void destroy_stack(Stack_t *pstack)
{
	while (!is_empty_stack(pstack))
	{
		//传入 NULL 作为第二个参数，表示只删除节点，不关心数据值
       pop_stack(pstack, NULL);
	}
	free(pstack);
}

2.10 附件代码

① stack.h

#ifndef __STACK_H__
#define __STACK_H__

typedef int DataType_t;
typedef struct node
{
	DataType_t data;
	struct node *pnext;
}SNode_t;

typedef struct stack
{
	SNode_t *ptop;
	int clen;
}Stack_t;

extern Stack_t *create_link_stack();
extern int push_stack(Stack_t *pstack, DataType_t data);
extern void show_stack(Stack_t *pstack);
extern int pop_stack(Stack_t *pstack, DataType_t *pdata);
extern int get_stack_top(Stack_t *pstack, DataType_t *pdata);
extern void destroy_stack(Stack_t *pstack);

#endif

② stack.c

#include "stack.h"
#include <stdio.h>
#include <stdlib.h>

Stack_t *create_link_stack()
{
	Stack_t *pstack = malloc(sizeof(Stack_t));
	if (NULL == pstack)
	{
		printf("malloc error\n");
		return NULL;
	}
	pstack->ptop = NULL;
	pstack->clen = 0;
	return pstack;
}

SNode_t *create_node(DataType_t data)
{
	SNode_t *pnode = malloc(sizeof(SNode_t));
	if (NULL == pnode)
	{
		printf("malloc error\n");
		return NULL;
	}
	pnode->data = data;
	pnode->pnext = NULL;
	return pnode;
}

int push_stack(Stack_t *pstack, DataType_t data)
{
	SNode_t *pnode = create_node(data);
	if (NULL == pnode)
	{
		return -1;
	}
	pnode->pnext = pstack->ptop;
	pstack->ptop = pnode;
	pstack->clen++;
	return 0;
}

void show_stack(Stack_t *pstack)
{
	SNode_t *ptmp = pstack->ptop;
	while (ptmp)
	{
		printf("%d ", ptmp->data);
		ptmp = ptmp->pnext;
	}
	printf("\n");
}

int is_empty_stack(Stack_t *pstack)
{
	return NULL == pstack->ptop;
}

int pop_stack(Stack_t *pstack, DataType_t *pdata)
{
	if (is_empty_stack(pstack))
	{
		return -1;
	}	
	SNode_t *ptmp = pstack->ptop;
	pstack->ptop = ptmp->pnext;
	if (pdata != NULL)
	{
		*pdata = ptmp->data;
	}
	free(ptmp);
	pstack->clen--;
	return 0;
}

int get_stack_top(Stack_t *pstack, DataType_t *pdata)
{
	if (is_empty_stack(pstack))
	{
		return -1;
	}
	if (pdata != NULL)
	{
		*pdata = pstack->ptop->data;
	}
	return 0;
}

void destroy_stack(Stack_t *pstack)
{
	while (!is_empty_stack(pstack))
	{
		pop_stack(pstack, NULL);
	}
	free(pstack);
}

③ main.c

#include <stdio.h>
#include "stack.h"
int main(int argc, const char *argv[])
{
	Stack_t *pstack = NULL;
	DataType_t data;
	pstack = create_link_stack();	
	if (NULL == pstack)
	{
		return -1;
	}
	
	push_stack(pstack, 1);
	push_stack(pstack, 2);
	push_stack(pstack, 3);
	push_stack(pstack, 4);
	push_stack(pstack, 5);
	
	show_stack(pstack);

	int ret = pop_stack(pstack, &data);
	if (0 == ret)
	{
		printf("data = %d\n", data);
	}
	
	ret = get_stack_top(pstack, &data);
	if (0 == ret)
	{
		printf("top %d\n", data);
	}
	
	destroy_stack(pstack);
	return 0;
}

三、 malloc疑点

①  在申请内存空间时需要指定大小，但释放时只需传入指针而无需提供大小，这是为什么？

      因为malloc在申请内存时，操作系统/运行库内部维护了一张“地址-大小”映射表（或存储在返回地址前的头部信息中）。free只需传入指针，就能通过查表或读头部找到要释放的确切大小，因此无需额外传参。

  • 底层记账机制：malloc申请内存时，内存分配器会额外存储此次分配的元数据（包括大小、起始地址等）。这些元数据要么存放在返回地址前的头部（Header）中，要么存放在操作系统维护的映射表里。

  • 释放时的查找流程：free(p)被调用时，运行库通过指针p逆向寻址找到头部，或查表定位到该内存块的实际大小，然后精准回收整块内存。

  • 避免野指针：内存释放后，该指针p仍然保存着旧地址（变成野指针）。最好在free(p)后立即执行p = NULL;，防止后续误操作（如if(p != NULL)判断失效）导致悬空指针（Dangling Pointer）引发的崩溃。

# 数据结构 # 算法 # linux # ubuntu # c语言 # 开发语言
Logo
openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

cover

二进制安全-Reverse | 底层基础 01 | 从零认识 Reverse：逆向工程研究范畴与学习目标梳理

avatar openEuler 社区

喂狗在操作系统(rtos)上面的正确用法

喂狗在操作系统(rtos)上面的正确用法

avatar openEuler 社区

深入了解 AiPy（爱派）：当桌面 AI 不再只是聊天

它的技术底座是自研的 Python-Use 范式，核心理念是"No Agents, Code is Agent"，不依赖插件、工具包或第三方 Agent，仅通过自然语言就能生成、运行和调试 Python 或 Node.js 程序，让 AI 真正在操作系统层面完成任务。这款由知道创宇出品的 AI 桌面智能体，正在把桌面 AI 从"能聊天"推进到"能干活"的阶段。市面上的开源本地大模型桌面客户端 国产

avatar openEuler 社区