数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码) |
您所在的位置:网站首页 › 什么是空的数据结构 › 数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码) |
前言:在前面的文章中,我们讲解了顺序表,单链表,双向链表。而我们今天要分享的栈则是基于之前的数据结构上搭建的,但是相较于顺序表和链表来说,栈的实现就非常简单了。 目录 一.栈(Stack)的概念 二.栈的数据结构 三.栈的实现 判断栈已满 判断栈非空 入栈push 出栈pop 查看栈顶元素 完整代码 Java版本 c语言版 一.栈(Stack)的概念栈是一种先进后出(LIFO)的数据结构,在其中元素的的添加(称为“入栈”)和删除(称为“出栈”)仅在栈的顶部进行。因此,最后一个插入到栈中的元素是第一个从栈中删除的元素。 它通常有两个主要操作: push:在栈的顶部插入一个元素。pop:从栈的顶部移除一个元素。栈的push入栈图解: 栈的pop出栈图解 : 我们可以看见对于栈的操作,我们都是在栈顶上操作的,先进来的元素会被后面的元素覆盖,而最后一个进来的元素也就是栈顶,因此我们称为先进后出(LIFO) 像传统的狙击步枪的弹夹就属于是一种栈的结构 对于栈的实现,我们通常使用数组,当然也可以使用链表,不过相对而言数组的实现是更容易的。 而对于一个栈的数据结构,他首先得有存放元素的位置,我们这里选择用数组来存放,其次还得有栈内元素个数的记录: public class MyStack { public int[] elem; public int usedSize; } 三.栈的实现对于一个栈,他应该有以下这些功能: 入栈出栈判断栈是否为空判断栈已满查看栈顶元素 判断栈已满当已经使用的数组的大小等于数组本身的大小的时候,栈就相当于满了 public boolean isFull() { return usedSize == elem.length; } 判断栈非空当数组内一个元素都没有,也就是已经使用的数组大小为0的时候,栈就是空的 public boolean isEmpety() { return usedSize == 0; } 入栈push当我们要将元素放入栈内的时候,先进行判断,只有在栈内还有剩余空间的情况下,我们才会进行入栈操作,如果没有剩余空间,我们就进行扩容 出栈前要先进行判断,如果栈内一个元素都没有,那自然是不能进行出栈操作的,我们就抛出一个自定义异常然后抛出;对于正常的出栈操作,我们拿出栈顶的元素,然后让记录数组的个数减一 public int pop() { if (isEmpety()) { //栈为空,无法出栈 throw new EmptyStackException("栈为空,无法弹出"); } int popNumber = elem[usedSize-1]; usedSize--; return popNumber; } 查看栈顶元素和出栈不一样的是,查看栈顶元素只是将元素拿出来展示,并没有实际上删除这个元素 public int peek() { if (isEmpety()) { //栈为空,无法出栈 throw new EmptyStackException("栈为空,无法弹出"); } return elem[usedSize - 1]; } 完整代码栈的整体实现相较于顺序表和链表是非常简单的,这里附上完整代码 Java版本 import java.util.Arrays; public class MyStack { public int[] elem; public int usedSize; public static int DEFULT_SIZE = 10; public MyStack() { this.elem = new int[DEFULT_SIZE]; } public void push(int val) { if (isFull()) { //扩容 elem = Arrays.copyOf(elem, elem.length * 2); } elem[usedSize++] = val; } public int pop() { if (isEmpety()) { //栈为空,无法出栈 throw new EmptyStackException("栈为空,无法弹出"); } int popNumber = elem[usedSize-1]; usedSize--; return popNumber; } public int peek() { if (isEmpety()) { //栈为空,无法出栈 throw new EmptyStackException("栈为空,无法弹出"); } return elem[usedSize - 1]; } public boolean isFull() { return usedSize == elem.length; } public boolean isEmpety() { return usedSize == 0; } } c语言版 #include #include #define STACK_SIZE 10 // 定义栈结构体 typedef struct { int data[STACK_SIZE]; // 存放数据的数组 int top; // 栈顶指针 } Stack; // 初始化栈 void init_stack(Stack *s) { s->top = -1; // 栈顶初始化为-1 } // 判断栈是否为空 int is_empty(Stack *s) { return s->top == -1; } // 判断栈是否已满 int is_full(Stack *s) { return s->top == STACK_SIZE-1; } // 入栈 void push(Stack *s, int value) { if (is_full(s)) { printf("Stack overflow\n"); exit(1); } s->data[++s->top] = value; // 栈顶指针先加1,再将元素入栈 } // 出栈 int pop(Stack *s) { if (is_empty(s)) { printf("Stack underflow\n"); exit(1); } return s->data[s->top--]; // 先将元素出栈,再将栈顶指针减1 } // 获取栈顶元素 int peek(Stack *s) { if (is_empty(s)) { printf("Stack underflow\n"); exit(1); } return s->data[s->top]; } |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |