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

一、栈

（一）概念

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

栈在现实生活中的例子：

（二）栈的使用

我们可以看到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
2Process 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
falseProcess 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();}
}