数据结构从入门到精通——栈

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


前言

栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。

在现代软件开发中,栈的概念被广泛应用在内存管理、并发控制等多个领域。以内存管理为例,每个线程都有自己的栈空间,用于存储局部变量和函数调用信息。这种隔离保证了线程之间的数据安全,避免了数据混乱和意外覆盖。

同样,在并发控制中,栈也发挥着不可替代的作用。通过维护一个任务栈,系统可以合理地调度和分配计算资源,确保任务按照特定的顺序执行,从而避免了并发访问导致的数据不一致问题。

不仅如此,栈的思想还可以被借鉴到生活的方方面面。想象一下,如果我们将日常生活比作一个栈,那么每一天的生活就是一个新的元素被推入栈中。而当我们结束一天的生活,这个元素就会被从栈中弹出,成为我们宝贵的回忆。这种后进先出的特性使得我们能够更好地珍惜当下,因为每一个现在都会成为过去,而每一个过去都是无法替代的。

在这个意义上,栈不仅仅是一种数据结构,更是一种生活态度。它提醒我们珍惜每一个当下,因为每一个现在都会成为我们未来回忆的一部分。同时,它也告诉我们,在面对困难和挑战时,要敢于迎难而上,因为只有这样,我们才能不断成长和进步。


一、栈

1.1栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

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

出栈:栈的删除操作叫做出栈。出数据也在栈顶。
数据结构从入门到精通——栈,数据结构从入门到精通,数据结构,性能优化,算法,c语言,链表,leetcode,柔性数组
Push是入栈

Pop是出栈
数据结构从入门到精通——栈,数据结构从入门到精通,数据结构,性能优化,算法,c语言,链表,leetcode,柔性数组

1.2栈的实现

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

数据结构从入门到精通——栈,数据结构从入门到精通,数据结构,性能优化,算法,c语言,链表,leetcode,柔性数组

数据结构从入门到精通——栈,数据结构从入门到精通,数据结构,性能优化,算法,c语言,链表,leetcode,柔性数组

// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;
 
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
 STDataType* _a;
 int _top; // 栈顶
 int _capacity; // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps); 
// 入栈 
void StackPush(Stack* ps, STDataType data); 
// 出栈 
void StackPop(Stack* ps); 
// 获取栈顶元素 
STDataType StackTop(Stack* ps); 
// 获取栈中有效元素个数 
int StackSize(Stack* ps); 
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps); 
// 销毁栈 
void StackDestroy(Stack* ps); 

1.3栈的面试题

  1. 括号匹配问题

  2. 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是( )。
    A. 12345ABCDE
    B. EDCBA54321
    C. ABCDE12345
    D. 54321EDCBA

  3. 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
    A 1,4,3,2
    B 2,3,4,1
    C 3,1,4,2
    D 3,4,2,1

答案:B C

二、栈的具体实现代码

栈的初始化

void STInit(ST* ps);//栈的初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;//或者ps->top = -1;具体区别在于先++还是后++
}

栈的初始化是数据结构中栈操作的第一步,它涉及为栈分配内存空间并设置其初始状态。栈是一种后进先出(LIFO)的数据结构,这意味着最后一个被放入栈中的元素将是第一个被取出的元素。

在进行栈的初始化时,我们需要考虑几个关键步骤。首先,我们需要为栈定义一个合适的数据结构,这通常是一个数组或链表。数组实现的栈在内存中使用连续空间,而链表实现的栈则更为灵活,但可能会占用更多的内存。

接下来,我们需要为栈分配内存空间。对于数组实现的栈,这通常意味着创建一个固定大小的数组来存储栈元素。对于链表实现的栈,我们需要创建一个空的链表节点作为栈顶。

在分配了内存空间之后,我们需要设置栈的初始状态。这通常意味着将栈顶指针或引用设置为一个表示栈为空的状态。对于数组实现的栈,这通常是数组的第一个位置或最后一个位置的索引。对于链表实现的栈,这通常是一个指向空链表节点的指针。

完成栈的初始化后,我们就可以开始执行栈的基本操作,如入栈(push)、出栈(pop)、查看栈顶元素(top)以及判断栈是否为空(is_empty)等。这些操作需要确保遵循栈的后进先出原则。

栈的销毁

void STDestroy(ST* ps);//栈的销毁
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

栈的销毁是栈生命周期中的最后一个阶段,它标志着栈内所有数据元素的释放和栈结构本身的解除。在进行栈的销毁之前,必须确保栈中没有任何数据元素,否则可能会导致数据丢失或内存泄漏。

栈的销毁过程通常包括以下几个步骤:

首先,需要遍历栈内的所有元素,并将它们逐一释放。这通常涉及到调用每个元素的析构函数(如果是C++等支持面向对象编程的语言)或相应的清理函数(如果是C等过程式编程语言),以确保每个元素在被销毁前能够正确地完成其生命周期内的所有任务,如关闭文件、释放内存等。

其次,需要销毁栈本身的数据结构。这通常意味着释放栈所占用的内存空间。在大多数编程语言中,这可以通过调用类似于free(C语言)或delete(C++)这样的内存管理函数来完成。一旦栈的数据结构被销毁,它就不再是一个有效的栈,不能再执行入栈、出栈等操作。

最后,为了确保栈确实已经被销毁,可以在销毁后进行一些检查操作。例如,可以尝试对栈执行一些操作,如入栈或出栈,并检查是否会引发错误或异常。如果程序能够正确地检测到栈已经被销毁,并采取相应的错误处理措施,那么这就可以作为栈销毁过程完成的一个标志。

总的来说,栈的销毁是一个非常重要的过程,它确保了栈在不再需要时能够正确地释放其占用的资源,防止了内存泄漏和其他潜在的资源管理问题。同时,通过销毁栈,也可以为其他需要使用这些资源的操作提供空间,从而提高了整个程序的效率和可靠性。

入栈

//入栈
void STPush(ST* ps,STDatatype x);
void STPush(ST* ps,STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDatatype* p = (STDatatype*)realloc(ps->a, sizeof(STDatatype)*newcapacity);
		if (p == NULL)
		{
			perror("p malloc : ");
			return 0;
		}
		ps->a = p;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

“入栈”(Push)是栈(Stack)这种数据结构中的一个基本操作。栈是一种遵循后进先出(Last In First Out,简称LIFO)原则的数据结构,意味着最后放入栈中的元素将会是第一个被取出的。

“入栈”操作的具体含义是:

  1. 添加元素:将一个元素添加到栈的顶部。
  2. 栈顶变化:由于新元素被添加到栈顶,所以栈顶指针或引用会更新,指向这个新添加的元素。
  3. 栈大小变化:栈的大小(或容量)会增加,因为多了一个元素。

例如,假设我们有一个空的栈,并且按照以下顺序执行入栈操作:

  1. 入栈 A
  2. 入栈 B
  3. 入栈 C

那么,栈的当前状态将是 C 在顶部,B 在中间,A 在底部。如果我们现在执行出栈(Pop)操作,C 将被取出,接着是 B,最后是 A。

在实际应用中,栈常用于保存函数调用过程中的局部变量、参数和返回地址,实现递归调用,以及进行深度优先搜索等。

入栈,是每一个数据处理流程中不可或缺的一环。在信息技术的世界里,数据就如同图书馆的藏书,需要有序地存放和取用。而栈,便是这个数字世界中的一个小巧精致的藏书阁,它遵循着后进先出(LIFO)的规则,每一份数据都像是一本书,被轻轻放在栈顶,等待着被取用或者再次被存放。

每当有新的数据需要处理时,它就会被推入栈中。这个过程就像是图书馆里新到了一本畅销书,图书管理员会将它放在最显眼的位置,供读者最先取阅。同样,栈顶的数据也是最先被处理的,因为它是最后进栈的。这种有序的处理方式,保证了数据处理的效率和准确性。

然而,栈并非万能的。它的规则简单而明确,但也因此有局限性。有时候,我们需要按照不同的顺序来处理数据,这时候就需要使用到队列等其他数据结构。但无论如何,栈都是数据处理中不可或缺的一部分。

在软件开发的世界里,栈的作用更是举足轻重。函数调用、递归算法、异常处理等,都离不开栈的支持。每当一个函数被调用时,它的相关信息就会被压入调用栈中,等待函数执行完毕后弹出。这使得程序能够准确地跟踪函数的执行顺序,保证程序的正确运行。

同时,栈也是内存管理的重要手段。在编程中,我们经常需要动态地分配和释放内存。而栈就是内存分配的一种方式。它会自动管理分配给每个函数的内存空间,当函数执行完毕后,这些内存空间就会被自动释放,避免了内存泄漏等问题的发生。

总的来说,入栈是数据处理和程序运行中的关键步骤。它保证了数据的有序性和程序的正确性,是信息技术世界中不可或缺的一环。在未来的技术发展中,栈的作用将更加重要,我们也需要更加深入地理解和应用它。

出栈

//出栈
void STPop(ST* ps);
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

当元素从栈的顶部被移除时,这个过程被称为“出栈”。栈是一种遵循后进先出(LIFO)原则的数据结构,其中新元素总是被添加到栈顶,而只有栈顶的元素可以被移除。出栈操作会减少栈的大小,并返回被移除的元素。如果栈为空,则无法进行出栈操作。

返回栈顶元素

STDatatype STTop(ST* ps);//返回栈顶元素
STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

返回栈中的元素个数

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

检测是否为空

注意:在使用VS2022编译器编译C语言需要用到布尔类型的时候,需要添加头文件#include <stdbool.h>,添加了这个头文件才能使用布尔类型文章来源地址https://www.toymoban.com/news/detail-838361.html

bool STEmpty(ST* ps);//检测是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁

//入栈
void STPush(ST* ps,STDatatype x);
//出栈
void STPop(ST* ps);
STDatatype STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中的元素个数
bool STEmpty(ST* ps);//检测是否为空

Stack.c

#include "Stack.h"

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;//或者ps->top = -1;具体区别在于先++还是后++
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void STPush(ST* ps,STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDatatype* p = (STDatatype*)realloc(ps->a, sizeof(STDatatype)*newcapacity);
		if (p == NULL)
		{
			perror("p malloc : ");
			return 0;
		}
		ps->a = p;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

test.c

#include"Stack.h"

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);

	int top = STTop(&s);
	printf("%d ", top);
	STPop(&s);

	STPush(&s, 4);
	STPush(&s, 5);

	while (!STEmpty(&s))
	{
		int top = STTop(&s);
		printf("%d ", top);
		STPop(&s);
	}

	STDestroy(&s);

	return 0;
}

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

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

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

相关文章

  • 数据结构从入门到精通——堆排序

    堆排序是一种利用堆数据结构实现的排序算法。首先,它将待排序的数组构建成一个大顶堆或小顶堆。然后,通过不断将堆顶元素(最大或最小)与末尾元素交换并重新调整堆,使得数组逐渐有序。最后,当堆的大小减至1时,排序完成。堆排序的时间复杂度为O(nlogn),空间复

    2024年04月09日
    浏览(50)
  • 数据结构从入门到精通——冒泡排序

    冒泡排序是一种简单的排序算法,通过重复遍历待排序数列,比较相邻元素的大小并交换位置,使得每一轮遍历后最大(或最小)的元素都会“冒泡”到数列的一端,直到整个数列有序。这种算法的时间复杂度较高,但在处理小规模数据或近乎有序的数据时表现良好,除此之

    2024年04月16日
    浏览(38)
  • 数据结构从入门到精通——直接插入排序

    直接插入排序是一种简单的排序算法,其工作原理是逐个将待排序元素插入到已排序序列中的适当位置,直到全部元素排序完毕。算法从第二个元素开始,将其与前面的元素进行比较,如果当前元素小于前一个元素,则将其插入到前一个元素之前,否则继续向前比较。重复此

    2024年03月21日
    浏览(50)
  • 数据结构从入门到精通——树和二叉树

    树和二叉树是计算机科学中常用的数据结构,它们在数据存储、搜索、排序等多个领域都有着广泛的应用。从简单的二叉树出发,我们可以逐步理解更复杂的树结构,如红黑树、AVL树等。 二叉树是一种每个节点最多有两个子节点的树结构,通常子节点被称为“左子节点”和“

    2024年03月15日
    浏览(101)
  • 数据结构从入门到精通——排序的概念及运用

    排序是将数据按照一定规则重新排列的过程,常见规则有升序、降序等。排序算法如冒泡排序、快速排序等,广泛用于数据库、搜索引擎等场景,提高数据检索效率。此外,排序也应用于统计分析、机器学习等领域,以获取有序数据集或发现数据间的关联。 排序是一种将一组

    2024年03月21日
    浏览(40)
  • LwIP 之七 详解 PBUF 结构、通信数据流、性能优化

      数据包的复制在协议栈中是非常耗时的一个操作。LwIP 协议栈内部使用 pbuf 这种数据结构来对数据进行传递,灵活的 pbuf 结构体使得数据在不同网络层之间传递时可以减少内存的开销,避免频繁的内存复制,增加数据在不同层之间传递的速度。   Packet buffers 简称 pbuf,

    2024年02月15日
    浏览(114)
  • Redis从入门到精通【高阶篇】之底层数据结构跳表(SkipList)

    上个篇章回顾,我们上个章节我们学习了《Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解》,我们从源码层了解整数集由一个头部和多个数据块组成。头部中存储了整数集的元素个数、编码方式和数据块的起始地址等信息。数据块中存储了实际的整型数据,当

    2024年02月09日
    浏览(49)
  • Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解

    上个篇章回顾,我们上个章节,讲了Redis中的快表(QuickList),它是一种特殊的数据结构,用于存储一系列的连续节点,每个节点可以是一个整数或一个字节数组。快表是Redis中的底层数据结构之一,常用于存储有序集合(Sorted Set)等数据类型的底层实现。 那么本章讲解Red

    2024年02月09日
    浏览(50)
  • Redis从入门到精通【高阶篇】之底层数据结构压缩列表(ZipList)详解

    前面的Redis从入门到精通的基础篇和进阶篇都是在使用层面和概念层面,本章节,我们了解一下redis的底层数据结构,上几个章节,我们讲了SDS,字典 。本章节我们聊一下ZipList。 压缩列表(ZipList)就是redis为了节约内存而设计开发的数据结构,并且作为列表键和哈希键的底层

    2024年02月08日
    浏览(91)
  • Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解

    上个篇章回顾,我们上个章节我们学习了《Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解》,我们从源码层了解字典是一种以键值对(key-value)形式存储数据的数据结构。在 Redis 中,字典使用哈希表来实现。哈希表是一种以常数时间复杂度 O(1) 进行插入、删

    2024年02月09日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包