【数据结构】线性表(六)堆栈:顺序栈及其基本操作(初始化、判空、判满、入栈、出栈、存取栈顶元素、清空栈)

本文主要是介绍【数据结构】线性表(六)堆栈:顺序栈及其基本操作(初始化、判空、判满、入栈、出栈、存取栈顶元素、清空栈),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、堆栈
    • 1. 定义
    • 2. 基本操作
  • 二、顺序栈
    • 0. 顺序表
    • 1. 头文件和常量
    • 2. 栈结构体
    • 3. 栈的初始化
    • 4. 判断栈是否为空
    • 5. 判断栈是否已满
    • 6. 入栈
    • 7. 出栈
    • 8. 查看栈顶元素
    • 9. 清空栈
    • 10. 主函数
    • 11. 代码整合

  堆栈Stack 和 队列Queue是两种非常重要的数据结构,两者都是特殊的线性表:

  • 对于堆栈,所有的插入和删除(以至几乎所有的存取)都是在表的同一端进行
  • 对于队列,所有的插入都是在表的一端进行,所有的删除(以至几乎所有的存取)都是在表的另一端进行。

一、堆栈

1. 定义

  堆栈(简称)是一种操作受限的线性表,只允许在表的同一端进行插入和删除操作,且这些操作是按后进先出的原则进行的。进行插入和删除的一端被称为栈顶,另一端被称为栈底。当栈中无元素时称其为空栈。根据上述定义,每次删除(退栈)的总是最后插入(进栈)的元素。

堆栈示意图
  如图所示的堆栈中,诸元素以a1,a2,a3,a4,a5的顺序进栈,而退栈的次序则是a5,a4,a3,a2,a1。 也就是说,从栈中取走元素是按后进先出的原则进行的,因此栈又被称作后进先出(Last in First Out)的线性表,简称为LIFO表

2. 基本操作

  • 堆栈是受限的线性表,其基本操作包括
    • push ( ) : 压入一个元素(插入);
    • pop ( ) : 弹出一个元素(删除);
    • peek ( ) : 存取栈顶元素值;
    • clear ( ) : 清空栈;
    • IsEmpty ( ) : 判断栈是否为空;
  • 同普通线性表一样,堆栈也可以用顺序存储和链接存储两种方式来实现:

二、顺序栈

  用顺序存储方式实现的堆栈称为顺序栈

  • 顺序栈用数组存放栈元素,可方便地进行各种栈操作;
  • 某一堆栈的规模指该堆栈最多能容纳的元素个数;
  • 存放堆栈的数组规模(或大小)应按堆栈的规模来确定:
    • 当堆栈中元素的个数达到堆栈规模(简称为栈满)时,则无法再向堆栈插入元素,换言之此时的插入操作将产生上溢出。
  • 如何确保既不上溢也不下溢?
    • 需要一个整型变量size来存放数组规模,以及一个整型变量top来存放栈顶元素在数组中的位置(下标)
      • 当栈为空时,top值为0
      • 每入栈(或出栈)一个元素,top值加1(或减1)
      • 当top等于size时,说明栈满

0. 顺序表

参考前文:顺序表及其基本操作

1. 头文件和常量

   #include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100
  • 两个头文件
    • stdio.h用于输入输出操作
    • stdlib.h用于内存分配和释放
  • 通过#define指令定义了一个常量MAX_SIZE,它表示栈的最大容量为100

2. 栈结构体

   typedef struct {int data[MAX_SIZE];int top;} Stack;

  使用结构体定义了一个栈的数据结构,data是一个整型数组,用于存储栈中的元素,top表示栈顶的索引。

3. 栈的初始化

   void init(Stack* stack) {stack->top = -1;}

  初始化栈,将栈顶索引top置为-1,表示栈为空。

4. 判断栈是否为空

   int isEmpty(Stack* stack) {return stack->top == -1;}

  判断栈是否为空,如果栈顶索引top等于-1,表示栈为空,函数返回1;否则,返回0。

5. 判断栈是否已满

   int isFull(Stack* stack) {return stack->top == MAX_SIZE - 1;}

  isFull函数用于判断栈是否已满,如果栈顶索引top等于MAX_SIZE - 1,表示栈已满,函数返回1;否则,返回0。

6. 入栈

   void push(Stack* stack, int value) {if (isFull(stack)) {printf("Stack is full. Cannot push element.\n");return;}stack->data[++stack->top] = value;}

  push函数用于将元素入栈,首先判断栈是否已满,如果已满,则打印错误信息并返回;否则,将元素存储在栈顶索引top的位置,并将栈顶索引加1。

7. 出栈

   int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty. Cannot pop element.\n");return -1;}return stack->data[stack->top--];}

  pop函数用于将栈顶元素出栈,首先判断栈是否为空,如果为空,则打印错误信息并返回-1;否则,返回栈顶元素的值,并将栈顶索引减1。

8. 查看栈顶元素

   int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty. Cannot peek element.\n");return -1;}return stack->data[stack->top];}

  peek函数用于查看栈顶元素的值,首先判断栈是否为空,如果为空,则打印错误信息并返回-1;否则,返回栈顶元素的值。

9. 清空栈

   void clear(Stack* stack) {stack->top = -1;}

  clear函数用于清空栈,将栈顶索引top置为-1,表示栈为空。

10. 主函数

int main() {Stack stack;init(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printf("Top element: %d\n", peek(&stack));printf("Popped element: %d\n", pop(&stack));printf("Popped element: %d\n", pop(&stack));printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");clear(&stack);printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");return 0;
}
  • 声明一个Stack类型的变量stack,然后调用init函数对栈进行初始化。

  • 使用push函数将元素10、20和30依次入栈。

  • 使用peek函数查看栈顶元素的值。

  • 使用pop函数将栈顶的两个元素出栈。

  • 使用isEmpty函数判断栈是否为空。

  • 调用clear函数清空栈。

  • 再次使用isEmpty函数判断栈是否为空。

在这里插入图片描述

11. 代码整合

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;
} Stack;void init(Stack* stack) {stack->top = -1;
}int isEmpty(Stack* stack) {return stack->top == -1;
}int isFull(Stack* stack) {return stack->top == MAX_SIZE - 1;
}void push(Stack* stack, int value) {if (isFull(stack)) {printf("Stack is full. Cannot push element.\n");return;}stack->data[++stack->top] = value;
}int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty. Cannot pop element.\n");return -1;}return stack->data[stack->top--];
}int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty. Cannot peek element.\n");return -1;}return stack->data[stack->top];
}void clear(Stack* stack) {stack->top = -1;
}int main() {Stack stack;init(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printf("Top element: %d\n", peek(&stack));printf("Popped element: %d\n", pop(&stack));printf("Popped element: %d\n", pop(&stack));printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");clear(&stack);printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");return 0;
}

这篇关于【数据结构】线性表(六)堆栈:顺序栈及其基本操作(初始化、判空、判满、入栈、出栈、存取栈顶元素、清空栈)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/247553

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Spring组件初始化扩展点BeanPostProcessor的作用详解

《Spring组件初始化扩展点BeanPostProcessor的作用详解》本文通过实战案例和常见应用场景详细介绍了BeanPostProcessor的使用,并强调了其在Spring扩展中的重要性,感... 目录一、概述二、BeanPostProcessor的作用三、核心方法解析1、postProcessB

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要