节点学院
百 M 栈和队列
2021-01-28 19:32:02 50/100 庶卒 参与编辑 0 版本： 1 引用率 22.60%

栈和队列

本章讲述栈、队列和优先级队列

不同的结构类型

栈、队列和之前讲的数组有很大的区别

程序员的工具

栈和队列更多是用作程序员的工具，它们作为构思算法的辅助工具，而不是完全的数据存储工具。这些数据结构的生命周期比数据库类型的结构要短得多，在程序执行期间它们才被创建，通常用它们去执行某项特殊的业务，执行完成之后，它们就被销毁。

受限访问

在数组中，如果知道下标，便可以立刻访问该数据项，或者通过顺序搜索数据项。而栈和队列，访问是受限的，即在特定时刻，只有一个数据项可以被读取或者删除。

访问其他数据项，理论上是不可以的。

更加抽象

栈、队列是比数组更抽象的结构。

栈

栈（英语：stack）又称为堆栈或堆叠，栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。

这里以羽毛球筒为例，羽毛球筒就是一个栈，刚开始羽毛球筒是空的，也就是空栈，然后我们一个一个放入羽毛球，也就是一个一个push进栈，当我们需要使用羽毛球的时候，从筒里面拿，也就是pop出栈，但是第一个拿到的羽毛球是我们最后放进去的。

image.png

栈的方法

  1. void push(Object value) 入栈
  2. Object pop() 出栈
  3. Object peek() 访问栈顶元素
  4. boolean isEmpty() 是否为空
  5. boolean isFull() 是否满了

用数组模拟栈

public class MyStack {
    private int[] array;
    private int maxSize;
    private int top;
    public MyStack(int size) {
        this.maxSize = size;
        array = new int[size];
        top = -1;
    }
    //压入数据
    public void push(int value) {
        if(top < maxSize - 1) {
            array[++top] = value;
        }
    }
    //弹出栈顶数据
    public int pop(){
        return array[top--];
    }
    //访问栈顶数据
    public int peek(){
        return array[top];
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return (top == -1);
    }
    //判断栈是否满了
    public boolean isFull(){
        return (top == maxSize-1);
    }
}

算法题

1、利用栈判断分隔符是否匹配

给出一个仅包含字符’(’,’)’,’{’,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。

import java.util.*;
import java.util.Stack;
public class Solution {
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        Stack<Character> c = new Stack<Character>();
        for(int i = 0 ; i < s.length(); i++){
            if(c.empty()){
                c.push(s.charAt(i));
                continue;
            }
            if(s.charAt(i)==')'&&c.peek()=='('){c.pop();}
            else if(s.charAt(i)=='}'&&c.peek()=='{'){c.pop();}
            else if(s.charAt(i)==']'&&c.peek()=='['){c.pop();}
            else{ c.push(s.charAt(i));}
        }
        return c.empty();
    }
}

队列

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

比如我们去电影院排队买票，第一个进入排队序列的都是第一个买到票离开队列的人，而最后进入排队序列排队的都是最后买到票的。

image.png

在比如在计算机操作系统中，有各种队列在安静的工作着，比如打印机在打印列队中等待打印。

队列的基本操作插入和删除

插入时从在队头插入，删除时在队尾删除

image.png

队列分为：

  1. 单向队列（Queue）：只能在一端插入数据，另一端删除数据。
  2. 双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。

这里我们还会介绍一种队列——优先级队列，优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

用数组模拟队列

初始化一个10个空间的数组

[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
 0   1   2   3   4   5   6   7   8   9
// 队头小标 0
// 队尾下标 0

从下标0开始插入三个数据 1、2、3
[1] [2] [3] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
 0   1   2   3   4   5   6   7   8   9
// 队头下标 0
// 队尾下标 2

// 移除一个数据
[ ] [2] [3] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
 0   1   2   3   4   5   6   7   8   9
// 队头下标 1
// 队尾下标 2

可以发现，使用数组模拟队列时，当发生移除操作后，队头的下标将不再是已0开头

image.png

参考文章

  1. https://www.cnblogs.com/ysocean/p/7911910.html

评论