【JavaDS】栈与集合Stack的理解和使用

✨博客主页: XIN-XIANG荣
✨系列专栏:【Java实现数据结构】
✨一句短话: 难在坚持,贵在坚持,成在坚持!

文章目录

一. 什么是栈?

1. 栈的特点

栈是一种组织数据的方式，栈内的元素有先进后出的特点 , 是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。我们自己去实现栈可以用数组或者双链表来完成 ;

Java集合中的Stack类在底层其实就是一个数组空间 , 当然LinledList底层是一个双链表，所以LinkedList也可以当做栈来使用。

栈的几个术语：
允许进行插入、删除操作的一端称为栈顶；栈的另一端称为栈底。
当栈中没有数据元素时，称为空栈。
栈的插入操作通常称为进栈或入栈（压栈）。
栈的删除操作通常称为退栈或出栈。

2. 栈相关的应用场景

2.1 关于栈的出栈序列

给你入栈序列，判断不可能的出栈序列，看下面给出的例题：

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

​ A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

解析:

选项A： 1入栈，1出栈，2，3，4依次入栈，4，3，2 依次出栈 , 出栈序列为1，4，3，2 ，所以选项A的出栈序列是可能的。

选项B： 1，2依次入栈，2出栈，3入栈，3出栈，4入栈，4出栈，1出栈 , 出栈序列为2，3，4，1 ，所以选项C的出栈序列是可能的。

选项C： 1，2，3依次入栈，3出栈，选项中的第二个出栈序列为1 , 但此时3出栈后栈顶元素为2 , 不可能是1出栈 , 所以选项C的出栈序列是不可能的。

选项D： 1，2，3依次入栈，3出栈，4入栈，4出栈，2，1依次出栈，出栈序列为3，4，2，1 ，所以选项D的出栈序列是可能的。

1. 一个栈的入栈序列为1，2，3，…，n ，其出栈序列是P1，P2,P3，…，Pn。若P2=3，则P3可能取值的个数是（ ）多少?

​ A.n-3 B.n-2 C.n-1 D.无法确定

解析:

P3的取值除了不能取到3其他的值均有可能，所以P3可能取值的个数为n-1。

2.2 前，中，后缀表达式

我们常用的数学加减乘除运算表达式都是中缀表达式，比如 1+2+3∗4，将中缀表达式按运算顺序打上不同的括号对，分别将运算符移到对应括号最右边，再将所有括号擦除，就能得到后缀表达式，同理将运算符移到到对应括号最左边就是前缀表达式。

示例如下 :

3. 栈的模拟实现

由于Java集合中的Stack类在底层是一个顺序表 , 所以这里用数组来模拟实现栈 .

MyStack.java

importjava.util.Arrays;publicclassMyStack{publicint[] elem;publicint usedSize;publicstaticfinalint DEFAULT_SIZE =10;publicMyStack(){this.elem =newint[DEFAULT_SIZE];}//压栈publicintpush(int val){//判断空间容量if(this.isFull()){//扩容this.elem =Arrays.copyOf(elem,this.usedSize*2);}this.elem[this.usedSize++]= val;return val;}publicbooleanisFull(){returnthis.elem.length ==this.usedSize;}//出栈publicintpop(){if(this.empty()){thrownewMyEmptyStackException("当前栈为空!");}returnthis.elem[--usedSize];}//判断栈是否为空publicbooleanempty(){returnthis.usedSize ==0;}//获取栈顶元素publicintpeek(){if(this.empty()){thrownewMyEmptyStackException("当前栈为空");}returnthis.elem[this.usedSize-1];}}

MyEmptyStackException.java

publicclassMyEmptyStackExceptionextendsRuntimeException{publicMyEmptyStackException(){}publicMyEmptyStackException(String message){super(message);}}

TestStack.java

publicclassTestStack{publicstaticvoidmain(String[] args){MyStack myStack =newMyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);System.out.println(myStack.peek());System.out.print(myStack.pop()+" ");System.out.print(myStack.pop()+" ");System.out.print(myStack.pop()+" ");System.out.print(myStack.pop()+" ");System.out.println(myStack.pop());System.out.println(myStack.empty());}}

执行结果

【思考】

如果使用链表来实现栈 , 如何操作入栈和出栈更方便一些呢?

首先考虑单链表 , 假设单链表中有head和tail两个引用指向头节点和尾节点 , 那么如果是尾插入栈 , 时间复杂度为O(1) , 但此时出栈 , 需要找到尾节点的前一个节点 , 出栈的时间复杂度就为O(N)了 ; 再看头插入栈 , 时间复杂度为O(1) , 此时出栈也是从头出 , 时间复杂度为O(1) ;

所以如果采用单链表来实现栈应该采用头插法入栈 .

再考虑双链表表来实现栈 , 由于节点之间是双向的 , 所以入栈采用头插和尾插都可 , 最终入栈和出栈的时间复杂度都为O(1) , 所以采用双向链表来实现栈还是很方便的 .

4. 栈、虚拟机栈、栈帧有什么区别呢？

这里要注意概念的区分;

栈 : 是一种先进后出的数据结构。

虚拟机栈 : 是JVM的一块内存空间

栈帧 : 是在调用函数的过程当中，在Java虚拟机栈上开辟的一块内存。

二. 集合-Stack类

1. Stack的介绍

在集合框架中 , Stack的继承实现关系如下:

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的 ;

Vector类，是线程安全的动态数组，但是性能较差 , 现在已经不是很常用了 , 可以说已经过时了 .

2. 常用方法

方法****功能Stack()构造一个空的栈E push(E e)将e入栈，并返回eE pop(将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空
代码示例:

publicstaticvoidmain(String[] args){Stack<Integer> s =newStack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);System.out.println(s.size());// 获取栈中有效元素个数---> 4System.out.println(s.peek());// 获取栈顶元素---> 4
        s.pop();// 4出栈，栈中剩余1 2 3，栈顶元素为3System.out.println(s.pop());// 3出栈，栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}

执行结果:

3. 利用Stack将递归用循环实现

比如下面的代码 , 使用递归逆序打印单链表 , 可以使用Stack来模拟实现递归的过程(循环) .

// 递归方式打印单链表publicvoidprintList1(ListNode head){if(null!= head){printList1(head.next);System.out.print(head.val +" ");}}// 循环方式,利用栈打印单链表publicvoidprintList2(ListNode head){if(null== head){return;}Stack<ListNode> s =newStack<>();// 将链表中的结点保存在栈中ListNode cur = head;while(null!= cur){
            s.push(cur);
            cur = cur.next;}}