C++数据结构学习——栈

这篇具有很好参考价值的文章主要介绍了C++数据结构学习——栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言

栈(Stack)是计算机科学中一种常见的数据结构,它是一种线性数据结构,具有特定的添加和删除元素的方式,遵循"先进后出"(Last In, First Out,LIFO)原则。栈通常用于管理函数调用、表达式求值、内存管理等多个计算机科学领域。


提示:以下是本篇文章正文内容,下面案例可供参考

一、栈

栈是一种特殊的线性表,只允许在固定的一端进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守**先进后出LIFO(Last In First Out)**的原则。
压栈:栈的插入操作叫做进行入栈、进栈、压栈,入数据在栈顶;
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
C++数据结构学习——栈,数据结构,c++,学习栈的实现一般可以使用数组或者链表,相对而言数组的结构实现更优一些,因为数组在尾上插数据的代价比较小。

二、C语言实现

1.声明代码

代码如下(示例):

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int STDatatype;
// 数组栈,数组尾部为栈顶,数组头为栈底

typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;
}ST;

void StackInit(ST* ps); //初始化栈
void StackDestroy(ST* ps); // 销毁栈
void StackPush(ST* ps, STDatatype x); //入栈
void StackPop(ST* ps); //出栈
STDatatype StackTop(ST* ps); //获取栈顶元素 

bool StackEmpty(ST* ps); // 判断栈是否为空
int StackSize(ST* ps); //栈中元素个数

2.实现增删查改代码

代码如下(示例):

#include "Stack.h"

void StackInit(ST* ps)
{
	assert(ps); //断言检查
	ps->a = (ST*)malloc(sizeof(ST) * 4); //开辟空间
	if (ps->a == NULL) //空间申请失败
	{
		perror("malloc fail....");
		exit(-1);
	}
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps); //释放空间
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackPush(ST* ps, STDatatype x) //入栈
{
	assert(ps);
	if (ps->top+1 == ps->capacity) // 如果空间已经满了
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype)); //扩容
		if (ps->a == NULL)
		{
			perror("malloc fail...");
			exit(-1);
		}
		ps->a = tmp; //ps要指向新开辟的空间tmp
		ps->capacity *= 2; // ps的容量变为原来的2倍
	}
	ps->top++;
	ps->a[ps->top] = x;
}

void StackPop(ST* ps) //出栈
{
	assert(ps);
	ps->top--; //指针前移
}

STDatatype StackTop(ST* ps) //获取栈顶元素
{
	assert(ps);
	assert(!StackEmpty(ps)); //断言栈不为空

	return ps->a[ps->top-1]; //注意:栈顶元素为top的前一个元素
}

bool StackEmpty(ST* ps) // 判断栈是否为空
{
	assert(ps);

	if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int StackSize(ST* ps) //栈中元素个数
{
	assert(ps);
	
	return ps->top; //top为最后一个数据的下一个位置
}

3.测试代码

代码如下(示例):

#include "Stack.h"

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

void Stack_Test1()
{
	ST st;
	StackInit(&st); //初始化结构体,要把结构体的地址传过去
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	int size = StackSize(&st);
	printf("st's size:%d", size);

	StackDestroy(&st);

}

int main()
{
	Stack_Test1();
	return 0;
}

总结

栈适用于需要后进先出操作的情况,例如函数调用和操作历史记录。文章来源地址https://www.toymoban.com/news/detail-676759.html

到了这里,关于C++数据结构学习——栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 数据结构

    C/C++ 数组允许定义可存储相同类型数据项的变量,但是结构是 C++ 中另一种用户自定义的可用的数据类型,它允许您存储不同类型的数据项。 结构用于表示一条记录,假设您想要跟踪图书馆中书本的动态,您可能需要跟踪每本书的下列属性: Title :标题 Author :作者 Subject :

    2024年01月21日
    浏览(54)
  • c++基础数据结构

    基础数据结构 目录 • 线性结构 • 二叉堆 • 并查集 • 哈希表 • 应用举例 一、线性结构 基础知识 • 数组 • 带头结点的双链表 – He a d 结点 : 虚拟头结点 – Fir s t 结点 : 第一个有实际内容的结点 • 队列 : 循环队列与 Open-Close 表 例 1. 最小值 • 实现一个 n 个元素的线性

    2024年02月10日
    浏览(37)
  • c++基本数据结构

    线性表可以用普通的一维数组存储。 你可以让线性表可以完成以下操作(代码实现很简单,这里不再赘述): 返回元素个数。 判断线性表是否为空。 得到位置为 p 的元素。 查找某个元素。 插入、删除某个元素:务必谨慎使用,因为它们涉及大量元素的移动。 (1) 单链表:

    2023年04月14日
    浏览(28)
  • 数据结构——栈(C++实现)

    今天我们来看一个新的数据结构—— 栈 。 栈是一种基础且重要的数据结构,它在计算机科学和编程中扮演着核心角色。栈的名称源于现实生活中的概念,如一叠书或一摞盘子,新添加的物品总是放在顶部,而取出物品时也总是从顶部开始。这种后进先出(Last In, First Out, L

    2024年04月29日
    浏览(42)
  • 数据结构——队列(C++实现)

    目录 队列的概念及结构  队列的实现 队列的代码实现 完整的源文件代码 总结 推荐题目巩固知识 队列:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,队列最重要的特性是 先进先出 (First In First Out) 入队列:进行插入操作的一端称为 队尾 出队列

    2024年02月07日
    浏览(40)
  • C++:【数据结构】哈希表

    哈希表(hash table)又叫散列表,是一种很实用的数据结构。首先来看一下百度给出的定义:散列表,是 根据关键码值(Key value)而直接进行访问的数据结构 。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放

    2024年02月03日
    浏览(52)
  • c++【数据结构】 八大排序

    在计算机科学中,排序算法是最重要的算法之一。排序算法可以将一组无序的数据按照一定的规则重新排列,使其变为有序的数据集合。排序算法的应用十分广泛,它们在计算机科学、数据结构、数据库、人工智能、机器学习等领域都扮演着重要的角色。 本文将介绍C++/C语言

    2024年02月10日
    浏览(46)
  • C++数据结构--红黑树

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。如图所示: 每个结点不是红色就是黑色。

    2024年02月09日
    浏览(46)
  • 数据结构-B树的特点结构与C++实现

    目录 1. 引言 2. 什么是B树 3. B树的特点 3.1 平衡性 3.2 多路搜索树 3.3 高度平衡 4. B树的应用场景 4.1 文件系统 4.2 数据库系统 4.3 索引结构 5. B树的基本操作 5.1 插入操作 5.2 删除操作 5.3 查找操作 6. B树与其他数据结构的比较 6.1 B树与二叉搜索树 6.2 B树与红黑树 7. C++代码实现 8.

    2024年02月09日
    浏览(44)
  • C++数据结构之队列详解

    队头填充进四个元素 此时思考一个问题,当删除元素时(元素出队列时)会出现假饱和的情况,如上图m_data[0]和m_data[1]再进行出队列操作之后,这两个位置可以容纳新的元素,但m_rear没有回到原本的m_data[0]位置,因此需要引入一个新的队列结构,环形队列,m_rear这个位置可以

    2024年02月05日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包