【数据结构】栈(Stack)的实现 -- 详解

简介: 【数据结构】栈(Stack)的实现 -- 详解

一、栈的概念及结构

1、概念

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


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

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


2、结构


二、栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。如果用尾作栈顶(尾插、尾删),那么要用双向链表更好。如果要用单链表实现,那么就用头去作栈顶更好(头插、头删),这样入栈和出栈的效率都是 O(1)。因为栈只会在一端进行插入和删除操作,用数组效率还是比较高,数组在尾上插入数据的代价比较小。当然,也会存在一些问题,就是每次空间不够,要重新开辟空间,可能会造成一些内存浪费。

双向链表虽然不需要考虑内存大小的问题,但实际上价值并不高,在这里使用单向链表好于双向链表,能节省空间。但是,从各个角度而言, 栈的实现还是选择数组的结构来实现更好一些,不需要增容和释放,空间上更加节省,且CPU 高速缓存命中更高一些。


1、栈的顺序存储结构

数组的首元素作为栈底,另外一端作为栈顶,同时定义一个变量 top 来记录栈顶元素在数组中的位置。


2、栈的链表存储结构

单链表的尾部作为栈底,头部作为栈顶,方便插入和删除(进栈头插,出栈头删),头指针和栈顶指针 top 合二为一。


三、栈的实现

1、创建文件

  • test.c(主函数、测试栈各个接口功能)
  • Stack.c(栈接口函数的实现)
  • Stack.h(栈的类型定义、接口函数声明、引用的头文件)

2、Stack.h 头文件代码

下面是动态增长的栈的结构,在实际中更常用。

#pragma once
#include <stdio.h>
#include <assert.h> // assert
#include <stdlib.h> // realloc
#include <stdbool.h> // bool
 
// 支持动态增长的栈
typedef int STDataType; // 类型重命名 栈中元素类型先假设为int
 
typedef struct Stack
{
    STDataType* a; // 指向动态开辟的数组
    int top; // 记录栈顶位置
    int capacity; // 栈的容量大小
}Stack;
 
// 初始化栈
void StackInit(Stack* ps); 
// 销毁栈
void StackDestroy(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data); 
// 出栈
void StackPop(Stack* ps); 
// 获取栈顶元素
STDataType StackTop(Stack* ps); 
// 获取栈中有效元素个数
int StackSize(Stack* ps); 
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps); 

四、Stack.c 中各个接口函数的实现

1、栈的初始化

// 初始化栈
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = NULL;
    
    //思路一:
  ps->top = 0; // 意味着top指向栈顶数据的下一个
 
    //思路二:
    //ps->top = -1; // 意味着top指向栈顶数据
    
  ps->capacity = 0;
}

思路二:


2、栈的销毁

// 销毁栈
void StackDestroy(Stack* ps)
{
  assert(ps);
  if (ps->a)
  {
    free(ps->a);
  }
    ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}

3、入栈

// 入栈
void StackPush(Stack* ps, STDataType x)
{
  assert(ps);
 
  if (ps->top == ps->capacity) // 检查栈空间是否满了
  {
    int newCapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2;
    STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity); // 扩容至新容量
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity; // 更新容量
  }
  ps->a[ps->top] = x; // 将新增元素放入栈顶空间
  ps->top++; // 栈顶指针加一
}

4、出栈

// 出栈
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps)); // 栈不能为空
  ps->top--; // 栈顶指针减一
}

5、获取栈顶元素

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
  assert(ps);
    assert(!StackEmpty(ps)); // 栈不能为空
  return ps->a[ps->top-1];
}

6、获取栈中有效元素个数

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

7、检测栈是否为空

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool StackEmpty(Stack* ps)
{
  assert(ps);
 
    //写法一:
    /*if (ps->top == 0)
  {
    return true;
  }
  else
  {
    return false;
  }*/
 
    //写法二:
  return ps->top == 0;
}

五、代码整合

// Stack.c
#include "Stack.h"
 
// 初始化栈
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0; // 意味着top指向栈顶数据的下一个
  ps->capacity = 0;
}
 
// 销毁栈
void StackDestroy(Stack* ps)
{
  assert(ps);
  if (ps->a)
  {
    free(ps->a);
  }
    ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
 
// 入栈
void StackPush(Stack* ps, STDataType x)
{
  assert(ps);
 
  if (ps->top == ps->capacity) // 检查栈空间是否满了
  {
    int newCapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2;
    STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity); //扩容至新容量
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity; // 更新容量
  }
  ps->a[ps->top] = x; // 将新增元素放入栈顶空间
  ps->top++; // 栈顶指针加一
}
 
// 出栈
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps)); // 栈不能为空
  ps->top--; // 栈顶指针减一
}
 
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
  assert(ps);
    assert(!StackEmpty(ps)); // 栈不能为空
  return ps->a[ps->top-1];
}
 
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
 
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}

六、测试栈的功能

栈的实现不能像顺序表一样,去实现一个打印函数来遍历栈并输出,这样做就不符合栈的特点了(只能在栈顶插入删除,后进先出),所以我们这样来实现出栈:获取并打印栈顶元素,再删除栈顶元素,继续获取新的栈顶元素。


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