数据结构--------栈和队列_m0

1. 栈

1.1 栈的概念

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

1.2 栈的使用

代码示例：

 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());
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.3 栈的应用场景

1.3.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 B D 都能实现
   正确答案：C
2. 一个栈的状态始终为空，现将元素1,2,3,4,5,A,B,C,D,E依次入栈，然后再依次出栈，则元素出栈的顺序为
   A:12345ABCDE
   B:EDCBA54321
   C:ABCDE12345
   D:54321EDCBA
   正确答案：B

1.3.2将递归转化为循环

比如：逆序打印链表

    //逆序打印链表
    //递归方式
    void printList(Node node){
        if(null!=node){
            printList(node.next);
            System.out.println(node.val+" ");
        }
    }
    //循环方式
    void printList(Node node){
        if(null==node){
            return;
        }
        
        Stack<Node> s=new Stack<>();
        //将链表中的结点保存在栈中
        Node cur=node;
        while(null!=cur){
            s.push(cur);
            cur=cur.next;
        }
        //将栈中的元素出栈
        while(!s.empty()){
            System.out.println(s.pop().val+" ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

1.4 栈的模拟实现

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

import java.util.Arrays;
import java.util.EmptyStackException;
public class Stack<E> {
    E[] array;
    int size;//用来表示栈中总共有多少个元素//size-1表示栈顶元素的位置
    public Stack(){
        array=(E[])new Object[3];
        size=0;
    }

    public void push(E e){
        //1.首先确保栈中空间足够
        ensureCapacity();
        //2.插入元素
        array[size]=e;
        size++;
    }

    private void ensureCapacity(){
        if(size==array.length){
            int newCapacity=size*2;
            array=Arrays.copyOf(array,newCapacity);
        }
    }

    public E peek(){
        if(empty()){
            throw new RuntimeException("pop:栈是空的");
        }
        return array[size-1];
    }
    public boolean empty(){
        return size==0;
    }

    public E pop(){
        E ret=peek();
        size--;
        return ret;
    }

    public static void main(String[] args) {
        Stack<String> s=new Stack<>();
        s.push("1");
        s.push("2");
        s.push("3");
        s.push("4");
        s.push("5");
        System.out.println(s.size);
        System.out.println(s.peek());
        s.pop();
        System.out.println(s.peek());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

1.5 概念区分

栈、虚拟机栈、栈帧有什么区别？
栈：是后进先出的一种数据结构，在Java集合中有对应的实现-----Stack，Stack在实现时继承了Vector。
虚拟机栈：是一块具有特殊作用的内存空间，JVM为了对数据进行更好的管理，将内存按照不同的需要划分出来的一种结构。
栈区：线程是私有的，栈区中存放的是函数调用相关的一些信息，主要是栈帧，当栈区中内存空间不足时，会抛出StackOverflowException，当中的元素(栈帧)是按照数据结构中栈的特性来实现的。
栈帧：一种结构，这种结构是与函数调用相关的。其内部有局部变量表、操作数栈等。
每个方法在运行时，JVM都会创建一个栈帧，然后将栈帧压入到虚拟机栈中；当方法调用结束时，该方法对应的栈帧会从虚拟机栈中出栈。
注意：每个方法的栈帧中结构都是一样的，大小可能不同，栈帧的大小在程序编译时就已经确定好的。

2. 队列

2.1 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列是先进先出的。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

2.2 队列的使用

在Java中，Quene是个接口，底层是通过链表实现的。

队列中所有方法：时间复杂度都是O(1)。

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());//获取队头元素
        System.out.println(q.poll());//从队头出队列，并将删除的元素返回
        if(q.isEmpty()){
            System.out.println("队列为空");
        }else{
            System.out.println(q.size());
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.3 队列模拟实现

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

public class Queue<E> {
    public static class ListNode<E>{
        ListNode<E> next;
        ListNode<E> prev;
        E value;

        ListNode(E value){
            this.value=value;
        }
    }

    ListNode<E> front;//队头
    ListNode<E> last;//队尾
    int size=0;

    //入队列---向双向链表位置插入新节点
    public void offer(E e){
        ListNode<E> node=new ListNode<>(e);
        if(front==null){
            front=node;
        }else{
            last.next=node;
            node.prev=last;
        }
        last=node;
        size++;

    }

    //出队列，将双向链表中的第一个节点删除掉
    public E poll(){
        //分情况考虑
        //1.队列为空
        //2.队列中只有一个元素，链表中只有一个节点，直接删除
        //3.队列中有多个元素，链表中有多个节点，将第一个节点删除
        E value=null;
        if(front==null){
            return null;
        }else if(front==last){
            last=null;
            front=null;
        }else{
            value=front.value;//拿到第一个点的值域
            front=front.next;//front往后走
            front.prev.next=null;//将front的前一个指向空
            front.prev=null;//将front指向空
        }
        --size;
        return value;
    }

    //获取队头元素，获取链表中第一个节点的值域
    public E peek(){
        if(front==null){
            return null;
        }else{
            return front.value;
        }
    }
    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return front==null;
    }

    public static void main(String[] args) {
        Queue<Integer>q=new Queue<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5);
        q.offer(6);
        System.out.println(q.size());
        System.out.println(q.peek());

        q.poll();
        q.poll();
        q.poll();
        q.poll();
        q.poll();
        System.out.println(q.size());
        System.out.println(q.peek());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

接下来思考一个问题队列能使用连续空间实现吗？

1. 入队列：
   使用连续空间实现队列时，可以保证入队列操作的时间复杂度为O(1)。

2. 出队列：
   方式一： 保持front不动，将队头之后所有的元素整体往前搬移一个位置，最后将rear往前走一步。
   
   这样操作的话，时间复杂度为O(N)。
   方式二： 每次出队列时，让front往后移一步
   
   这样操作的话，时间复杂度就是O(1)。

但是又会出现新的问题：

这种情况，我们再去入队列，就已经放不下了，称为队列的假溢出。
真溢出：队列中有效元素已经和空间大小相等了
为了解决使用连续空间实现队列时的假溢出问题，大佬们提出了循环队列。

2.4 循环队列

环形队列通常使用数组实现。

数组下标循环的小技巧

1. 下标最后再往后(offset小于array.length)：index=(index+offset)%%array.length
2. 下标最前再往前(offset小于array.length)：
   index=(index-offset+array.length)%%array.length

那么问题来了，如何检测循环队列是空还是满？这里有三种方式检测：

1. 通过添加size属性记录(使用count计数)
   如果队列空，count=0；如果队列满，count=array.length。
   
2. 保留一个位置，少存储一个元素：
   队列空：front=rear；队列满：(rear+1)%%array.length==front
3. 使用标记
   设置标志位：flag=false
   当入队列时：rear需要向下一个位置移动，同时将flag=true。
   当出队列时：front需要往下一个位置移动，同时将flag=false。

2.5 双端队列(Deque)

双端队列是指允许两端都可以进行入队和出队操作的队列，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。