数据结构——顺序栈与链式栈的实现-1

简介: 数据结构——顺序栈与链式栈的实现

一、概念

1、栈的定义

 栈 是仅限在 表尾 进行 插入 和 删除 的 线性表。

 栈 又被称为 后进先出 (Last In First Out) 的线性表,简称 LIFO 。


2、栈顶

 栈 是一个线性表,我们把允许 插入 和 删除 的一端称为 栈顶。

c4e9151013f1a98ed6d51d0b39c353fc_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1doZXJlSXNIZXJvRnJvbQ==,size_1,color_FFFFFF,t_70#pic_center.png


3、栈底

 和 栈顶 相对,另一端称为 栈底,实际上,栈底的元素我们不需要关心。

37f7fc3f3a30e530415c5499036e08d4_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1doZXJlSXNIZXJvRnJvbQ==,size_1,color_FFFFFF,t_70#pic_center.png


二、接口

1、可写接口

1)数据入栈

 栈的插入操作,叫做 入栈,也可称为 进栈、压栈。如下图所示,代表了三次入栈操作:

image.gif


2)数据出栈

 栈的删除操作,叫做 出栈,也可称为 弹栈。如下图所示,代表了两次出栈操作:

image.gif


3)清空栈

 一直 出栈,直到栈为空,如下图所示:

image.gif


2、只读接口

1)获取栈顶数据

 对于一个栈来说只能获取 栈顶 数据,一般不支持获取 其它数据。


2)获取栈元素个数

 栈元素个数一般用一个额外变量存储,入栈 时加一,出栈 时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 �(1)O(1) 的时间复杂度获取栈元素个数。


3)栈的判空

 当栈元素个数为零时,就是一个空栈,空栈不允许 出栈 操作。


三、栈的基本运算

创建空栈 : CreateStack (len)


清空栈 : ClearStack (S)


判断是否栈空 : EmptyStack (S)


判断是否栈满 : FullStack (S)


元素进栈 : PushStack (S,x)


元素出栈 : PopStack (S)


取栈顶元素 : GetTop (S)


四、顺序栈Sequential Stack)实现

1、数据结构定义

对于顺序表,在 C语言 中表现为 数组,在进行 栈的定义 之前,我们需要考虑以下几个点:

 1)栈数据的存储方式,以及栈数据的数据类型;

 2)栈的大小;

 3)栈顶指针;


  • 我们可以定义一个 栈 的 结构体,C语言实现如下所示:
typedef int datatype;
typedef struct node{     /*定义栈中数据元素的数据类型*/
  datatype *data;      /*用指针指向栈的存储空间*/
  int maxlen;          /*当前栈的最大元素个数*/
  int top;             /*指示栈顶位置(数组下标)的变量*/
}sqstack;                /*顺序栈类型定义*/

2、创建栈

C语言实现如下所示:

sqstack* stack_create(int len)
{
  sqstack *s;
 
  if((s=(sqstack *)malloc(sizeof(sqstack)))==NULL)
  {
    puts("malloc failed");
    return NULL;
  }
  if((s->data=(datatype *)malloc(len*sizeof(datatype)))==NULL)
    
  {
    puts("malloc failed");
    return NULL;
  }
  s->maxlen=len;
  s->top=-1;
 
  return s;
}


3、清空栈

C语言实现如下所示:

void stack_clear(sqstack* s)
{
  s->top = -1;
}

4、判断栈是否为空

C语言实现如下所示:

int stack_empty(sqstack* s)
{
  return (s->top==-1 ? 1:0);
}

5、判断栈是否饱和

C语言实现如下所示:

int stack_full(sqstack* s)
{
  return (s->top==(s->maxlen-1) ? 1:0);
}

6、入栈

C语言实现如下所示:


int stack_push(sqstack* s,datatype value)
{
  if(s->top==s->maxlen-1){
    puts("stack is full");
    return -1;
  }
 
  s->data[s->top+1]=value;
  s->top++;
 
  return 1;
}


数据结构——顺序栈与链式栈的实现-2

https://developer.aliyun.com/article/1507981


相关文章
|
15小时前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
11 5
|
1天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
4天前
|
缓存 调度
栈和队列的区别
栈和队列的区别
7 0
|
5天前
|
算法 Java 编译器
Java数据结构与算法:线性数据结构之栈
Java数据结构与算法:线性数据结构之栈
|
5天前
|
存储 程序员 编译器
堆和栈的区别
堆和栈的区别
|
5天前
|
C++
【洛谷 P1739】表达式括号匹配 题解(栈)
该编程题目要求检查给定的包含字母、运算符和括号的表达式是否括号匹配。输入为一行表达式,以`@`结束。如果括号匹配,输出`YES`,否则输出`NO`。样例包括一个匹配和一个不匹配的表达式。解决方案是使用栈,遇到左括号入栈,遇到右括号时判断栈是否为空,栈空则输出`NO`,否则出栈。当读到`@`时,栈空则输出`YES`,否则输出`NO`。提供的AC代码使用C++实现,通过`stack`处理括号匹配。
7 0
|
5天前
|
存储 Java Python
数据结构===栈
数据结构===栈
|
5天前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解(递归+记忆化搜索)
**NOIP2003普及组栈问题**:给定操作数序列1到n,仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3,输出5。当队列空时返回1,栈空则只能入栈,栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
8 1
|
6天前
|
索引
栈的数组实现
栈的数组实现
5 0
|
7天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
8 1