C语言深入探究栈的原理

2024-09-30 12:25:48

栈

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。如下图：

下面用顺序表（数组）来实现栈；

建立一个顺序表结构：

typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //表示栈顶
int capacity;//表示容量，当容量满时，扩容；
}ST;

创建一个结构体变量：ST st；在传数据之前要先初始化；不然当你没赋值就直接访问时会出现乱码或者报警告；

//初始化
void StackInit(ST* ps)
{
	assert(ps);//断言，保证传进来的非空；
	ps->a = NULL;//先将顺序表指针指向空；
	ps->top = 0;//栈顶位置表示0位置；
	ps->capacity = 0;//容量为0；
}

接下来就是向栈内传数据（压栈），要传结构体地址和要传的数据；

//压栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
    //判断：数据从下标0开始，因为pot表示该插入的栈顶的位置，也是压栈的个数
    //一次插入一个数据，所以数据数量与总容量相同时，就需要扩容
	if (ps->top == ps->capacity)
	{
		//扩容，扩二倍
        //使用三目运算符判断，当是第一次扩容时，用二倍没变化，所以固定开辟4个空间；
		int retcapa = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* ret = (STDataType*)realloc(ps->a, sizeof(STDataType)*retcapa);
		if (ret != NULL)
		{
			ps->a = ret;
			ps->capacity = retcapa;
		}
		else
		{
			printf("realloc开辟失败，退出！");
			exit(-1);
		}
	}
    //扩容完，更新数据；
	ps->a[ps->top] = x;
	ps->top++;
}

有压栈就有出栈；出栈用两个接口。1.返回栈顶数据 2.出栈

因为有时候只需要访问栈顶数据不需要出栈，如果想出栈又想返回数据，就先调用1，再调用2；

//返回栈顶元素；
STDataType StackTop(ST* ps)
{
	assert(ps);

    //直接断言要求栈中必须要有数据；
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

//出栈，顺序表直接把下标减一即可
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

有时候还需要返回栈中元素

//返回栈中元素个数；
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

在一些复杂结构中要直接调用查看栈中是否有数据，判断栈是否为空；

//判断栈中元素是否为空，返回布尔类型
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//注意这里是没有数据是返回true;
}

用动态开辟的空间就必须手动释放

//释放；顺序表释放头指针即可
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

看一下如何调用的：

int main()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPush(&st, 7);

    printf("%d\n",StackTop(&st));

    StackPop(&st);
	StackPush(&st, 8);

	printf("%d\n",StackTop(&st));
    StackPop(&st);

	StackDestroy(&st);
	return 0;
}

到此这篇关于C语言深入探究栈的原理的文章就介绍到这了,更多相关C语言栈内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言数据结构之使用链表模拟栈的实例

C语言数据结构之使用链表模拟栈的实例以下是"使用链表模拟栈"的简单示例: 1. 用C语言实现的版本 #include<stdio.h> #include<stdlib.h> typedef char datatype; typedef struct node{ datatype data; struct node *next; } stack; stack* m_stack = NULL; /* 创建链表,从表头插入新元素 */ void creat(void
C语言编程数据结构栈与队列的全面讲解示例教程

目录一.栈的表示和实现 1栈的概念和结构 2栈的初始化 3压栈(栈顶插入一个数据) 4出栈(栈顶删除一个数据) 5取栈顶元素 6取栈顶元素 7判断栈是否为空二.队列的表示和实现 1队列的概念及结构 2队列的实现 3队列初始化 4入队(队尾插入一个数据) 5出队(队头删除一个数据) 6取队头数据 7取队尾数据 8计算队列中数据个数 9判断队列是否为空 10销毁队列总结一.栈的表示和实现 1栈的概念和结构栈:一种特殊的线性表(逻辑上数据是连着放的),其只允许在固定的一端进行插入和删除操作.
C语言数据结构之栈简单操作

C语言数据结构之栈简单操作实验: 编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能: (1)初始化顺序栈 (2)插入元素 (3)删除栈顶元素 (4)取栈顶元素 (5)遍历顺序栈 (6)置空顺序栈分析: 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表. 对于顺序栈,入栈时,首先判断栈是否为满,栈满的条件为:p->top= =MAXNUM-1,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢. 出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作
C语言数据结构进阶之栈和队列的实现

目录栈的实现: 一.栈的概念和性质二.栈的实现思路三.栈的相关变量内存布局图四.栈的初始化和销毁五.栈的接口实现: 1.入栈 2.出栈 3.获取栈顶的数据 4.获取栈的元素个数 5.判断栈是否为空队列的实现: 一.队列的概念和性质二.队列的实现思路三.队列相关变量的内存布局图四.队列的初始化和销毁五.队列的接口实现: 1. 入数据 2.出数据 3.取队头数据 4.取队尾数据 5.获取队列元素个数 6.判断队列是否为空总结栈的实现: 一.栈的概念和性质栈(stack)又名
C语言数据结构栈的基础操作

C语言数据结构栈的基础操作实现了栈的基本操作,包括入栈出栈,以及书上没有写的销毁栈等操作,并对代码进行了详细的注释 MyStack.h /* * Include.h * * Created on: 2016.11.23 * Author: Jack Cui */ #ifndef MYSTACK_H_ #define MYSTACK_H_ #include <stdlib.h> #include <stdio.h> #include <malloc.h> /*栈(St
C语言编程数据结构的栈和队列

目录栈数组实现标题全部代码 Stack_array.c Stack_array.h 初始化数组栈满栈后扩容是否为空栈压栈和退栈链表实现 stack_chain.h stack_chain.c 整个压栈流程整个弹栈流程出栈情况队列队列的实现 queue_chain.h queue_chain.c 一个结构体类型用于维护这个队列概念流程图入队列的实现出队列的实现是否空队栈栈是一种以后进先出为顺序对对象进行添加或删除的数据结构对栈进行形象记忆就像是桌子上的一堆书或一
C语言深入探究栈的原理

栈压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶. 出栈:栈的删除操作叫做出栈.出数据也在栈顶. 栈的实现栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些.因为数组在尾上插入数据的代价比较小.如下图: 下面用顺序表(数组)来实现栈: 建立一个顺序表结构: typedef int STDataType; typedef struct Stack { STDataType* a; int top; //表示栈顶 int capacity;//表示容量,当容量满时,扩容
C语言深入探究动态规划之线性DP

目录写在前面数字三角形最长上升子序列最长上升子序列 II 最长公共子序列写在前面之前讲过背包问题,不知道大家忘了吗,如果忘了可以点这里,这次是线性DP 数字三角形状态表示:f[i,j],到点i,j的最大路径状态计算:f[i,j] = MAX(f[i-1,j-1]+a[i,j],f[i-1,j]+a[i,j]) 看图,以例题为例,将它看成五行五列的三角形,每个点都可以用坐标表示.那么我们可以得知到一个数的最大路径要么来自左上,要么来自右上.左上的数用f[i-1,j-1]表示,右上的
C语言深入探究自定义类型之结构体与枚举及联合

目录 1.结构体 1.1结构体类型的声明 1.2结构的自引用 1.3结构体变量的定义和初始化 1.4结构体内存对齐 1.5结构体传参 1.6结构体实现位段(位段的填充&可移植性) 2.枚举 2.1枚举类型的定义 2.2枚举的优点 3.联合 3.1联合类型的定义 3.2联合的特点 3.3联合大小的计算 1.结构体 1.1结构体类型的声明结构是一些值的集合,这些值称为成员变量.结构的每个成员可以是不同类型的变量这里给大家举个列子演示一下: //定义一个学生的结构体 typedef struct
C语言实现颠倒栈的方法

本文实例讲述了C语言实现颠倒栈的方法,很实用的技巧.分享给大家供大家参考之用. 具体实现方法如下: #include <iostream> #include <iterator> #include <algorithm> #include <vector> #include <stack> using namespace std; void initializeStack(stack<int> &st) { for(int i
C语言表、栈和队列详解及实例代码

C语言表.栈和队列详解表ADT 形如A1,A2,A3-An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素:CreateEmpty创建一个空表:Find返回关键字首次出现的位置:Insert和Delete从表的某个位置插入和删除某个关键字. 对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现.链表(linked list)由一系列不必在内存中相连的结构组成,每个结构均含有元素和指
Java语言实现数据结构栈代码详解

近来复习数据结构,自己动手实现了栈.栈是一种限制插入和删除只能在一个位置上的表.最基本的操作是进栈和出栈,因此,又被叫作"先进后出"表. 首先了解下栈的概念: 栈是限定仅在表头进行插入和删除操作的线性表.有时又叫LIFO(后进先出表).要搞清楚这个概念,首先要明白"栈"原来的意思,如此才能把握本质. "栈"者,存储货物或供旅客住宿的地方,可引申为仓库.中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈.出栈的说法. 实现方式是
总结易语言节点与栈的操作方法

以下就是本次我们给大家分享了易语言节点与栈的操作的实例代码和相关内容: .版本 2 .支持库 EDataStructure .程序集窗口程序集1, , , 易语言节点与栈的操作 .子程序 _按钮1_被单击 .局部变量栈, 栈 .局部变量 yyy, 节点 .局部变量 zzz, 节点 .局部变量 ttt, 节点 .局部变量获取栈的节点信息1, 文本型 .局部变量获取栈的节点信息2, 日期时间型 yyy.加入属性 ("姓名", "张三") yyy.加入属性 (&q
python中栈的原理及实现方法示例

本文实例讲述了python中栈的原理及实现方法.分享给大家供大家参考,具体如下: 栈(stack),有些地方称为堆栈,是一种容器,可存入数据元素.访问元素.删除元素,它的特点在于只能允许在容器的一端(称为栈顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算.没有了位置概念,保证任何时候可以访问.删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序. 由于栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)
C语言实现出栈序列合法性判定

本文实例为大家分享了C语言实现出栈序列合法性判定的具体代码,供大家参考,具体内容如下输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序. 假设压入栈的所有数字均不相等.例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列.(注意:这两个序列的长度是相等的) 输入格式第一行一个整数n,表示输入序列的长度.(1<=n<=10000) 第二行n个整数,表示栈的压入顺

C语言深入探究栈的原理

栈

栈的实现

相关推荐

随机推荐