栈的定义及基本操作实现（顺序栈）

2023-05-23 140

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 栈的定义及基本操作实现（顺序栈）

前言

相信大家小时后一定玩过玩具枪吧，在我们装子弹时玩具枪的子弹只能从弹夹的一端进并且从同一端出来，这种特殊的结构在我们数据结构的世界称为——栈

一.栈是什么？🧐🧐🧐

栈(stack )是限定仅在表尾进行插人或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶(top)，相应地，表头端称为栈底( bttom)。不含元素的空表称为空栈。

假设栈S= (a1,a2,… , an),则称a1为栈底元素，an为栈顶元素。栈中元素按a1, a2, …,an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，因此,栈又称为后进先出( Last In First Out, LIFO) 的线性表。

二、栈与线性表的关系🆚🆚🆚

栈是一种重要的线性结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为具有限定性的数据结构。但从数据类型角度看，它是和线性表不相同的两类重要的抽象数据类型。

三、栈的基本操作🔬🔬🔬

1.栈的储存结构结构💻

typedef  int Elemtype;
typedef struct 
{
  Elemtype* top;//指向栈顶的指针
  Elemtype* base;//指向栈底的指针
  int log;//存储当前栈的最大容量
}snake;

2.栈的初始化✨

void Creat(snake* a)
{
  a->base = (Elemtype*)malloc(sizeof(int) * MAX);//
  if (a == NULL)
  exit(0);
  a->top = a->base;
  a->log = MAX;
}

3. 入栈🚗

void Push(snake* a, Elemtype o)
{
  if (a->top - a->base >= a->log)//如果栈已满则需扩容
  {
  a->base = (Elemtype*)realloc(a->base, sizeof(Elemtype) * (a->log + MAX));//扩充到原来的一倍
  a->top = a->log + MAX;//重新指向未增容前的栈顶
  a->log = a->log + MAX;//记入扩大前的容量
  if (!a->base)
    exit(0);
  }
  *(a->top) =o;//赋值
  a->top++;//指向下一个
}

4.出栈🚅

Elemtype pop(snake* a, Elemtype *e)
{
  if (a->top == a->base)
  return 0;//栈已空
  *e = *--(a->base);//先指向栈的第一个元素，并取出元素
  return *e;//返回
}

5.清空与销毁🆘

void QingKong(snake* a)
{
  a->top = a->base;
  a->log = MAX;
}//清空一个栈，栈本身没有消失
void Destroy(snake* a)
{
  int i, len;
  len = a->log;
  for (i = 0;i < len;i++)
  {
  free(a->base);
  a->base++;
  }
  a->base = a->top = NULL;
  a->log = 0;
}

总结🎆🎆🎆

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常习惯的做法是:以top= 0表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C语言作描述语言时，如此设定会带来很大不便，因此另设指针base指示栈底元素在顺序栈中的位置。当top和base的值相等时，表示空栈。

#include<string.h>
#include<stdlib.h>
#define MAX 100//一次的最大容量
typedef  int Elemtype;
typedef struct 
{
  Elemtype* top;//指向栈顶的指针
  Elemtype* base;//指向栈底的指针
  int log;//存储当前栈的最大容量
}snake;
void Creat(snake* a)
{
  a->base = (Elemtype*)malloc(sizeof(int) * MAX);//
  if (a == NULL)
  exit(0);
  a->top = a->base;
  a->log = MAX;
}
void Push(snake* a, Elemtype o)
{
  if (a->top - a->base >= a->log)//如果栈已满则需扩容
  {
  a->base = (Elemtype*)realloc(a->base, sizeof(Elemtype) * (a->log + MAX));//扩充到原来的一倍
  a->top = a->log + MAX;//重新指向未增容前的栈顶
  a->log = a->log + MAX;//记入扩大前的容量
  if (!a->base)
    exit(0);
  }
  *(a->top) =o;//赋值
  a->top++;//指向下一个
}
Elemtype pop(snake* a, Elemtype *e)
{
  if (a->top == a->base)
  return 0;//栈已空
  *e = *--(a->base);//先指向栈的第一个元素，并取出元素
  return *e;//返回
}
void QingKong(snake* a)
{
  a->top = a->base;
  a->log = MAX;
}//清空一个栈，栈本身没有消失
void Destroy(snake* a)
{
  int i, len;
  len = a->log;
  for (i = 0;i < len;i++)
  {
  free(a->base);
  a->base++;
  }
  a->base = a->top = NULL;
  a->log = 0;
}
int Snakelen(snake* a)
{
  return (a->top - a->top);
}//计算栈的当前容量
int main()
{
  snake* a;//创建栈
  Creat(a);//赋值
  return 0;
}