数据结构第四课 -----线性表之栈

简介: 数据结构第四课 -----线性表之栈

栈的概念和结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶,另一端称为栈底栈里的元素遵循后进先出的原则

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

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

栈顶的位置是变化的,不是在某一个地方,栈顶是插入数据和删除数据的位置

如果我们要实现栈,有两种方法

  1. 数组栈

使用数组来当作栈,栈底和栈顶的位置没有任何规定,但是我们一般是使用尾部为栈顶,头部为栈底,这样就可以减少数据的移动,空间不够就扩容,


  1. 链式栈

    栈顶和栈底的位置随意,哪边都可以,而我们使用链表一般都是单链表

    还要一个栈的出栈的顺序有多种,不会只有一种
    下面我就以数组栈来写一个栈


栈的设计

栈的创建和初始化

创建

typedef int TackDataType;
typedef struct SLtack
{
  TackDataType* TData;
  TackDataType Top;//标识栈顶位置
  int Capacity;
}SLtack;

初始化

void TackInit(SLtack* pst)
{
  assert(pst);
  pst->TData = NULL;
  pst->Top = 0;//栈顶元素的下一个
  pst->Capacity = 0;
}

这里的top的初始化有两种:

1.top 表示的是栈顶元素,我们要初始化为-1,

2.top表示栈顶元素的下一个 我们要初始化为0

原因:

假设我们初始化为0 且top是表示栈顶元素,就像上面这种情况,我们无法判断top为0时,栈是否还有元素,当我们表示top表示栈顶元素的下一个,top为0,栈就没有元素,或者我们top初始化为-1,top为栈顶元素,即使top为0,那栈还是有元素的

栈的释放

//释放
void TackDestroy(SLtack* pst)
{
  assert(pst);
  free(pst->TData);
  pst->TData = NULL;
  pst->Top = 0;
  pst->Capacity = 0;
}

入栈

void TackcapacityAdd(SLtack* pst)
{
  assert(pst);
  //扩容
  pst->Capacity = (pst->Capacity == 0 ? 4 : pst->Capacity * 2);
  TackDataType* tmp = realloc(pst->TData, sizeof(TackDataType) * pst->Capacity);
  if (tmp == NULL)
  {
    perror("realloc");
    return;
  }
  pst->TData = tmp;
  
}
//插入数据
void TackPushData(SLtack* pst, TackDataType elemest)
{
  assert(pst);
  //判断容量
  if (pst->Capacity == pst->Top)
  {
    TackcapacityAdd(pst);
    printf("扩容成功\n");
    
  }
  assert(pst->Capacity != pst->Top);
  pst->TData[pst->Top] = elemest;
  pst->Top++;
  

}

出栈

//删除数据
void TackPopData(SLtack* pst)
{
  assert(pst);
  if(pst->Top)
    pst->Top--;
}

栈顶

//找出栈顶
TackDataType* TackTop(SLtack* pst)
{
  assert(pst);
  return pst->TData + (pst->Top - 1);
}

栈是否为空

//判断栈是否为空
bool Empty(SLtack* pst)
{
  assert(pst);
  return pst->Top == 0;
}

栈的长度

//栈的长度
int TackSize(SLtack* pst)
{
  assert(pst);
  return pst->Top;
}

第二种方法

这种是把top初始化为-1

typedef char TackDataType;
typedef struct Stack
{
    TackDataType * a;
    int top; //栈顶元素
    int capacity;
}Stack;
//初始化
void TackInit(Stack *pst)
{
    assert(pst);
    pst->a = NULL;
    pst->top = -1;
    pst->capacity = 0;
}
// 入栈
void TackPush(Stack *pst, TackDataType elemest)
{
    assert(pst);
    //判断是否满了
    if ((pst->top) +1 == pst->capacity)
    {
        pst->capacity = (pst->capacity == 0? 4 : pst->capacity * 2);
        TackDataType* tmp = (TackDataType*)realloc(pst->a,sizeof(Stack) * pst->capacity);
        if (tmp == NULL)
        {
            perror("realloc");
            return;
        }
        pst->a = tmp;

    }
    pst->a[++(pst->top)] = elemest;

}
//出栈
void TackPop(Stack *pst)
{
    assert(pst);
    if(pst->top != -1)
        pst->top--;
}
//长度
int TackSize(Stack *pst)
{
    assert(pst);
    return (pst->top) + 1;
}
//是否为空
bool TackEmpty(Stack *pst)
{
    assert(pst);
    return pst->top == -1; 
}
//栈顶元素
TackDataType TackTop(Stack *pst)
{
    assert(pst);
    return pst->a[pst->top];
}
//释放
void TackDestroy(Stack *pst)
{
    free(pst->a);
    pst->a = NULL;
    pst->top = -1;
    pst ->capacity = 0;
}

总结

栈的简单设计就到这里了,如果想要设置链式栈可以动手自己设计,后续会更新相关的代码

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