Java数据结构——栈（Stack）和队列（Queue）

一、栈（Stack）

1.1 栈的概念

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

进栈：进栈就是栈的插入操作，在栈顶插入一个数据元素

出栈：出栈就是栈的删除操作，在栈顶删除一个数据元素

我们在生活中也能经常看到栈的使用，比如子弹装入弹夹，我们只能在一个口放入或拿出子弹

1.2 栈的使用

1.2.1 栈的构造

class Student{String name;int age;
}public class stack {public static void main(String[] args) {Stack<Integer> stack=new Stack<>();Stack<Student> stack1=new Stack<>();}
}

可以看到Stack里面可以传入参数，可以是系统有的包装类 Integer，String……，也可以是自己的创建的类Student

1.2.2 栈的方法

1.3 栈的模拟实现

public class MyStack {int[] array;int size;public MyStack(){array = new int[3];}public int push(int e){ensureCapacity();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 int size(){return size;}public boolean empty(){return 0 == size;}private void ensureCapacity(){if(size == array.length){array = Arrays.copyOf(array, size*2);}}
}

二、队列（Queue）

2.1 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头（Head/Front）

2.2 队列的使用

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

2.2.1 队列的构造

class student{String name;int age;
}public class queue {public static void main(String[] args) {Queue<Integer> queue1=new LinkedList<>();Queue<student> queue2=new LinkedList<>();}
}

2.2.2 队列的方法

2.3 队列的模拟实现

队列需要存储元素的空间，我们之前学过两种储存元素的结构，顺序结构和链式结构，我们需要考虑队列的实现使用顺序结构还是链式结构好？

2.3.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;}else{last.next = newNode;newNode.prev = last;}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;}
}

2.3.2 循环队列

我们可以看到当队列是空的时候，头和尾在同一个位置，当队列为满的时候，头和尾也相遇在同一个位置，那么我们该如何区分队空还是队满呢？

我们一般有3种方法来判断队空和队满

1. 通过添加 size 属性记录

我们创建一个变量usedsize，记录当前队列中的元素个数

public class MyCycleQueue2 {public int[] elem;public int usedSize;public int front;public int rear;public MyCycleQueue2(int k) {elem = new int[k];}//入队列public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1)%elem.length;usedSize++;return true;}//出队列public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;usedSize--;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 usedSize == 0;}public boolean isFull() {return usedSize == elem.length;}
}

2. 保留一个位置

我们在空出一个位置，也就是浪费一个空间。此时当队满的时候，头尾就不会相遇。队空的时候，头尾相遇，队满的时候，头尾差一个位置，这样就可以区分开来了

public class MyCycleQueue {public int[] elem;//public int usedSize;public int front;public int rear;public MyCycleQueue(int k) {elem = new int[k];}//入队列public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;//rear++; errorrear = (rear+1)%elem.length;//usedSize++;return true;}//出队列public boolean deQueue() {if(isEmpty()) {return false;}//front++;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 usedSize == elem.length;return (rear+1)%elem.length == front;}

3. 使用标记

我们创建一个boolean变量flg，默认false，在添加元素的时候将flg变为true，删除元素的时候将flg变为false，判空的时候条件为头尾相遇并且flg为false，判满的时候条件为头尾相遇并且flg为true

public class MyCycleQueue3 {public int[] elem;public int usedSize;public int front;public int rear;public boolean flg;//默认是falsepublic MyCycleQueue3(int k) {elem = new int[k];}//入队列public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1)%elem.length;flg = true;return true;}//出队列public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;flg = false;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() {if(front == rear && !flg) {return true;}return false;}public boolean isFull() {if(front == rear && flg) {return true;}return false;}
}

2.4 双端队列（Deque）

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

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