数据结构系列五：栈和队列

一、栈

（一）概念

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

栈在现实生活中的例子：

（二）栈的使用

我们可以看到Java中的Stack给了如下方法

import java.util.Stack;

public class test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        System.out.println(stack.peek());//看一下栈顶的元素但是不删除
        System.out.println(stack.pop());//删除栈顶元素
        System.out.println(stack.peek());//看一下栈顶的元素但是不删除
        System.out.println(stack.isEmpty());//判断栈是否为空
        System.out.println(stack.size());//栈中元素个数
    }
}

//输出结果
34
34
23
false
2

Process finished with exit code 0

（三）栈的模拟实现

栈的底层实际上就是一个数组，接下来我们来实现一下其中的操作

添加元素

//往栈中添加元素
    public void push(int val){
        if (isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        this.usedSize++;
    }

判断是否为空栈

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

弹出元素

public int pop(){
        if (isEmpty()){
            throw new no();
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        return oldVal;
    }

返回栈顶元素

public int peek(){
        if (isEmpty()){
            throw new no();
        }
        return elem[usedSize-1];
    }

（四）利用栈的特性逆序打印链表

在一个链表中，我们可以利用栈的特性，先进后出，来逆序打印这个链表

 public void reservePrintList(){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()){
           ListNode top =  stack.pop();
            System.out.print(top.val + " ");
        }
    }

二、队列

（一）概念

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

（二）队列的使用

public static void main(String[] args) {
        Queue<Integer> queue1 = new LinkedList<>();//单向队列
        Deque<Integer> queue2 = new LinkedList<>();//双端队列
        queue1.offer(1);
        queue1.offer(2);
        queue1.offer(3);//从队尾入队列
        System.out.println(queue1.poll());//从队头出队列
        System.out.println(queue1.peek());//看一眼队头元素
        System.out.println(queue1.isEmpty());//判断队列是否为空
    }
//输出结果
1
2
false

Process finished with exit code 0

（三）队列的模拟实现

队列中既然可以存储元素，那么底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构，从实际情况来看，链式结构操作队列相对简单一些

插入元素

//头插法
    public void offer(int x){
        ListNode node = new ListNode(x);
        if (front == null){
            front = rear = node;
        }else {
            node.next = front;
            front.prev = node;
            front = node;
        }
        usedSize++;
    }

删除元素

//出队列
    public int poll() {
        if (front == null) {
            return -1;
        }
        int ret = front.val;
        if (front == rear) {
            front = null;
            rear = null;
            usedSize--;
            return ret;
        }
        front = front.next;
        front.prev = null;
        usedSize--;
        return ret;
    }

获取队头元素

public int peek(){
        if (front == null){
            return -1;
        }
        return front.val;
    }

求出队列长度

public int getUsedSize(){
        return usedSize;
    }

判断是否为空

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

三、循环队列

环形队列通过循环利用存储空间，避免了普通队列中因元素出队而导致的空间浪费问题。在普通队列中，当队列头部的元素被移除后，前面的存储空间无法再被利用，而环形队列则可以将这些空闲的空间重新用于存储新的元素

循环队列的方法

public class MuCircularQueue {
    private int[] elem;
    private int front;
    private int rear;

    public MuCircularQueue(int k){
        //采用浪费一个位置来判断是否为满，所以要多开辟一个格子的空间
        this.elem = new int[k+1];
    }
    public boolean isEmpty(){
        return  front == rear;
    }
    public boolean isFull(){
        if ((rear+1)%elem.length == front){
            return true;
        }
        return false;
    }
    //入队操作
    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  index;
    }
}

四、双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队

Deque是一个接口，使用时必须创建LinkedList的对象

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

public class demo {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
        Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
        stack.push(1);
        stack.pop();

        queue.offer(1);
        queue.poll();
    }
}