数据结构 之 栈(Stack) |
您所在的位置：网站首页 › 栈具有什么性质 › 数据结构 之 栈(Stack) |
数据结构 之 栈(Stack)
|
1. 定义：栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作； 进行数据插入的和删除的一端称为栈顶，另一端称为栈底； 栈这个数据结构遵从后进先出（先进后出）的原则； 如图所示，每次在栈中添加元素或者取出元素时，只能在栈顶进行操作，这就是后进先出的原则 类似于我们现实生活中的枪械的弹夹一般：  先装入弹夹的子弹，往往在弹夹的最下方，同时也是最后一个被发射出去的； 又例如：  这是我们qq的更新的弹窗，如果我们不关闭这个弹窗，就无法使用qq的其他功能，这个弹窗是最后一个弹出来的，同时也是第一个被关闭的，这里同样使用的栈这个数据结构；  从上图可以看出，Stack继承于Vector，Vevtor和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的； 2. 栈、虚拟机栈、栈帧的区别：栈：如上所述，栈是一种后进先出的数据结构； 虚拟机栈：虚拟机栈是具有特殊作用的一块内存空间； jvm为了对数据进行更好的管理，将内存按照不同的需求划分出来的一种结构 栈帧：一种结构，这种结构与函数调用相关的，内部：局部变量表、操作数栈...... 每个方法在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中 当方法调用结束时，该方法对应的栈帧会从虚拟机栈中出栈 3.栈的常用方法和模拟实现：3.1 常用方法：方法作用Stack()构造一个大小为默认大小的栈Stack(int n) 构造一个大小为n的空栈 E push(E e)将e入栈，并返回eE pop() 获取栈顶元素并删除栈顶元素E peek()获取栈顶元素size()获取栈的元素个数empty() 检测栈是否为空 （在栈的模拟实现中，我们并不使用泛型，而是使用整形来代替泛型） 以上就是栈的常用方法，接下来我们开始模拟实现这些方法： 3.2 模拟实现：首先我们来写一个My_Stack类： 代码语言：javascript复制public class My_Stack { int[] elem; //模拟实现栈 int usedSize; //已使用的长度 int DEFAULT_CAPACITY = 10; //默认大小 }< 1 > 构造方法： 这里模拟实现两个构造方法： 一个是构造默认大小的栈 一个是构造指定大小的栈 代码语言：javascript复制public My_Stack() { this.elem = new int[DEFAULT_CAPACITY]; //构造一个大小为默认大小的栈 } public My_Stack(int n) { this.elem = new int[n]; //构造一个大小为n的栈 }< 2 > push方法： push方法是将给定的值进行入栈操作，并返回该值 在进行push方法的时候，我们需要判断栈是否满了，如果栈满了，我们就需要进行扩容，那我们就需要写一下判断栈是否满了和扩容的方法： 代码语言：javascript复制private boolean isFUll () { return usedSize == elem.length; //返回数组长度是否等于使用大小 的值 } private void grow (int[] elem) { if (elem.length > 1); //如果大于64，则进行1.5倍扩容 } }在此基础上，我们开始push方法的模拟实现： 代码语言：javascript复制public int push (int val) { if (isFUll()) { //判断栈是否满了，如果满了，则进行扩容 grow(elem); } elem[usedSize++] = val; //在数组的最末尾进行插入，并将usedSize++ return val; //返回val的值 }< 3 > empty方法： empty方法是判断栈是否为空，方法比较简单，如下： 代码语言：javascript复制public boolean empty () { return usedSize == 0; //判断usedSize是否 = 0 即可 }< 4 > pop方法： pop方法是将栈顶元素进行出栈操作，并返回该值： 在进行该操作的时候，我们同样需要判断，栈是否为空，若栈为空，则抛出异常： 异常的代码如下： 代码语言：javascript复制public class StackEmptyException extends RuntimeException{ public StackEmptyException () { super(); } public StackEmptyException (String str) { super(str); } }随后进行pop方法的模拟实现： 代码语言：javascript复制public int pop () { if (empty()) { throw new StackEmptyException("该栈为空，不能进行pop操作!!!"); } int ret = elem[usedSize]; //将elem[usedSize]的值保存下来 usedSize--; //usedSize--相当于删去数组最后一位元素 return ret; //返回被删掉的元素 }< 5 > peek方法： peek方法是返回栈顶的元素，但不删除栈顶元素： 同样在使用peek方法时，我们需要判断栈是否为空，若为空，则需要抛出异常： 代码语言：javascript复制public int peek () { if (empty()) { //判断是否为空 throw new StackEmptyException("该栈为空，不能进行peek操作!!!"); } return elem[usedSize - 1]; //将栈顶元素进行返回 }< 6 > size方法： 代码语言：javascript复制public int size () { return usedSize; //直接返回usedSize大小 }4. 模拟实现全部源码：代码语言：javascript复制import java.util.Arrays; public class My_Stack { int[] elem; //模拟实现栈 int usedSize; //已使用的长度 int DEFAULT_CAPACITY = 10; //默认大小 public My_Stack() { this.elem = new int[DEFAULT_CAPACITY]; //构造一个大小为默认大小的栈 } public My_Stack(int n) { this.elem = new int[n]; //构造一个大小为n的栈 } public int push (int val) { if (isFUll()) { //判断栈是否满了，如果满了，则进行扩容 grow(elem); } elem[usedSize++] = val; //在数组的最末尾进行插入，并将usedSize++ return val; //返回val的值 } private boolean isFUll () { return usedSize == elem.length; //返回数组长度是否等于使用大小 的值 } private void grow (int[] elem) { if (elem.length > 1); //如果大于64，则进行1.5倍扩容 } } public int pop () { if (empty()) { throw new StackEmptyException("该栈为空，不能进行pop操作!!!"); } int ret = elem[usedSize]; //将elem[usedSize]的值保存下来 usedSize--; //usedSize--相当于删去数组最后一位元素 return ret; //返回被删掉的元素 } public boolean empty () { return usedSize == 0; //判断usedSize是否 = 0 即可 } public int peek () { if (empty()) { //判断是否为空 throw new StackEmptyException("该栈为空，不能进行peek操作!!!"); } return elem[usedSize - 1]; //将栈顶元素进行返回 } public int size () { return usedSize; //直接返回usedSize大小 } }5. 栈的应用场景：1. 改变元素的序列 例如，将1 2 3 4依次进行入栈操作，期间可以进行出栈操作，那么我们可以得到许多出栈序列； 2. 将递归转换成循环 例如逆序打印链表 代码语言：javascript复制// 递归方式 void printList(Node head){ if(null != head){ printList(head.next); System.out.print(head.val + " "); } } // 循环方式 void printList(Node head){ if(null == head){ return; } Stack s = new Stack(); // 将链表中的结点保存在栈中 Node cur = head; while(null != cur){ s.push(cur); cur = cur.next; }下面我为大家推荐几道关于栈的题，有兴趣的朋友可以去练练手： 1. 括号匹配 2. 逆波兰表达式求值 3. 出栈入栈次序匹配 4. 最小栈 以上就是栈的全部内容，感谢大家观看！！！！！ |
【本文地址】
今日新闻 |
推荐新闻 |