数据结构——栈

简介: 数据结构——栈

什么是栈

栈是一种特殊的线性结构,对数据增加及其删除只能在一端进行操作。

进行数据删除及增加的一端为栈顶,另一端为栈底。

增加数据为压栈。删除数据为出栈。

创建类型

typedef int StackTypeDate;
typedef struct stack
{
  StackTypeDate* arr;
  int top;
  int capacity;
}Stack;

初始栈

void InitStack(Stack* ps)
{
  assert(ps);
  ps->arr = NULL;
  ps->top = ps->capacity = 0;
}

压栈

压栈的时候要察看栈是不是满了,以及它为空的情况。

void StackPush(Stack* ps, StackTypeDate x)
{
  assert(ps);

  if (ps->capacity == ps->top)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    ps->arr = (StackTypeDate*)realloc(ps->arr,sizeof(StackTypeDate) * newcapacity);
    ps->capacity = newcapacity;
  }

  ps->arr[ps->top] = x;
  ps->top++;
}

出栈

void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}

察看栈顶的元素

StackTypeDate StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  //注意这里的减一
  return ps->arr[ps->top-1];
}

栈的个数

int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}

栈是否为空

bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->capacity == 0;
}

栈的销毁

void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->arr);
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}
相关文章
|
16天前
|
存储 Java 容器
深入浅出 栈和队列(附加循环队列、双端队列)
深入浅出 栈和队列(附加循环队列、双端队列)
|
2天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
11 3
|
10天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现(两个方式实现)
【数据结构】栈和队列的模拟实现(两个方式实现)
|
2天前
数据结构初阶 栈
数据结构初阶 栈
7 1
|
7天前
|
算法
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
11 0
|
7天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
14 2
|
7天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
13 0
|
7天前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
9 0
|
7天前
|
算法
数据结构和算法学习记录——特殊线性表之栈(上)-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数
数据结构和算法学习记录——特殊线性表之栈(上)-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数
4 0
|
7天前
|
存储 机器学习/深度学习 算法
数据结构和算法学习记录——空间复杂度的计算(冒泡排序、阶乘递归、斐波那契数列递归、常见复杂度对比、栈帧、栈溢出)
数据结构和算法学习记录——空间复杂度的计算(冒泡排序、阶乘递归、斐波那契数列递归、常见复杂度对比、栈帧、栈溢出)
6 0