南宁做网站价格,有关网站建设的文章,广告网页推广,做网站可以用思源字体吗前言
栈最鲜明的特点就是后进先出#xff0c;一碟盘子就是类似这样的结构#xff0c;最晚放上去的#xff0c;可以最先拿出来。本文将介绍的是如何自己实现一个栈结构。
栈的操作
栈是一种先进后出#xff08;Last-In-First-Out, LIFO#xff09;的数据结构#xff0c…前言
栈最鲜明的特点就是后进先出一碟盘子就是类似这样的结构最晚放上去的可以最先拿出来。本文将介绍的是如何自己实现一个栈结构。
栈的操作
栈是一种先进后出Last-In-First-Out, LIFO的数据结构常见操作包括
1、入栈Push将元素压入栈顶。 2、出栈Pop弹出栈顶元素并返回其值。 3、查看栈顶元素Peek返回栈顶元素的值但不对栈进行修改。 4、判断栈是否为空isEmpty检查栈是否为空如果栈中没有任何元素则返回 true否则返回 false。 5、获取栈的大小size返回栈中元素的数量。 6、清空栈clear清除栈中的所有元素使其变为空栈。 这些是栈的基本操作。栈的实际使用还可能涉及其他操作如遍历栈、搜索特定元素、栈的深度等等。根据具体的需求你可以针对栈的特性来自定义其他更复杂的操作。
栈的实现
栈是较容易实现的抽象数据结构之一。我们可以选择数组或者链表来实现它们各有特点前者容量有限且固定但操作简单而后者容量理论上不受限但是操作并不如数组方便每次入栈要进行内存申请出栈要释放内存稍有不慎便造成内存泄露。本文对两种实现都做介绍。
1、用数组实现栈
数组之你值得了解的底层
/*** 用数组实现一个栈*/
public class MyStack {private int maxSize; //栈的大小private int[] stackArray; // 数组模拟一个栈用于存放private int top -1; // 表示栈顶初始为-1public MyStack(int maxSize) {this.maxSize maxSize;stackArray new int[this.maxSize];}public void push(int value) {//判断是否栈满if(isFull()){System.out.println(栈满了..);return;}stackArray[top] value;}//弹出栈顶的元素并返回public int pop(int value) {//判断栈是否为空if(isEmpty()) {throw new RuntimeException(栈空没有数据~~);}value stackArray[top--];return value;}//查看栈顶的元素public int peek() {//判断栈是否为空if(isEmpty()) {throw new RuntimeException(栈空没有数据~~);}return stackArray[top];}// 显示栈中的数据-从栈顶开始显示public void list() {// 判断是否栈空if (isEmpty()) {System.out.println(栈空~~);return;}//从栈顶开始展示数据for (int i top; i 0; i--) {System.out.printf(stack[%d]%d\n, i, stackArray[i]);}}//栈空public boolean isEmpty() {return top -1;}//栈满public boolean isFull() {return top (maxSize - 1);}
}
2、用队列实现栈
Java两个队列实现一个栈
3、用链表实现栈
/*** Description* Author Flag* Date: 2021/7/20 8:53* Version: 1.0**/
public class LinkedStackDome {public static void main(String[] args) {//测试一下LinkedStack是否正常//先创建一个ArrayStack对象-表示栈LinkedStack stack new LinkedStack(4);String key ;boolean loop true;//用于控制是否退出Scanner scanner new Scanner(System.in);while (loop){System.out.println(show:表示显示栈);System.out.println(exit:退出程序);System.out.println(push:表示添加元素到栈(入栈));System.out.println(pop:表示从栈取出数据(出战));System.out.println(请输入你的选择:);key scanner.next();switch (key){case show:stack.show();break;case exit:scanner.close();loop false;break;case push:System.out.println(请输入一个数字);int i scanner.nextInt();stack.push(i);break;case pop:try{int pop stack.pop();System.out.println(出栈的数据:pop);} catch (Exception e){System.out.println(e.getMessage());}break;default:break;}}}}class LinkedStack{//定义栈的大小private int maxSize;//链表模拟栈private LinkedStackNode first;//top表示栈顶初始化是-1private int top;/*** 构造方法* param maxSize 栈的大小*/public LinkedStack(int maxSize) {this.maxSize maxSize;top -1;}/*** 判断栈是否满了* return*/public boolean isFull(){return top1 maxSize;}/*** 入栈* param value 入栈的元素*/public void push(int value){//1、判断栈是否满了if(this.isFull()){System.out.println(栈已经满了,不能再添加元素);return;}//2、新创建一个节点用于添加到链表上LinkedStackNode node new LinkedStackNode(value);//3、将top,表示链表中的元素新增了一个top;//4、判断头元素是否为null,如果是null,代表是第一个元素,则直接让新元素当第一个元素if(first null){first node;return;}//5.如果头元素不是null,则证明此时链表中已经有元素则将新元素添加上即可//5.1获取到链表的尾部LinkedStackNode middleNode first;while (middleNode.getNext() ! null){middleNode middleNode.getNext();}//5.2将链表添加上去middleNode.setNext(node);}/*** 出栈* return 出栈的元素*/public int pop(){//1.判断栈是否为nullif(this.isEmpty()){throw new RuntimeException(栈中没有元素);}//2.将链表的数量减一top -- ;//3.如果链表中是否只有一个元素if(first.getNext() null){LinkedStackNode popNode this.first;this.first null;return popNode.getNumber();}//4.如果链表中有不只一个元素//4.1.定义一个中间变量让他指向链表的最后一个元素即最后要出栈的元素LinkedStackNode lastNode first;//4.2.定义一个中间变量用来用来获取到比lastNode前一个元素,‘//因为是单向链表我们出栈后要置空指向最后一个元素的指针所以需要找到最有一个元素的前一个元素进行操作LinkedStackNode beforeLastNode null;//4.2.遍历链表,直到lastNode是最后一个元素,此时如果链表中只有一个元素则while (lastNode.getNext() ! null){//将lastNode给到beforeLastNode//然后lastNode向后移动//此时就构造出 beforeLastNode在lastNode前一个位置的情况beforeLastNode lastNode;lastNode lastNode.getNext();}//4.3.此时将最后一个元素的前一个元素的next指针变成null,则相当于舍弃掉了最后一个元素beforeLastNode.setNext(null);//4.3.返回lastNode的编号return lastNode.getNumber();}/*** 显示栈的元素*/public void show(){//判断栈是否为nullif(this.isEmpty()){System.out.println(栈中无元素);return;}//定义一个新的链表节点LinkedStackNode newLinedStackHead null;//正向遍历原始链表将链表的每一个元素都放到新的链表的第一个元素//因为前面做了判断所以first不可以为nullLinkedStackNode oldLinkedStackNode first;//直到原始链表元素为null时结束while (oldLinkedStackNode ! null){LinkedStackNode middleNode new LinkedStackNode(oldLinkedStackNode.getNumber());if(newLinedStackHead null){newLinedStackHead middleNode;} else {middleNode.setNext(newLinedStackHead);newLinedStackHead middleNode;}//移动原始链表的位置oldLinkedStackNode oldLinkedStackNode.getNext();}while (newLinedStackHead ! null){System.out.println(newLinedStackHead.getNumber());newLinedStackHead newLinedStackHead.getNext();}}/*** 判断栈是否为null* return 结果*/public boolean isEmpty(){return top -1;}
}/*** 链表栈的节点*/
class LinkedStackNode{private int number;private LinkedStackNode next;public LinkedStackNode(int number) {this.number number;}public int getNumber() {return number;}public LinkedStackNode getNext() {return next;}public void setNext(LinkedStackNode next) {this.next next;}
}
栈的应用
1、栈的应用——递归
1、递归的定义
递归是一种重要的程序设计方法。简单地说,若在一个函数、过程或数据结构的定义中又应用了它自身,则这个函数、过程或数据结构称为是递归定义的,简称递归。 它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的代码就可以描述岀解题过程所需要的多次重复计算,大大减少了程序的代码量但在通常情况下,它的效率并不是太高。
2、斐波那契数列
2、栈的应用——四则运算表达式求值
1、后缀表达式计算结果 2、中缀表达式转后缀表达式
笔记
