数据结构 Java数据结构 --- 栈和队列_java中无法解析mystack类怎么处理?

1. 栈(Stack)

1.1 概念

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

Stack的Push和Pop遵循先进后出的原则,如图:

1.2 实现

1. 利用顺序表实现，即使用尾插 + 尾删的方式实现
2. 利用链表实现，则头尾皆可.
   头插法: 入栈O(1) 出栈O(1)
   尾插法: 入栈O(N) 出栈O(N)

相对来说，顺序表的实现上要更为简单一些，所以我们优先用顺序表实现栈。

public class MyStack {
    //简单的实现,使用int元素即可,也不考虑扩容问题
    private int[] elem = new int[100];
    private int usedSize = 0;// 栈中存在多少个有效元素
    
    //入栈
    public void push(int val){
        elem[usedSize] = val;
        usedSize++;
    }
    
    //取栈顶元素(最后进来的那个元素)
    public int peek(){
        return elem[usedSize - 1];
    }
    
    //出栈
    public int pop(){
        int ret = elem[usedSize - 1];
        usedSize--;
        return ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2. 队列(Queue)

2.1 概念

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

2.2 实现

        队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

public class MyQueueByLinkedList {
    /**
     * Node这个类叫做"内部类",定义在某个类或者方法中的类
     * static 效果就是: 创建Node的实例不依赖 MyQueueByLinkedList 这个类的实例
     */
    static class Node{
        public int val;
        Node next = null;

        public Node(int val){
            this.val = val;
        }
    }

    // 创建一个链表,就得有头节点.此处的head节点不是傀儡节点.
    // 基于链表来实现队列,可以入队列可以从尾巴插入,出队列从头部删除;
    // 也可以入队列从头部插入,出队列从尾部删除
    // 无论是那种实现方式,最好都把头和尾都记录下来.
    private Node head = null;
    private Node tail = null;

    // 入队列(标准库的队列,入队列操作就叫 offer)
    public void offer(int val) {
        Node newNode = new Node(val);
        if(head == null){
            head = newNode;
            tail = newNode;
            return;
        }
        //如果非空
        tail.next = newNode;
        tail = newNode;
    }

    // 出队列
    public Integer poll(){
        // 如果当前队列就是空队列,再去poll显然不科学
        if(head == null){
            // 如果出队列失败,返回一个错误的值
            return null;
        }
        int ret = head.val;
        head = head.next;
        if(head == null){
            //删除当前元素之后,队列变成了空的队列
            tail = null;

        }
        return ret;
    }

    // 取队首的元素
    public Integer peek() {
        if(head == null){
            return null;
        }
        return head.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
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

2.3 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。
环形队列通常使用数组实现。

public class MyQueueByArray {
    private int[] elem = new int[100];
    // [head,tail) 有效元素的范围. 注意, tail 可能在 head 之前
    private int head = 0; // 表示对首元素下标
    private int tail = 0; // 表示对尾下一个元素的下标
    private int size = 0; // 元素个数

    public void offer(int val){
        if (size == elem.length) {
            //队列满了, 无法继续插入
            return ;
        }
        // 保证这个操作下标不能越界
        elem[tail] = val;
        tail++;
        // tail ++ 之后如果超出数组有效范围,就从头开始
        if (tail >= elem.length){
            tail = 0;
        }
        size++;
    }

    public Integer poll(){
        if (size == 0){
            return null;
        }
        Integer ret = elem[head];
        head++;
        if(head >= elem.length){
            head = 0;
        }
        size--;
        return ret ;
    }

    public Integer peek(){
        if(size == 0){
            return null;
        }
        return elem[head];
    }
}

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

3. 双端队列 (Deque)

3.1 概念

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

4. java 中的栈和队列

Stack

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        //压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        //查看栈顶元素
        System.out.println(stack.peek());

        //出栈
        int ret = stack.pop();
        System.out.println(ret);  //4
        ret = stack.pop();
        System.out.println(ret);  //3
        ret = stack.pop();
        System.out.println(ret);  //2
        ret = stack.pop();
        System.out.println(ret);  //1
        //判断栈是否为空
        System.out.println(stack.empty());
        //此时栈为空 如果 查看栈顶元素 或者 出栈 会报异常(EmptyStackException)
        System.out.println(stack.peek());
        System.out.println(stack.pop());
    }
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

运行结果:

Queue

Deque

总结:
Stack:
push ,pop,peek.当当前是一个空栈的,再去pop或者peek就会产生异常.
Queue:
add,remove,element 如果当前操作失败就会抛出异常;
offer,poll,peek 如果操作失败就会返回一个错误值;

5. LeetCode 题目

第一题 : 有效的括号

有效的括号
LeetCode 20:
描述:
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

解题思路:

1. 遍历字符串,依次取出字符串中的字符.
      1.1 如果取出的字符串为左括号例如’(‘,’[‘,’{‘.就放入栈中
      1.2 如果取出的字符串为右括号例如’)‘,’]‘,’}'.就和栈顶元素比较是否匹配.
            a) 匹配就出栈,然后继续遍历.
            b) 不匹配就直接返回false
      1.3 如果栈为空,且取出的字符是右括号,则返回false没有例如字符串"]()"
2. 遍历结束后,判断是否栈为空
      2.1 如果为空 则满足题意 return true;
      2.2 如果不为空 表示没有足够匹配的字符, return false; 如字符串"["

画图解析:

代码实现:

    public boolean isValid(String str) {
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');

        //1.先创建一个栈,栈中保存字符类型即可
        Stack<Character> stack = new Stack<>();
        //2.遍历字符串的每个字符
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            //3.判断字符 ch 是否为左括号,如果是,就入栈
            if (ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
                continue;//进入下次循环,取出下一个字符
            }
            if(stack.empty()){
                //如果ch不是左括号,且栈为空,则不是合法括号
                return false;
            }
            //4.判断ch是否是右括号,如果是,就取栈顶元素比较是否相等
            char top = stack.pop();//栈顶元素
            //以下是3种情况合法情况 -- 写法1
            /*if(top == '(' && ch == ')') {
                continue;
            }
            if(top == '[' && ch == ']') {
                continue;
            }
            if(top == '{' && ch == '}') {
                continue;
            }*/
            // 判断合法情况 -- 写法2
            if(map.get(top) == ch){
                continue;
            }
            //如果三种情况都不满足,表示不是合法情况
            return false;
        }
        //遍历完成后 如果栈为空 则满足条件
        if(stack.empty()) {
            return true;
        }
        //否则就不合法
        return false;
    }
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

第二题 : 用队列实现栈

用队列实现栈
LeetCode 225:
描述:
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

解题思路:

1. 用两个队列来模拟一个栈的效果,引用两个队列 A 和 B .
2. 入栈 : 直接把元素入队到A中即可
3. 出栈 : 因为队列是先进先出的,栈是后进先出的,可以让 A队列 元素出队列然后入队列到 B队列 中,直到A队列中最后一个元素的时候,直接出队列,就实现了后进先出.然后要让A和B交换,始终让入栈到A队列中.
4. 取栈顶元素 : 取栈顶元素就是 出栈 的元素, 不过取栈顶元素要把这个元素返回去
5. 判断是否为空 : A 和 B都为空的时候 就是空栈

画图解析:

代码实现:

import java.util.LinkedList;
import java.util.Queue;

public class MyStackByDoubleQueue {
    private Queue<Integer> A = new LinkedList<>();
    private Queue<Integer> B = new LinkedList<>();

    public void push(int x) {
        // x往A中入队列即可
        A.offer(x);
    }

    public Integer pop() {
        if (empty()){
            return null;
        }
        // 把A中的元素往 B 中放
        while(A.size() > 1) {
            Integer font = A.poll();
            B.offer(font);
        }
        //当循环结束后,A 中 应该只剩1个元素
        //这个元素就应该是被出栈的元素
        int ret = A.poll();
        //交换A和B
        swapAB();
        return ret;
    }

    private void swapAB(){
        Queue<Integer> tmp = A;
        A = B;
        B = tmp;
    }

    public Integer top() {
        if (empty()){
            return null;
        }
        // 把A中的元素往 B 中放
        while(A.size() > 1) {
            Integer font = A.poll();
            B.offer(font);
        }
        //当循环结束后,A 中 应该只剩1个元素
        //这个元素就应该是被出栈的元素
        int ret = A.poll();
        B.offer(ret); // top 和 pop的区别就是 top要把元素返回去,pop不需要返回去
        //交换A和B
        swapAB();
        return ret;
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}
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

第三题 : 用栈实现队列

用栈实现队列
LeetCode 232:
描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

解题思路:

1. 引用2个栈A和B,A专门用来入队列;B专门用来出队列
2. 实现入队列: 先把B中的所有元素都放到A中(因为出栈的时候元素会放入B中),然后直接往A里入栈.
3. 实现出队列: 后进先出的栈实现先进先出的队列,要让A中的所有元素移入B中,先出的的元素就是后进的,此时栈顶就是就是最先进入的元素,B中出栈操作即可
4. 实现取队首元素: 同出队列操作,把A所有元素放入B中,然后取B的栈顶元素就是队首元素.
5. 判空: A 和 B 都为空.

画图解析:

代码实现:

import java.util.Stack;

public class MyQueueByDoubleStack {
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();

    public void push(int x) {
        //1.先将B中的元素 放入 A 中
        while (!B.isEmpty()){
            int tmp = B.pop();
            A.push(tmp);
        }
        //2.把新元素放入A中
        A.push(x);
    }


    public Integer pop() {
        //1.如果为空 直接返回
        if(empty()){
            return null;
        }
        //2.把A中的元素都给B
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.针对B进行出栈
        return B.pop();
    }

    public Integer peek() {
        //1.如果为空 直接返回
        if(empty()){
            return null;
        }
        //2.把A中的元素都给B
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.取B的栈顶元素
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

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

第四题 : 最小栈

最小栈
LeetCode 155:
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

解题思路:

1. 引用2个栈A和B, A按照正常栈的规则入栈出栈,B存放的是A的最小值以及A历史的最小值
2. 实现入栈操作: A中: 直接入栈 . B中: 取要入栈的值 和 B栈顶元素比较,把较小值入栈到B中.
3. 实现出栈操作: A 和 B 一起出栈
4. 实现取栈顶元素操作: 直接取 A 栈顶元素
5. 实现取最小值操作: 直接取 B 栈顶元素

画图解析:

代码实现:

import java.util.Stack;

public class MinStack {
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();

    public void push(int x){
        //A 直接入栈
        A.push(x);
        //如果B为空 直接入栈
        if(B.isEmpty()){
            B.push(x);
            return;
        }
        //如果B不为空,比较x和B栈顶的较小值,将较小值入栈
        int min = B.peek();
        min = min < x ? min : x;
        B.push(min);
    }

    public Integer pop(){
        //如果A为空 直接返回
        if(A.isEmpty()){
            return null;
        }
        //B和A同时出栈
        B.pop();
        return A.pop();
    }

    public Integer top(){
        //如果A为空 直接返回
        if(A.isEmpty()){
            return null;
        }
        return A.peek();
    }

    public Integer getMin(){
        //如果B为空 直接返回
        if(B.isEmpty()){
            return null;
        }
        //B的栈顶即使最小元素
        return B.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

第五题 : 设计循环队列

设计循环队列
LeetCode 622:
描述:
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

解题思路:

1. 循环队列 运用数组实现. head和tail是下标,head位置始终都是队首的元素;tail位置始终都是队尾的下一个元素 有效元素个数[ head, tail) 左闭右开
2. 入队列 : 把新元素放到 tail 位置上,同时 tail++.
3. 出队列 : 取出 head 位置的元素,同时 head++.
4. 空队列 : 有效元素个为0
5. 满队列 : 有效元素个数等于数组长度
6. 注意当head 和 tail达到 元素上线时,回到最开始的位置.

画图解析:

代码实现:

public class MyCircularQueue {
    private int[] elem;
    private int head = 0;//队首元素下标
    private int tail = 0;//队尾下一个元素下标
    private int size = 0;//有效元素个数

    /**
     * 构造器，设置队列长度为 k 。
     * @param k 队列长度
     */
    public MyCircularQueue(int k) {
        this.elem = new int[k];
    }

    /**
     * 向循环队列插入一个元素。如果成功插入则返回真。
     * @param value 插入元素
     * @return
     */
    public boolean enQueue(int value) {
        //队满就无法入队 返回false
        if(size == elem.length){
            return false;
        }
        elem[tail] = value;
        tail++;
        //tail>=队列长度 要归零
        if(tail >= elem.length){
            tail = 0;
        }
        size++;
        return true;
    }

    /**
     * 从循环队列中删除一个元素。如果成功删除则返回真。
     * 队头出
     * @return
     */
    public boolean deQueue() {
        //如果队列为空 没有要删除的返回false
        if(size == 0){
            return false;
        }
        head++;
        //head>=队列长度 要归零
        if(head >= elem.length){
            head = 0;
        }
        size--;
        return true;
    }

    /**
     * 从队首获取元素。如果队列为空，返回 -1 。
     * @return
     */
    public int Front() {
        if(size == 0){
            return -1;
        }
        return elem[head];
    }

    /**
     * 获取队尾元素。如果队列为空，返回 -1 。
     * @return
     */
    public int Rear() {
        if(size == 0){
            return - 1;
        }
        if(tail==0) return elem[elem.length - 1];
        return elem[tail-1];
    }

    /**
     * 检查循环队列是否为空。
     * @return
     */
    public boolean isEmpty() {
        if(size == 0){
            return true;
        }
        return false;
    }

    /**
     * 检查循环队列是否已满
     * @return
     */
    public boolean isFull() {
        if(size == elem.length){
            return true;
        }
        return false;
    }

}

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
88
89
90
91
92
93
94
95
96
97
98
99
100

第六题 : 逆波兰表达式求值(后缀表达式)

后缀表达式
逆波兰表达式求值
LeetCode 150:
剑指 Offer Ⅱ 036:
描述:
根据 逆波兰表示法，求表达式的值。

有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

解题思路:

1. 中缀记法 是一个通用的算术或逻辑公式表示方法,中缀表达式如3 + 4
前缀表达式如+ 3 4 , 后缀表达式如3 4 +. 前缀和后缀表达式都表示3+4
2. 用栈解决逆波兰表达式, 遍历字符数组
      ① 如果为数字 入栈
      ② 如果为 +、-、*、/ 出栈两个数字 完成对应操作,然后将得到的数据 入栈
3. 注意完成对应 +、-、*、/ 操作时,是后一个出栈的数据 +、-、*、/ 前一个出栈的数据

画图解析:

代码实现:

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        //遍历
        for (int i = 0; i < tokens.length; i++) {
            if("+".equals(tokens[i])){
                // '+' 运算
                stack.push(stack.pop() + stack.pop());
            }else if ("-".equals(tokens[i])){
                // '-' 运算
                stack.push(-stack.pop() + stack.pop());
            }else if ("/".equals(tokens[i])){
                // '/' 运算 
                int m = stack.pop();
                int n = stack.pop();
                stack.push(n / m);
            }else if ("*".equals(tokens[i])){
                // '*' 运算
                stack.push(stack.pop() * stack.pop());
            }else{
                // 不是运算符 直接入栈
                stack.push(Integer.valueOf(tokens[i]));
            }
        }
        //遍历结束 出栈即是结果
        return stack.pop();
    }
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