栈和队列(详解)

绝地灬酷狼 2024-04-23 12:54 64阅读 0赞

**【本节目标】  
1. 栈的概念及使用  
2. 队列的概念及使用  
3. 相关OJ题**

## **1.栈(Stack)** ##

### **1.1 概念** ###

栈:一种特殊的线性表,其只允许在固定一端进行插入和删除元素的操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底,栈中的数据遵守后进后出的原则.

![e713505c7ba345eaa59159f6c972071b.png][]

栈在生活中的例子:

![04a1c8d379c24754bcacb685ec443ad3.png][]

### 1.2 栈的使用 ###

![2450fec46ff747afb9299bd1ffec205e.png][]

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
    }

![d149a4c45d9c46899cdac406d1cafeac.png][]

### 1.3 栈的模拟实现 ###

![25b8ab79292d438f83fe02257d4f0bf0.png][]

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

import java.util.Arrays;
    
    public class Mystack implements IStack{
        int[] elem;
    private final int chushi=10;
        public Mystack(int[] elem) {
            this.elem = new int[chushi];
        }
        int usesize = 0;
    
        @Override
        public int push(int e) {
            if(full()){
                elem= Arrays.copyOf(elem,elem.length*2);
            }
            elem[usesize]=e;
             usesize++;
            return e;
        }
        @Override
        public boolean full(){
           if(usesize == elem.length){
               return true;
           }
           else {
               return false;
           }
        }
    
        @Override
        public int pop() {
            if(full()){
    throw new EmpyExcetion("栈空了");
            }
            int old = elem[usesize-1];
            usesize--;
            return old;
        }
    
        @Override
        public int peek() {
           if(full()){
               throw new EmpyExcetion("栈空了");
           }
           return elem[usesize-1];
        }
    
        @Override
        public int size() {
            return 0;
        }
    
        @Override
        public boolean empty() {
            return usesize==0;
        }
        public class EmpyExcetion extends RuntimeException{
            public EmpyExcetion(String a) {
                super(a);
            }
        }
    
    }

### 1.4 栈的应用场景 ###

**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

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。  
A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

**2.将递归转化成循环**

比如逆序打印链表:

//递归方式
    void printList(Node head){
      if(null != head){
        printList(head.next);
        System.out.print(head.val + " ");
     }
    }
    
    //循环方式
      Stack<Node> s = new Stack<>();
      // 将链表中的结点保存在栈中
      Node cur = head;
      while(null != cur){
        s.push(cur);
        cur = cur.next;
     }
     // 将栈中的元素出栈
      while(!s.empty()){
        System.out.print(s.pop().val + " ");
     }
    }

通过一些习题加深对栈的理解:

1.括号匹配

[20. 有效的括号 - 力扣（LeetCode）][20. _ - _LeetCode]

class Solution {
        public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for(int i=0; i<s.length(); i++){            //遍历字符串
        char ch = s.charAt(i);                  
        if(ch=='('||ch=='['||ch=='{'){
            stack.push(ch);                     //将左括号压入栈
        }
        else{
            if(stack.empty()){                 
                return false;
            }
            char ch2 = stack.peek();
            if((ch2=='{'&&ch=='}') || (ch2=='('&&ch==')') || (ch2=='['&&ch==']')){
                stack.pop();
            }
            else{
    return false;
            }
        }
    }
    if(!stack.empty()){
        return false;
    }
    return true;
        }
    }

2.逆波兰表达式求值

[150. 逆波兰表达式求值 - 力扣（LeetCode）][150. _ - _LeetCode]

class Solution {
        public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for(String x:tokens){
        if(!Opertion(x)){
            stack.push(Integer.parseInt(x));
        }
        else{
            int a = stack.pop();
        int b = stack.pop();
    switch(x){
    case "+":
    stack.push(a+b);
    break;
    case "-":
    stack.push(b-a);
    break;
    case "*":
    stack.push(a*b);
    break;
    case "/":
    stack.push(b/a);
    break;
    }
        }
    }
    return stack.pop();
        }
    
        public boolean Opertion(String x){
    if(x.equals("*") || x.equals("/") || x.equals("-") || x.equals("+")){
        return  true;
    }
    else{
        return false;
    }
        }
    }

5.验证栈的序列

[946. 验证栈序列 - 力扣（LeetCode）][946. _ - _LeetCode]

class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> pushh =  new Stack<>();
    int j =0;
    for(int i=0; i<pushed.length; i++){
        pushh.push(pushed[i]);
        while(j<pushed.length&& !pushh.empty()&&popped[j]==pushh.peek() ){
    pushh.pop();
    j++;
        }
    }
    return pushh.empty();
        }
    }

6. 最小栈

[155. 最小栈 - 力扣（LeetCode）][155. _ - _LeetCode]

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minstack;
        public MinStack() {
    stack = new Stack<>();
    minstack = new Stack<>();
        } 
        public void push(int val) {
    stack.push(val);
    if(minstack.empty()){
        minstack.push(val);
    }
    else{
        int tem = minstack.peek();
        if(val<=tem){
            minstack.push(val);
        }
    }
        }
        
        public void pop() {
    int tem = stack.pop();
    if(!minstack.empty()){
    if(tem==minstack.peek()){
        minstack.pop();
        }
    }
        }
        
        public int top() { 
            return stack.peek();
        }
        
        public int getMin() {
    if(!minstack.empty()){
        return minstack.peek();
    }
    return -1;
        }
    }

### 1.5 区分概念 ###

栈,虚拟基栈,栈帧有什么区别?

栈是一种数据结构

虚拟基栈是JVM划分的一块内存

栈帧是调用这个方法的时候会在虚拟机中开辟一块内存

## 2.队列(Queue) ##

### 2.1 概念 ###

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行除操作的一端称为队头（Head/Front）.

### 2.2 队列的使用 ###

在java中,Queue是个接口,底层是通过链表实现的.

![265b5790d7bf430aac7ab4eb3d98b56c.png][]

操作方法:

![6e8b5192a309464c8f78f22117c07c63.png][]

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {
      Queue<Integer> q = new LinkedList<>();
      q.offer(1);
      q.offer(2);
      q.offer(3);
      q.offer(4);
      q.offer(5);          // 从队尾入队列
      System.out.println(q.size());
      System.out.println(q.peek());  // 获取队头元素
     
      q.poll();
      System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回
     
      if(q.isEmpty()){
        System.out.println("队列空");
     }else{
        System.out.println(q.size());
     }

![abac210599b94342bf834e7712820304.png][]

### 2.3 模拟实现队列 ###

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。

> 1.  插入和删除操作效率高：LinkedList实现的队列在插入和删除操作时效率更高，因为它的底层数据结构是链表，插入和删除元素时只需要改变指针指向，不需要移动元素。
> 2.  内存占用更灵活：LinkedList实现的队列在添加或删除元素时，不需要像ArrayList一样重新分配内存空间，因此内存占用更加灵活。
> 3.  支持更多操作：LinkedList实现的队列支持更多的操作，如在任意位置插入或删除元素，而ArrayList实现的队列只能在末尾进行插入和删除操作。
> 4.  对于大量的插入和删除操作，LinkedList实现的队列性能更好。但是对于随机访问的操作，ArrayList实现的队列性能更好。

public class Queue {
      // 双向链表节点
      public static class ListNode{
        ListNode next;
        ListNode prev;
        int value;
        ListNode(int value){
          this.value = value;
       }
     }
      ListNode first;  // 队头
      ListNode last;   // 队尾
      int size = 0;
      // 入队列---向双向链表位置插入新节点
      public void offer(int e){
        ListNode newNode = new ListNode(e);
        if(first == null){
          first = newNode;
          // last = newNode;
       }else{
          last.next = newNode;
          newNode.prev = last;
          // last = newNode;
       }
        last = newNode;
        size++;
     }
      // 出队列---将双向链表第一个节点删除掉
      public int poll(){
        // 1. 队列为空
        // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
        // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        int value = 0;
        if(first == null){
          return null;
       }else if(first == last){
          last = null;
          first = null;
       }else{
          value = first.value;
          first = first.next;
          first.prev.next = null;
          first.prev = null;
       }
        --size;
        return value;
     }
      // 获取队头元素---获取链表中第一个节点的值域
      public int peek(){
        if(first == null){
          return null;
       }
        return first.value;
     }
      public int size() {
        return size;
     }
      public boolean isEmpty(){
        return first == null;
     }
    }

### 2.4 双端队列 ###

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象.

**在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。**

Deque<Integer> d1 = new ArrayDeque<>();
    Deque<Integer> d2 = new LinkedList<>();

习题:用队列模拟栈

[225. 用队列实现栈 - 力扣（LeetCode）][225. _ - _LeetCode]

class MyStack {
    Queue<Integer> qu1;
    Queue<Integer> qu2;
        public MyStack() {
    qu1 = new LinkedList<>();
    qu2 = new LinkedList<>();
        }
        
        public void push(int x) {
    if(!qu1.isEmpty()){
    qu1.offer(x);
    }
    else if(!qu2.isEmpty()){
    qu2.offer(x);
    }
    else{
        qu1.offer(x);
    }
        }
        
        public int pop() {
    if(empty()){
        return -1;
    }
    if(!qu1.isEmpty()){
        int size = qu1.size();
        for(int i = 0;i<size-1;i++){
    int x = qu1.poll();
    qu2.offer(x);
        }
        return qu1.poll();
    }
    else{
    int size = qu2.size();
    for(int i= 0; i<size-1 ; i++){
        int x = qu2.poll();
        qu1.offer(x);
    }
    return qu2.poll();
    }
        }
        //
        public int top() {
    if(empty()){
        return -1;
    }
    if(!qu1.isEmpty()){
        int size = qu1.size();
        int x =-1;
        for(int i = 0;i<size ;i++){
    x = qu1.poll();
    qu2.offer(x);
        }
        return x;
    }
    else{
    int size = qu2.size();
    int x = -1;
    for(int i= 0; i<size ; i++){
        x = qu2.poll();
        qu1.offer(x);
    }
    return x;
    }
        }
        //
        public boolean empty() {
    return qu1.isEmpty() && qu2.isEmpty();
        }
    }

[e713505c7ba345eaa59159f6c972071b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/80fd32a79ffc44c7bfbc4545793c8403.png
[04a1c8d379c24754bcacb685ec443ad3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d86a7ff338f54ca79b60728268081c7c.png
[2450fec46ff747afb9299bd1ffec205e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/730e91cbab624a02ac9399b595d723eb.png
[d149a4c45d9c46899cdac406d1cafeac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/99f11232222949f5ad2fb69432a63bdb.png
[25b8ab79292d438f83fe02257d4f0bf0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/94dcb4e13adb4205acc2681741723d7d.png
[20. _ - _LeetCode]: https://leetcode.cn/problems/valid-parentheses/description/
[150. _ - _LeetCode]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
[946. _ - _LeetCode]: https://leetcode.cn/problems/validate-stack-sequences/
[155. _ - _LeetCode]: https://leetcode.cn/problems/min-stack/
[265b5790d7bf430aac7ab4eb3d98b56c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/32990002187f45c6a626d748474f077e.png
[6e8b5192a309464c8f78f22117c07c63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3496176959d8441ca7bedf67d7e4e4c4.png
[abac210599b94342bf834e7712820304.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3a00ae3aa9154d638e799a53605c4498.png
[225. _ - _LeetCode]: https://leetcode.cn/problems/implement-stack-using-queues/