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

ゞ浴缸里的玫瑰 2023-09-26 10:14 58阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【Java实现数据结构】**][Java]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  一. 什么是栈?
 *   *  1. 栈的特点
     *  2. 栈相关的应用场景
     *   *  2.1 关于栈的出栈序列
         *  2.2 前，中，后缀表达式
     *  3. 栈的模拟实现
     *  4. 栈、虚拟机栈、栈帧有什么区别呢？
 *  二. 集合-Stack类
 *   *  1. Stack的介绍
     *  2. 常用方法
     *  3. 利用Stack将递归用循环实现

## 一. 什么是栈? ##

### 1. 栈的特点 ###

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

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

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

![img][]

![img][img 1]

### 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，将中缀表达式按运算顺序打上不同的括号对，分别将运算符移到对应括号最右边，再将所有括号擦除，就能得到**后缀表达式**，同理将运算符移到到对应括号最左边就是**前缀表达式**。

示例如下 :

![img][img 2]

### 3. 栈的模拟实现 ###

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

**MyStack.java**

import java.util.Arrays;
    
    public class MyStack {
        
        public int[] elem;
        public int usedSize;
        public static final int DEFAULT_SIZE = 10;
    
        public MyStack() {
        
            this.elem = new int[DEFAULT_SIZE];
        }
    
        //压栈
        public int push(int val) {
        
            //判断空间容量
            if(this.isFull()) {
        
                //扩容
                this.elem = Arrays.copyOf(elem, this.usedSize*2);
            }
            this.elem[this.usedSize++] = val;
            return val;
        }
        public boolean isFull() {
        
            return this.elem.length == this.usedSize;
        }
    
        //出栈
        public int pop() {
        
            if(this.empty()) {
        
                throw new MyEmptyStackException("当前栈为空!");
            }
            return this.elem[--usedSize];
        }
    
        //判断栈是否为空
        public boolean empty() {
        
            return this.usedSize == 0;
        }
    
        //获取栈顶元素
        public int peek() {
        
            if(this.empty()) {
        
                throw new MyEmptyStackException("当前栈为空");
            }
            return this.elem[this.usedSize-1];
        }
    }

**MyEmptyStackException.java**

public class MyEmptyStackException extends RuntimeException{
        
        public MyEmptyStackException() {
        
        }
    
        public MyEmptyStackException(String message) {
        
            super(message);
        }
    }

**TestStack.java**

public class TestStack {
        
        public static void main(String[] args) {
        
            MyStack myStack = new MyStack();
            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());
        }
    }

**执行结果**

![img][img 3]  
**【思考】**

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

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

**所以如果采用单链表来实现栈应该采用头插法入栈**, 代码实现如下:

public class MyStack<V> {
        
        private Node<V> head;
        private int size;
    
        // 判断栈是否为空
        public boolean isEmpty() {
        
            return size == 0;
        }
        // 获取栈的长度
        public int size() {
        
            return size;
        }
        // 元素入栈
        public void offer(V val) {
        
            Node<V> cur = new Node<>(val);
            if (head == null) {
        
                head = cur;
            } else {
        
                cur.next = head;
                head = cur;
            }
            size++;
        }
        // 元素出栈
        public V pop() {
        
            V ret = null;
            if (head != null) {
        
                ret = head.val;
                head = head.next;
                size--;
            }
            return ret;
        }
        // 查看栈顶元素
        public V peek() {
        
            return head != null ? head.val : null;
        }
    }

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

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

**这里要注意概念的区分;**

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

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

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

## 二. 集合-Stack类 ##

### 1. Stack的介绍 ###

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

![img][img 4]

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

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

### 2. 常用方法 ###

<table> 
 <thead> 
  <tr> 
   <th><strong>方法</strong></th> 
   <th><strong>功能</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Stack()</td> 
   <td>构造一个空的栈</td> 
  </tr> 
  <tr> 
   <td>E push(E e)</td> 
   <td>将e入栈，并返回e</td> 
  </tr> 
  <tr> 
   <td>E pop(</td> 
   <td>将栈顶元素出栈并返回</td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取栈顶元素</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取栈中有效元素个数</td> 
  </tr> 
  <tr> 
   <td>boolean empty()</td> 
   <td>检测栈是否为空</td> 
  </tr> 
 </tbody> 
</table>

代码示例:

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

执行结果:  
![img][img 5]

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

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

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

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[Java]: https://blog.csdn.net/trong_/category_11997769.html
[img]: https://img-blog.csdnimg.cn/img_convert/abdfe87fb81d1b20d622766c2b8f8142.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/49e84b7be87f80d24a40455cf7f17be4.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/740e3424b2a16744993664aa14e9654a.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/fe4c5931ed0c04f2e9ef301cc882423d.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/e0051ff8fd7c4cecfd7d282f62559b01.png
[img 5]: https://img-blog.csdnimg.cn/img_convert/ac51e15daed10760cbe470668803f271.png