网络营销咨询网站源码,山西建设部网站查询,公众号绑定网站,成都品牌策划设计公司栈的基础知识
栈的特征
特征1 栈和队列是比较特殊的线性表#xff0c;又被称为 访问受限的线性表。栈是很多表达式、符号等运算的基础#xff0c;也是递归的底层实现#xff08;递归就是方法自己调用自己#xff0c;在JVM的虚拟机栈中#xff0c;一个线程中的栈帧就是…栈的基础知识
栈的特征
特征1 栈和队列是比较特殊的线性表又被称为 访问受限的线性表。栈是很多表达式、符号等运算的基础也是递归的底层实现递归就是方法自己调用自己在JVM的虚拟机栈中一个线程中的栈帧就是一个要调用的方法栈帧的实现就是栈结构其会将正在执行的方法栈帧设在栈顶。理论上递归能够做的题目栈都可以做只是有些问题用栈会比较复杂。 特征2 栈的底层实现依然是链表或者顺序表。栈与线性表的最大区别就是数据的存取操作被限制了其插入和删除操作只允许在线性表的一端进行。 一般而言把2允许操作的一端称为栈顶top不可操作的一端称为栈底bottom 把插入元素的操作称为入栈Push把删除元素的操作称为出栈pop若栈中没有任何元素则称为空栈。其结构如下 栈的操作
栈的常用操作主要有 pushE增加一个元素Epop弹出一个元素Epeek只显示栈顶元素不弹出元素empty判断栈是否为空 在自定义栈时不管用数组还是链表都要实现上面的几个方法。 检测对栈的理解 入栈顺序为1234所有可能的出栈序列是什么 4个元素的全排列共有24种栈要求符合后进先出按此衡量排除后即得 1234√ 1243√ 1324√ 1342√ 1432√ 2134√ 2143√ 4321√ 2314√ 2341√ 2431√3421√ 3214√ 3241√ 3124x 3142x 3412x 4123x 4132x 2413x 4213x 4231x 4312x 1423x 14种可能10种不可能如上所示。 Java中的栈 java的util中提供了栈Stack类使用不复杂看下面例子 public class MainTest {
public static void main(string[] args) {StackInteger stack new stack();stack.push(1);stack.push(2);stack.push(3);System.out.println(栈顶元素为: stack.peek());while (!stack.empty()){//只显示没出栈System.out.printIn(stack.peek());//出栈并且显示System.out.println(stack.pop());}}
}
自定义栈 如果要自己实现栈可以有数组、链表和java提供的LinkedList三种基本方式我们都看一下。 采用顺序表实现的的栈内部以数组为基础实现对元素的存取操作。在应用中还要注意每次入栈之前先判断栈的容量是否够用如果不够用可以进行扩容。 入栈过程如下图所示 出栈过程如下图所示 基于数组实现栈 top先将栈顶元素取出然后再执行top--。完整的实现代码如下 package org.example.stack;import java.util.Arrays;public class MyStackByArrayT{// 实现栈的数组private Object[] stack;// 栈顶元素private int top;//初始化栈容量public MyStackByArray(int top) {stack new Object[top];}//判断栈是否为空public boolean isEmpty(){return top 0;}//返回栈顶元素public T peek(){T t null;if (top 0){t (T) stack[top -1];}return t;}// 入栈public void push(T t){extendCapacity(top 1);stack[top] t;top;}// 出栈public T pop(){T t peek();if (top 0){stack[top-1] null;top--;}return t;}//扩大容量private void extendCapacity(int size) {int len stack.length;if (len size){size size * 3/2 1;stack Arrays.copyOf(stack, size);}}}基于链表实现栈 链表实现栈只需要把删除和修改的操作都限制在头节点即可如下图 实现代码如下 package org.example.stack;public class MyStackByLinkedList T{// 构造节点class NodeT{public T t;public Node next;}// 头指针public NodeT head;// 初始化MyStackByLinkedList(){head null;}// 入栈public void push(T t){if (tnull){throw new NullPointerException(形参不能为空);}// 如果是空链表就将入栈的元素设为第一个元素if (head null){head new Node();head.t t;head.next null;}else {NodeT temp head;head new Node();head.t t;head.next temp;}}// 出栈public T pop(){T t null;if (head null){return null;}else {t head.t;head head.next;}return t;}// 取栈顶元素public T peek(){if (head null){return null;}return head.t;}//栈空public boolean isEmpty(){return head null;}
}
