Stack和Queue

1. 栈(Stack)

1.1 概念

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

1.2 栈的使用

import java.util.Stack;
public class Test {
    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.size());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        if (stack.isEmpty()) {
            System.out.println("栈空");
        } else {
            System.out.println(stack.size());
        }
    }
}

1.3 栈的模拟实现

import java.util.Arrays;

public class MyStack {
    int[] array;
    int size;

    public MyStack() {
        array = new int[3];
    }

    public int push(int e) {
        array[size++] = e;
        return e;
    }

    public int pop() {
        int e = peek();
        size--;
        return e;
    }

    public int peek() {
        if (empty()) {
            throw new RuntimeException("栈空");
        }
        return array[size - 1];
    }


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

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

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

栈 是数据结构的一种，用于存储数据；

虚拟机栈 是虚拟机执行程序时使用的栈空间；

栈帧 是具体的函数调用所使用的栈空间，用于存储函数执行所需的信息。

2. 队列(Queue)

2.1 概念

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

2.2 队列的使用

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

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

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

public class Test {
    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());
        }
    }
}

2.3 队列模拟实现

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

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 循环队列

如何区分空与满

1. 通过添加 size 属性记录

2. 保留一个位置

3. 使用标记

队空：

public boolean isEmpty() {
        return front == rear;

    }

队满：

public boolean isFull() {
        return ((rear + 1) % capacity) == front;
    }

队头元素：

public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];

    }

队尾元素：

 public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];

    }

进队：

public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

出队：

public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }

        front = (front + 1) % capacity;
        return true;
    }

完整代码：

class MyCircularQueue {

    int front;
    int rear;
    int[] elements;
    int capacity;

    public MyCircularQueue(int k) {
        front = 0;
        rear = 0;
        capacity = k + 1;
        elements = new int[capacity];

    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }

        front = (front + 1) % capacity;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];

    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];

    }

    public boolean isEmpty() {
        return front == rear;

    }

    public boolean isFull() {
        return ((rear + 1) % capacity) == front;
    }
}

3.双端队列

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

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

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现