数据结构初阶（栈和队列）_栈 队列 同时

一、栈

1.1 什么是栈

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

1.2 栈的使用

（1）结构

1.栈的抽象数据结构
对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对
它在操作会有些变化。特别是插入和删除操作，我们改名为 push 和 pop

2. 栈的存储结构及其实现
由于栈本身就是个线性表，那么线性表的顺序存储和链式存储，对于栈来说，也是同样适用的

2.1 栈的顺序存储结构及其实现

---

【1】结构

import java.util.Arrays;

public class MyStack {
    private int[] elem;     //stack的底层是数组
    private int usedSize;

    public MyStack() {
        this.elem = new int[5];
    }
}
1
2
3
4
5
6
7
8
9
10

---

【2】进栈操作

	//进栈
	public void push(int val) {
	    if(isFull()) {      //判断里面的空间是否为满的情况
	       elem = Arrays.copyOf(elem,2*elem.length);
	    }
	    elem[usedSize] = val;
	    usedSize++;
	}
	
	public boolean isFull() {
	    return usedSize == elem.length;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13

---

【3】出栈操作

  //出栈
  public int pop() {
      //1、判断栈不为空
      if(empty()) {
          //抛出异常！！
          throw new StackEmptyException("栈为空！");
      }
      //2、开始删除
      return elem[--usedSize];     
      //elem[useSize]的数字没有被删掉，后续如果有push的话，会把值该赋给掉
  }

1
2
3
4
5
6
7
8
9
10
11
12

---

【4】获取栈顶元素

    //获取栈顶元素
    public int peek() {
        //1、判断栈不为空
        if(empty()) {
            //抛出异常！！
            throw new StackEmptyException("栈为空！");
        }
        //2、开始删除
        return elem[usedSize-1];
    }

    public boolean empty() {
        return usedSize == 0;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2 栈的链式存储结构及实现

---

【1】结构

对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是 top = null的时候。

---

【2】进栈操作

---

【3】出栈操作

2.3 栈的两种结构对比

• 它们在时间复杂度上是一样的，均为O(1)
• 对于空间性能， 顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制
• 总结
  • 如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

（2）方法

（3）栈的应用

• 改变元素的序列
  • 进栈过程中可以出栈 和 依次入栈，然后再依次出栈 对元素出栈的顺序的改变
• 将递归转化为循环

原理：递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。
这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此编译器用栈实现递归

简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

	// 递归方式
	void printList(Node head){
		if(null != head){
			printList(head.next);
			System.out.print(head.val + " ");
		}
	}
	
	// 循环方式
	void printList(Node head){
		if(null == head){
			return;
		}
		
	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
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

• 逆波兰表达式求值

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}
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

• 有效的括号

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;
                }else {
                    char tmp = stack.peek();
                    if (ch == ')' && tmp == '(' || ch == '}' && tmp == '{' 
                        || ch == ']' && tmp == '[') {
                            stack.pop();
                        }else {
                            return false;
                        }
                }
            }
        }

        if (!stack.empty()) {
            return false;
        }

        return true;
    }
}
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

• 栈的压入、弹出序列

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (!stack.empty() && j < popA.length
                    && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 最小栈

class MinStack {
private Stack<Integer> stack ;
    private 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 {
            if(val <= minStack.peek()) {
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        //栈为空 则不能进行弹出元素
        if(stack.empty()) {
            return;
        }
        int val = stack.pop();
        if(val == minStack.peek()) {
            minStack.pop();
        }
    }
    //获取栈顶元素 和 最小栈没有关系
    public int top() {
        if(stack.empty()) {
            return -1;
        }
        return stack.peek();
    }

    //获取元素 不是删除元素
    public int getMin() {
        return minStack.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

栈、虚拟机栈、栈帧有什么区别呢？

栈是数据结构
虚拟机栈是内存
栈帧是调用方法是，在虚拟机栈开辟的一个内存

二、队列

2.1 什么是队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）
抽象场景：食堂排队买饭、移动客服服务客人、键盘输入

2.2 队列的使用

（1）底层代码的实现

在Java中，Queue是个接口，底层是通过链表实现的
队列可以通过数组和链表实现

• 如果是双向链表，那么入队和出队，均可以达到O(1)，不管从哪边进
• 如果是单链表，并且记录了最后一个节点的位置的情况下，我们可以采用从尾入队，从头出队的方式，都是O(1)。如果是从头进，从尾出，那么出队的复杂度为O(n)

（2）队列的使用

❤️创建
Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

Queue<Integer> q = new LinkedList<>();
1

❤️方法

❤️队列的模拟实现

• 顺序结构
  双向链表

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 -1;
        }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 -1;
        }
        return first.value;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }
}
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

单向链表

public class MyQueue {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;

    private int usedSize;

    public void offer(int val) {
        ListNode node = new ListNode(val);
        if(head == null) {
            head = node;
            last = node;
        }else {
            last.next = node;
            last = last.next;
        }
        usedSize++;
    }

    public int getUsedSize() {
        return usedSize;
    }

    public int poll() {
        if(head == null) {
            return -1;
        }
        int val = -1;
        if(head.next == null) {
            val = head.val;
            head = null;
            last = null;
            return val;
        }
        val = head.val;
        head = head.next;
        usedSize--;
        return val;
    }

    public int peek() {
        if(head == null) {
            return -1;
        }
        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

• 循环结构

环形队列通常使用数组实现
对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除 的时间复杂度变成了O(1)

class MyCircularQueue {
    private int[] elem;
    private int front;//队头下标
    private int rear;//队尾下标

    public MyCircularQueue(int k) {
        this.elem = new int[k+1];
    }

    //入队
    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear+1) % elem.length;
        return true;
    }

    //出队
    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        front = (front+1) % elem.length;
        return true;
    }

    //得到队头元素
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    //得到队尾元素
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = (rear == 0) ? elem.length-1 : rear-1;
        return elem[index];
    }
    
    public boolean isEmpty() {
        return rear == front;
    }
    
    public boolean isFull() {
        return (rear+1) % elem.length == front;
    }
}
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

解析

• 数组下标循环：
  下标最后再往后：(rear + 1) % elem.length;
  下标最前再往前：(front + 1) % elem.length;
• 如何区分空和满：
  满：
  通过添加 useSize 属性记录,当useSIze == len 的时候为满
  保留一个位置，用这个位置来表示满
  使用标记
  空： front == rear 时为空

2.3 双端队列

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

• Deque是一个接口，使用时必须创建相关的对象。

Deque<Integer> stack = new ArrayDeque<>();  双端队列的线性实现，底层是数组
Deque<Integer> queue = new LinkedList<>();  双端队列的链式实现，底层是链表
1
2

2.4 练习

一、用队列实现栈

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

class MyStack {

    private Queue<Integer> qu1;
    private 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 currentSize = qu1.size();
            for (int i = 0; i < currentSize-1; i++) {
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();//最后一个数据返回
        }
        if(!qu2.isEmpty()) {
            int currentSize = qu2.size();
            for (int i = 0; i < currentSize-1; i++) {
                int x = qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();//最后一个数据返回
        }
        return -1;
    }
    //peek方法
    public int top() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int currentSize = qu1.size();
            int x = -1;
            for (int i = 0; i < currentSize; i++) {
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;//最后一个数据返回
        }
        if(!qu2.isEmpty()) {
            int currentSize = qu2.size();
            int x = -1;
            for (int i = 0; i < currentSize; i++) {
                x = qu2.poll();
                qu1.offer(x);
            }
            return x;//最后一个数据返回
        }
        return -1;
    }
    
    public boolean empty() {
        return qu1.isEmpty() && qu2.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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

二、用栈实现队列

class MyQueue {

    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if(!s2.empty()) {
            return s2.pop();
        }else {
            while(!s1.empty()) {
                int val = s1.pop();
                s2.push(val);
            }
            return s2.pop();
        }
    }
    
    public int peek() {
        if(!s2.empty()) {
            return s2.peek();
        }else {
            while(!s1.empty()) {
                int val = s1.pop();
                s2.push(val);
            }
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}
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