目录

一、栈（Stack）

1.概念

2.栈的使用

3.栈的模拟实现

初始化

压栈（入栈）

弹出栈顶元素（出栈）

peek操作

获取栈元素个数

栈的练习--反转链表

二、队列（Queue）

概念

队列的使用

队列的模拟实现

初始化

入队

出队

peek() 

判断队列是否为空

循环队列

循环结构

代码实现

初始化

isFull() 和 isEmpty()

入队

出队

peek()

获取队尾元素

三、双端队列

概念

---

一、栈（Stack）

1.概念

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

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

2.栈的使用

3.栈的模拟实现

底层用数组

初始化

    public int[] elem;
    //当前栈 当中 存储的有效的数据个数  也可以当中  当前可以存放数据元素的下标
    public int usedSize;
 
    public static final int DEFAULT_CAPACITY = 10;
 
    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
    }

压栈（入栈）

在进行此步操作是需要判断数组是否已满，来确定是否需要扩容操作。

/**
     * 压栈
     */
    public void push(int val) {
        //1、判断栈是否是满的
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //存放到当前的下标，同时usedSize需要自增
        elem[usedSize] = val;
        usedSize++;
    }
 
    /**
     * 判断 当前栈是否是满的
     * @return
     */
    public boolean isFull() {
        if(usedSize == elem.length) {
            return true;
        }
        return false;
    }

弹出栈顶元素（出栈）

此步需要判断此时栈是否为空，以为栈为空的话无法弹出元素。

    /**
     * 删除栈顶元素
     * @return
     */
    public int pop(){
        if(isEmpty()) {
            throw new EmptyStackException("栈为空了！");
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        return oldVal;
    }
 
    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
        return usedSize == 0;
    }

peek操作

这里也需要判空。

    /**
     * 获取栈顶元素 但是不删除
     * @return
     */
    public int peek() {
        if(isEmpty()) {
            throw new EmptyStackException("栈为空了！");
        }
        return elem[usedSize-1];
    }

获取栈元素个数

因为我每一次入栈usedSize都会++，所以这里直接返回usedSize就行了。

    public int getUsedSize() {
        return usedSize;
    }

栈的练习--反转链表

 思路：因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。

public ListNode ReverseList(ListNode head) {
    Stack stack= new Stack<>();
 
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
 
    if (stack.isEmpty()) {
        return null;
    }
        
    ListNode node = stack.pop();
    ListNode dummy = node;
 
    //栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
 
    //要让最后一个节点的next等于空，否则会构成环
    node.next = null;
    return dummy;
}

二、队列（Queue）

概念

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

队列的使用

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

注意：

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

队列的模拟实现

刚才说了队列是一个接口，底层是通过链表来实现的，这里我也是通过链表实现的。

初始化

    static class Node {
        public int val;
        public Node next;
        public Node(int val) {
            this.val = val;
        }
    }
 
    public Node head;//队列的头
    public Node tail;//队列的尾

入队

    /**
     * 入队操作
     * @param val
     */
    public void offer(int val) {
 
        Node node = new Node(val);
        if(head == null) {
            head = node;
            tail = node;
        }else {
            tail.next = node;
            tail = tail.next;
        }
    }

出队

    /**
     * 出队
     */
    public int poll() {
        if(head == null) {
            return -1;//或者抛异常
        }
        int oldVal = head.val;
        if(head.next == null) {
            head = tail = null;
        }else {
            head = head.next;
        }
        return oldVal;
    }

peek() 

    //查看当前队头元素是几
    public int peek() {
        if(head == null) {
            return -1;//或者抛异常
        }
        return head.val;
    }

判断队列是否为空

    // 队列是否为空
    public boolean isEmpty() {
        return head == null;
    }

循环队列

在我们用数组实现队列时，很容易想到下面这个结构：

 但是当我们连续从该队头中弹出元素时，就可以发现问题了：

 可以看到此时数组并没有满，但是当我们再次插入元素时，队尾却插入不了了，这时候我们可以想到将该数组看成是循环的数组，结构如下：

循环结构

代码实现

首先：

1、设置usedSize 当usedSize和数组长度相等时为满，等于0 则为空。
2、设置标志位 设 flag = true，每放一个元素，将 flag 置为 false，每有一个元素出队列，则将 flag 置为 true。当 front 和 rear 相遇时，flag为 true 则是空的，反之则是满的。

初始化

    public int[] elem;
    public int front;// 队头下标
    public int rear;// 队尾下标
    boolean flag = true;// 是否为空
 
    public MyCircularQueue(int k) {
        elem = new int[k];
    }

isFull() 和 isEmpty()

    // 检查循环队列是否为空。
    public boolean isEmpty() {
        if (rear == front && flag){
            return true;
        }
        return false;
    }
    // 检查循环队列是否已满。
    public boolean isFull() {
        if (rear == front && !flag){
            return true;
        }
        return false;
    }

入队

    //向循环队列插入一个元素。如果成功插入则返回真。
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        flag = false;
        return true;
    }

出队

    //从循环队列中删除一个元素
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % elem.length;
        flag = true;
        return true;
    }

peek()

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

获取队尾元素

    //获取队尾元素。如果队列为空，返回 -1 。
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // 如果是0下标，拿最后一个元素
        if (rear == 0) {
            return elem[elem.length-1];
        }else {
            return elem[rear - 1];
        }
    }

三、双端队列

概念

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

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