栈和队列总结

1栈

1.1栈的概念

栈是一种线性表，只允许在固定的一端进行插入和删除元素操作，进行插入和删除元素的一端叫做栈顶，另外一端叫做栈底，栈遵循后进先出，先进后出原则 。结构类似于羽毛球桶，先放进去的由于重力来到最下面，然后口又在上面，所以先能拿到的一定是最后放入桶的在最上面（后进先出），第一个放入的在最下面，只有把上面的拿走才能拿到最下面的（先进后出）

入栈:插入数据---->压栈

出栈:删除数据                                                                                                                            

1.2栈的使用

有关栈的常用方法：

public static void main(String[] args) {Stack<Integer> data = new Stack<Integer>();data.push(1);data.push(2);data.push(3);data.push(4);//pop()出栈顶元素4，然后栈顶元素变成3System.out.println(data.pop());//---->4//peek()获取栈顶元素不出栈----3System.out.println(data.peek());//----->3//size()获取有效元素个数System.out.println(data.size());//----->3}

1.3栈的模拟实现

此处我们使用数组模拟实现栈，使用链表也可以（头插法）

class StackNullException extends Exception{public StackNullException(String message) {System.out.println(message);;}
}public class MyStack {int DEFAULT_CAPACITY=10;int[] elem=new int[DEFAULT_CAPACITY];int useSize=0;public MyStack() {}public int push(int n){//判满if (isFull()){//满了先扩容elem= Arrays.copyOf(elem,elem.length*2);}//扩容完事之后再||没满--->入栈elem[useSize]=n;useSize++;return n;}private boolean isFull(){return useSize==elem.length;}public int peek() throws StackNullException{if (!isEmpty()){//通过usesize--覆盖删除的手段来删除int ret=elem[useSize-1];return ret;}else throw new StackNullException("栈为空异常，无法正常获取栈顶元素");}public int pop() throws StackNullException{//出栈前先判断栈是否为空if (!isEmpty()){//通过usesize--覆盖删除的手段来删除int ret=elem[useSize-1];useSize--;return ret;}else throw new StackNullException("栈为空异常，无法正常出栈");}public boolean isEmpty(){return useSize==0;}//获取有效元素个数public int size(){return  useSize;}

2队列  

2.1队列的概念

队列是一种允许在一端插入数据，在另外一端删除数据的特殊线性表，具有先进先出的特点，插入数据的一端叫做队尾，删除数据的一端叫做队头

2.2队列的使用

常用方法

队列Queue类本身是一个接口类，当中的方法要想使用就必须得要有一个实现类去实现一下该接口，重写这些方法，才能正常使用这些方法，而LinkedList正好是该接口的实现类，所以在new一个队列的实例化对象的时候，必须new一个链表LinkedList来充当队列，也就是说队列的底层结构是链表。类似这样--->

具体使用:

public static void main(String[] args) {//Queue类本身是接口类，不能直接new实例，需要一个实现类（功能类）来实现该接口然后new实例用该接口当中的方法//而LinkedList正好是该接口的实现类，实现了该接口Queue<Integer> queue=new LinkedList<>();//offer()入队列queue.offer(1);queue.offer(2);queue.offer(3);//poll()出队列，删除队头元素并返回该值System.out.println(queue.poll());//----->1//获取队列头元素--不删除System.out.println(queue.peek());//----->2//size()获取当前队列有效元素个数System.out.println(queue.size());//----->2}

2.3队列的模拟实现

我们利用双向链表来模拟实现：

public class MyQueue {//节点类class ListNode {int val;//存储的值ListNode pre;//前一个节点的地址ListNode next;//后一个节点的地址public ListNode(int val) {this.val = val;}}int usedSize=0;ListNode head=null;//头节点--->队头元素ListNode tail=null;//尾节点--->队尾元素public boolean offer(int n){ListNode node=new ListNode(n);if (head==null){//插入第一个元素tail=head=node;}else {tail.next=node;node.pre=tail;tail=node;}usedSize++;return true;}public int poll(){//此处需要分三种情况1·队列为空  2·队列不为空但就一个元素   3·多个元素if (!isEmpty() && head!=tail){//多个元素的情况int ret=head.val;head=head.next;head.pre=null;usedSize--;return ret;}else if (!isEmpty()&&head==tail){//一个元素int ret=head.val;head=tail=null;usedSize--;return  ret;}else return -1;//没有元素情况}public int peek(){if (!isEmpty()){int ret=head.val;return ret;}else return -1;}public boolean isEmpty(){return usedSize==0;}public int size(){return usedSize;}

3循环队列

3.1概念

实际中我们有时还会使用一种队列叫循环队列。如生产者消费者模型中就会使用循环队列。 环形队列通常使用数组实现

3.2实现循环队列有两个关键点一个细节问题

关键点1：怎么判满？

1使用usesize记录有效元素个数

2使用boolean类型的标记，比如定义一个变量

3浪费一个空间

关键点2：下标怎么改变？如何从array.length-1---->0?

1使用if语句

先让rear后移，rear如果不是在最后一个位置，那么后移之后就不会进入if语句也不需要做任何处理
因为它就是对的，如果rear一开始在最后一个位置，++后越界，越界后就循环回到0下标位置

rear++;if(rear>elem.length-1) rear=0;

2让real%数组长度即可

细节问题：

在获取队尾数据的时候，不是直接return elem[rear-1] 因为rear可能在0位置 0-1=-1了，正确做法是加一层判断如-----> int index=rear==0?elem.length-1:rear-1;

实现代码:

class MyCircularQueue {int[] elem;int useSize=0;public MyCircularQueue(int k) {this.elem=new int[k];}int front=0;int rear=0;public boolean enQueue(int value) {if(!isFull()){elem[rear]=value;rear++;rear=rear%elem.length;useSize++;return true;}else return false;}public boolean deQueue() {if(!isEmpty()){front++;front=front%elem.lengthuseSize--;return true;}else return false;}public int Front() {if(!isEmpty()) return elem[front];else return -1;}public int Rear() {//细节问题int index=rear==0?elem.length-1:rear-1;if(!isEmpty()) return elem[index];else return -1;}public boolean isEmpty() {return useSize==0;}public boolean isFull() {return useSize==elem.length;}
}

4双端队列（Deque）

4.1概念

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

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

4.2应用

在实际工程中，使用Deque接口是比较多的，链表LinkedList和ArrayDeque均可实现该接口。

public static void main(String[] args) {Deque<Integer> deque=new LinkedList<>();Deque<Integer> deque1=new ArrayDeque<>();}