Java~数据结构（三）~栈和队列（Stack\Queue\Deque的常用方法和模拟实现一个栈和队列等）

知识框架

• 栈和队列本质上都是线性表，只不过是特殊的线性表，操作收到了限制。
• 栈是线性表只允许在一端进出，而队列是线性表只允许一端进，一端出。
• Java中有栈的具体类Stack，而队列（Queue）只是定义了接口，所有实现了这个接口的具体类都可以当做一个队列来使用。

栈（Stack）

• 什么是栈？栈是一种特殊的线性表。只能在表的一端进行插入和删除。可以进行数据插入和删除的一端称为栈顶。另一端称为栈底。
• 栈中的元素遵循“先进后出”原则。（也就是后进先出，Last In First Out，所以也称为LIFO结构）
• 空栈：不含有任何元素的空表。
  

如何实现一个栈？

• 在Java中，实现栈有两个方法：一个是Java本身的集合类型Stack类型。另一个是借用LinkedList来间接实现栈（其实链表或者数组都可以间接实现一个栈的功能，LinkedList就是链表，下面会用数组模拟实现一个栈）。
• Stack集合类型继承于Vector，由于Vector是通过数组实现的，所以Stack集合类型也是通过数组来实现的。
  
• 注意：我们平时所说的栈，是一种按照先入后出的线性存储结构。这种结构不仅用Java可以写，用C++也可以写。在Java中的栈，有两种实现方式，一种是本身的集合Stack，我们平常说的也就是这种。另一种就是用别的实现类来实现这种功能，比如LinkedList。（平时的Stack就是指Stack集合类型。而不是栈这种更广泛的概念。）
• LinkedList是双向链表，不仅仅能用来实现栈，还可以被用来实现队列或者双端队列。是一个比较“全能”的数据结构。因为LinkedList实现了List接口，所以可以进行队列的操作，还实现了Deque接口，所及还能当做双端队列使用。

栈（Stack）常用方法

常用方法使用：

使用1：
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());//获取栈顶元素，但是不弹出。
        stack.pop();//出栈，元素4出栈，栈中剩余元素3,2,1
        System.out.println("获取栈中的元素："+stack.pop());
        System.out.println("栈中有效元素个数："+stack.size());//获取栈的长度
        System.out.println("stack是否为空："+stack.isEmpty());//判断栈是否为空
    }

模拟实现一个栈（包括栈常用方法）

class MyStack{
    private int[] arr;

    //size记录数组中元素个数
    private int size;

    public MyStack(){
        this(12);//调用无参构造，默认最大容量12
    }
    public MyStack(int MaxSize){
        this.arr=new int[MaxSize];
    }

    //入栈
    public int push(int value){
        if(this.size == arr.length){
            //栈满 需要扩容

            int[] copyArr;
            //复制数组arr,数组扩充一倍
            copyArr=Arrays.copyOf(arr,2*arr.length);
            arr=copyArr;
        }

        //将元素添加到size位置
        this.arr[size]=value;
        //元素个数+1;
        this.size++;
        //返回添加元素
        return value;
    }

    //出栈
    public int pop(){
        if(this.size == 0){
            //没有元素
            //抛出时运行异常，此处也可以自定义异常。
            throw new RuntimeException("栈中没有元素，不能出栈..");
        }
        //获得栈顶元素
        int value=this.arr[size-1];
        //size-1之后，下一次插入时会覆盖原数据，利用覆盖替代删除。
        this.size--;
        return value;
    }
    //获取栈顶元素(peek)
    public int peek(){
        if(this.size == 0){
            //没有元素
            //抛出时运行异常，此处也可以自定义异常。
            throw new RuntimeException("栈中没有元素，不能出栈..");
        }
        return this.arr[this.size - 1];
    }
    //获取元素个数
    public int getSize(){
        return this.size;
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return this.size==0;
    }
    
}

单向队列（Queue）和双端队列（Deque）

• 什么是队列？只允许在一端进行插入数据，在另一端进行删除数据的特殊线性表。进行插入操作的一端是队尾。进行删除操作的一端是队头。
• 队列具有先进先出的特性。
  
• 详细图：

• Java中有单向队列（Queue）和双向队列（Deque），Queue是个接口，实现了队列的基础方法。Deque是在继承Queue的基础上，增加了反向队列的方法，也包括栈的基础方法。
  
  
• （上图）Java中虽然有Queue接口，但是Java并没有给出具体的实现类（栈是直接给出了Stack实现类），而是让LinkedList实现了Queue接口，所以一般用LinkedList来实现链表。

单向队列Queue常用方法

• 注意：Queue中插入和删除都有两个方法可以实现，当我们使用队列时，通常采用offer添加元素和poll删除元素。不适用add与remove方法。

使用：

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()); // 获取元素个数 输出5

        System.out.println("获取队头元素 : "+q.peek()); // 获取队头元素,但不删除元素
        q.poll();
        System.out.println("出队列元素 : "+q.poll()); // 从队头出队列，并将删除的元素返回

        if(q.isEmpty()){
            System.out.println("队列空");
        }else{
            System.out.println("元素个数 : "+q.size());
        }
    }

双向队列Deque常用方法

循环队列

• 实际使用时，可能还会接触到循环队列，循环队列一般用数组实现。就是首尾相连。
• 使用循环队列可以解决用数组实现队列时的空间浪费问题。

• 代码实现：

public class MyCircularQueue {

    private final int[] elem;
    private int front;      //队头下标
    private int rear;       //队尾下标
    private int size;

    public MyCircularQueue() {
        elem = new int[24];
    }

    //入队列
    public void offer(int val){
        if(size == elem.length){
            //可扩容,此处不实现
            throw new RuntimeException("队列已满...");
        }
        elem[rear] = val;
        //如果rear到达数组长度,则置0
        if(rear + 1 >= elem.length){
            rear = 0;
        }else {
            rear++;
        }
        size++;
    }

    public int poll(){
        if(size == 0){
            throw new RuntimeException("队列为空...");
        }
        int val = elem[front];
        if(front + 1 >= elem.length){
            front = 0;
        }else {
            front++;
        }
        size--;
        return val;
    }

    //判断元素个数
    public int size(){
        return size;
    }

    //获取队首元素
    public int peek(){
        if(size == 0){
            throw new RuntimeException("队列为空...");
        }
        return elem[front];
    }

    // 判断是否为空
    public boolean isEmpty(){
        return size == 0;
    }
}