【栈】基于顺序表的栈功能实现

简介: 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

1 栈是什么

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

称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

1.1 基本功能

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

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

栈可以形象得想象成一个高高的箱子,只能从上面放入与拿出。

1.2 为什么选择“顺序表”为基础

根据对顺序表的了解 ,顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。这样操作简单快速就可以实现“栈”的功能。

因为“栈”只能在栈顶进行操作,如果使用链表就需要频繁找尾,导致时间复杂度较高

而使用顺序表,通过“size”变量的使用可以快速找到尾部,更加方便。

2 功能实现

这是“栈”的功能概况,下面予以实现:

2.1 初始化与销毁

//初始化
void StackInit(Stack* ps) {

  assert(ps);
  ps->a = NULL;
  //栈顶元素的下一个元素
  ps->top = 0;
  ps->capacity = 0;
}
//销毁
void StackDestroy(Stack* ps) {
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}

与顺序表一致,多加了一个"top"变量的初始化。

top : 记录栈顶位置。 (与顺序表的“size”本质相同)

2.2 入栈与出栈

//入栈
void StackPush(Stack* ps, STDataType data) {
  assert(ps);
  //容量检查
  if (ps->top == ps->capacity) 
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
      STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);

      if (tmp == NULL) {
       perror("relloc failed");
       exit(-1);
      }

    ps->a = tmp;
      ps->capacity = newcapacity;
  }
  

  
  ps->a[ps->top] = data;
  ps->top++;

}

与顺序表的尾插功能一致。进行容量检查之后,就可以在尾部进行插入,并将“top”++。

//出栈
void StackPop(Stack* ps) {
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}

出栈的功能更加简单,将“top”–即可。

2.3 获取栈顶元素与获取有效元素个数

//获取栈顶元素
STDataType StackTop(Stack* ps) {
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top-1];
}

返回“top”前一个即可。

//获取栈中有效元素个数
int StackSize(Stack* ps) {
  assert(ps);
  return ps->top;
}

返回“top”就好。

2.4 检查是否为空

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

判断"top"是否等于初始值即可。

3 总结

栈可以用来快速解决一些特殊化问题,它独特的性质值得我们学习使用。

Thanks♪(・ω・)ノ

相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
131 9
|
23天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
11天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
29 5
|
26天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
29天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
49 4
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
38 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
数据结构(栈与列队)
数据结构(栈与列队)
22 1