【数据结构Java版】Stack栈的妙用

偏执的太偏执、 2024-04-01 09:17 52阅读 0赞

**目录**

一、栈的概念

二、栈的使用

（1）主要方法

（2）实例演示

三、栈的模拟实现

四、栈相关练习题

（1）有效的括号

（2）栈的压入、弹出序列

（3）逆波兰表达式求值

（4）用栈实现队列

--------------------

## 一、栈的概念 ##

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。  
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。  
出栈：栈的删除操作叫做出栈。出数据在栈顶。

观察栈顶元素，而不动栈的结构：peek

Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安  
全的。  
  
![aaee66b4bd9f4bf98d97ff66db89a6a7.png][]

![4c4dfe0d8e5f46fbaf23b6c3eb5b4c42.png][]

## 二、栈的使用 ##

### （1）主要方法 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>功能</td> 
  </tr> 
  <tr> 
   <td>Stack()</td> 
   <td>构造一个空栈</td> 
  </tr> 
  <tr> 
   <td>E push(E e)</td> 
   <td>将e入栈，并返回e</td> 
  </tr> 
  <tr> 
   <td> <p>E pop()</p> </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>

### （2）实例演示 ###

import java.util.Stack;
    public class Demo {
        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());
            }
        }
    }

![deeb2c2b9f644febb063d7b0527ce17e.png][]

## 三、栈的模拟实现 ##

// 元素类型固定为 long 类型
    // 使用数组（顺序表）实现栈
    // 使用尾插：压栈
    // 使用尾删：弹栈
    // 不考虑扩容等问题
    public class Stack {
        private final long[] array = new long[100];
        private int size = 0;   // 记录为 top 也可以
    
        public int size() {
            return size;
        }
    
        public boolean isEmpty() {
            return size() == 0;
        }
    
        public void push(long x) {
            array[size++] = x;  // 尾插
        }
    
        public long pop() {
            if (isEmpty()) {
                throw new RuntimeException("栈是空的");
            }
    
            return array[--size];   // 尾删
        }
    
        public long peek() {
            if (isEmpty()) {
                throw new RuntimeException("栈是空的");
            }
    
            return array[size - 1];
        }
    
        public static void main(String[] args) {
            Stack stack = new Stack();
    
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
    
            System.out.println(stack.peek());   // 4
            stack.push(5);
    
            System.out.println(stack.peek());   // 5
    
            stack.push(6);
    
            System.out.println(stack.pop());    // 6
            System.out.println(stack.pop());    // 5
        }
    }

## 四、栈相关练习题 ##

### （1）有效的括号 ###

> [20. 有效的括号][20.]
> 
> 难度简单3645
> 
> 给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。
> 
> 有效字符串需满足：
> 
> 1.  左括号必须用相同类型的右括号闭合。
> 2.  左括号必须以正确的顺序闭合。
> 3.  每个右括号都有一个对应的相同类型的左括号。
> 
> **示例 1：**
> 
>     输入：s = "()"
>     输出：true
> 
> **示例 2：**
> 
>     输入：s = "()[]{}"
>     输出：true
> 
> **示例 3：**
> 
>     输入：s = "(]"
>     输出：false

class Solution {
        public boolean isValid(String s) {
            Stack <Character> stack = new Stack<>();
            for(int i=0;i<s.length();i++){
                char c=s.charAt(i);
                if((c=='(')||(c=='[')||(c=='{')){
                    stack.push(c);
                    continue;
                }else{
                    if(!stack.empty()){
                        char e=stack.pop();
                        if(!isMatch(c,e)){
                            return false;
                            }
                        }else{
                            return false;
                        }
                    }
                }
            if(stack.empty()){
                return true;
            }else{
                return false;
            }
        }
         public boolean isMatch(char c,char e) {
          if((e=='('&&c==')')||(e=='['&&c==']')||(e=='{'&&c=='}')){
              return true;
          }else{
              return false;
          }
        }
    }

![0fee9587e684417c88f1a120f037c4a6.png][]

### （2）栈的压入、弹出序列 ###

> [【Java版oj】栈的压入、弹出序列\_小熊爱吃软糖吖的博客-CSDN博客][Java_oj_-CSDN]

### （3）逆波兰表达式求值 ###

> [【Java版oj】逆波兰表达式求值\_小熊爱吃软糖吖的博客-CSDN博客][Java_oj_-CSDN 1]

### （4）用栈实现队列 ###

> [232. 用栈实现队列][232.]
> 
> 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（`push`、`pop`、`peek`、`empty`）：
> 
> 实现 `MyQueue` 类：
> 
>  *  `void push(int x)` 将元素 x 推到队列的末尾
>  *  `int pop()` 从队列的开头移除并返回元素
>  *  `int peek()` 返回队列开头的元素
>  *  `boolean empty()` 如果队列为空，返回 `true` ；否则，返回 `false`
> 
> **说明：**
> 
>  *  你 **只能** 使用标准的栈操作 —— 也就是只有 `push to top`, `peek/pop from top`, `size`, 和 `is empty` 操作是合法的。
>  *  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
> 
> **示例 1：**
> 
>     输入：
>     ["MyQueue", "push", "push", "peek", "pop", "empty"]
>     [[], [1], [2], [], [], []]
>     输出：
>     [null, null, null, 1, 1, false]
>     
>     解释：
>     MyQueue myQueue = new MyQueue();
>     myQueue.push(1); // queue is: [1]
>     myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
>     myQueue.peek(); // return 1
>     myQueue.pop(); // return 1, queue is [2]
>     myQueue.empty(); // return false

class MyQueue {
        private Stack <Integer> stack1=new Stack<>();//用来放元素
        private Stack <Integer> stack2=new Stack<>();//用来出元素
    
        public MyQueue() {
    
        }
        
        public void push(int x) {
            stack1.push(x);
        }
        
        public int pop() {
            if(empty()){
                return 0;
            }
            if(stack2.empty()){
                while(!stack1.empty()){
                    int elem=stack1.pop();
                    stack2.push(elem);
                }
            }
            return stack2.pop();
        }
        
        public int peek() {
            if(empty()){
                return 0;
            }
            if(stack2.empty()){
                while(!stack1.empty()){
                    int elem=stack1.pop();
                    stack2.push(elem);
                }
            }
            return stack2.peek();
        }
        public boolean empty() {
            return stack1.empty()&&stack2.empty();
        }
    }

![6a511b51a1164a0688ddc95a7eff6921.png][]

--------------------

![aae56ecb221b4f76a68e992431e79b8a.png][]

[aaee66b4bd9f4bf98d97ff66db89a6a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4859b57eef6b4bbeb8072d8c3e0a8068.png
[4c4dfe0d8e5f46fbaf23b6c3eb5b4c42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7e603da8b87e4f5c8f1567e197d6334a.png
[deeb2c2b9f644febb063d7b0527ce17e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b8a1d069f62549dbbf0706378ef4f34e.png
[20.]: https://leetcode.cn/problems/valid-parentheses/
[0fee9587e684417c88f1a120f037c4a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b96c4f788ce3483bbe7660de8a2af4aa.png
[Java_oj_-CSDN]: https://blog.csdn.net/m0_63372226/article/details/128337855
[Java_oj_-CSDN 1]: https://blog.csdn.net/m0_63372226/article/details/128338517?spm=1001.2014.3001.5501
[232.]: https://leetcode.cn/problems/implement-queue-using-stacks/
[6a511b51a1164a0688ddc95a7eff6921.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8274cc70cbb0495aa79f067550a04565.png
[aae56ecb221b4f76a68e992431e79b8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/060f4be52d364e55b147d36cf20c7450.png