【算法】---栈与队列基础

前置准备

数据结构篇：学习过栈与队列这两种基本数据结构
前面会迅速回顾栈与队列的使用

本篇以Java为主，其它语言可自行对应内置的栈与队列容器。

栈

栈是一种后进先出的容器。
如下图，栈只有一个开口。

栈顶：栈的开口处，所有的插入（push）和删除（pop）操作都只能在栈顶进行。
栈底：栈的最底部，没有办法直接访问栈底的数据，必须通过逐步“弹出”栈顶元素才能到达栈底。
后进先出（LIFO）：最后放入栈中的元素会最先被取出，像叠盘子一样，最新放上去的盘子最先被拿走。
增删查询操作只允许在栈顶进行。
由于必定操作最近进入栈的数，因此栈的特性是后进先出。
Java中的Stack：Java—Stack
全局静态数组实现:解算法题常用，因为其常数时间快且可以空间复用算法题效率由于语言自带的栈，比如纯C选手就可以用这个迅速手搓一个栈不需要封装直接用。

class Stack {public  int[] stack;public int r;public Stack(int n) {stack = new int[n];r = 0;}public void push(int val) {stack[r++] = val;}public int pop() {return stack[--r];}public int peek() {return stack[r-1];}public boolean isEmpty() {return r==0;}public int size() {return r;}
}

Java中的LinkedList(双向链表)和ArrayDeque(双端队列）：两者也支持栈操作，具体查看手册。

队列

队列是一种先进先出的容器
在这里插入图片描述

Java中的Queue接口位于java.util包中，它有两个常见实现类可以充当队列。
LinkedList,ArrayDeque.

offer(E e)：将指定元素插入队列尾部，如果插入成功返回true。
poll()：移除并返回队首元素，如果队列为空则返回null。
peek()：获取队首元素但不移除，如果队列为空返回null。
isEmpty()：判断队列是否为空。
size():获取队列的长度

1. `LinkedList`使用

LinkedList类可以用来实现队列。支持队列操作。

import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {// 使用LinkedList实现队列Queue<Integer> queue = new LinkedList<>();// 队列是否为空·System.out.println(queue.isEmpty());// 入队操作queue.offer(1);queue.offer(2);queue.offer(3);// 查看队首元素（不移除）System.out.println("队首元素: " + queue.peek());// 出队操作System.out.println("移除的元素: " + queue.poll());// 队列长度·System.out.println(queue.size());// 查看出队后的队列System.out.println("队首元素: " + queue.peek());}
}

2. `ArrayDeque`

ArrayDeque 是一个基于数组的双端队列，它可以高效地作为队列或栈使用。

import java.util.ArrayDeque;
import java.util.Queue;public class ArrayDequeExample {public static void main(String[] args) {// 使用ArrayDeque实现队列Queue<String> arrayDeque = new ArrayDeque<>();// 队列是否为空·System.out.println(arrayDueue.isEmpty());// 入队操作arrayDeque.offer("A");arrayDeque.offer("B");arrayDeque.offer("C");// 查看队首元素System.out.println("队首元素: " + arrayDeque.peek());// 出队操作System.out.println("移除的元素: " + arrayDeque.poll());// 队列长度System.out.println(arrayDueue.size());// 查看出队后的队列System.out.println("队首元素: " + arrayDeque.peek());}
}

3. 常数时间快的数组实现

如果题目确定最大数据量是5000，那么意味着这个队列最多进入5000个元素。

public class MyQueue {public static int MAX = 5000;public int[] queue = new int[MAX];public int l,r,size;public MyQueue() {l = r = size = 0;}//[l,r)是有效数据， l==r意味队列为空public void offer(int val) {queue[r++] = val;size++;}public int poll() {size--;return queue[l++];}public int peek() {return queue[l];}public int size() {return size;}public boolean isEmpty() {return l==r;//或者size==0}public static void main(String[] args) {MyQueue queue = new MyQueue();System.out.println(queue.isEmpty());queue.offer(1);queue.offer(2);queue.offer(3);System.out.println("queue.size():"+queue.size());System.out.println(queue.poll());System.out.println("queue.size():"+queue.size());System.out.println(queue.poll());}
}

MAX取决于算法题的测试数据量。
这里没有引入多余的检查可自行补充。
事实上，这个类都不用封装，只需要MAX,queue数组，l,r这3个字段就可以直接充当队列解题，而且常数时间也优于Java自带的Queue的两个实现类。
C语言选手采用这种写法，时间性能最佳。

环形队列实现

设计循环队列
测试链接

//本题接口
/
class MyCircularDeque {public MyCircularDeque(int k) {}public boolean insertFront(int value) {}public boolean insertLast(int value) {}public boolean deleteFront() {}public boolean deleteLast() {}public int getFront() {}public int getRear() {}public boolean isEmpty() {}public boolean isFull() {}
}

解决方案
阅读题目。
1. 引入size,limit字段，方便维护。
1. 先实现isEmpty(),isFull()方法。
1. 设计[l,r)区间，l指向当前有效数据，r当前第一个无效数据。，插入，先左移动后插入，r先插入再往后移动。注意数组边界处理，使得整个数组循环起来。
1. 删除同3，但只需要挪动l或者r，注意边界。
1. getFront(),getRear()方法中，如果队列为空要返回-1，否则返回队列中对应的值。再次强调l指向当前有效数据，r当前第一个无效数据.

public int[] queue;private int l,r,limit,size;//limit:队列的最大容量//size：队列的长度//[l,r) 队列区间。public MyCircularDeque(int k) {queue = new int[k];l = r = size = 0;limit = k;}public boolean insertFront(int value) {if(isFull()) {return false;}queue[l = l==0?limit-1:l-1] = value;size++;return true;}public boolean insertLast(int value) {if(isFull()) {return false;}queue[r] = value;r = r==limit-1?0:r+1;size++;return true;}public boolean deleteFront() {if(isEmpty()) {return false;}l = l==limit-1?0:l+1;size--;return true;}public boolean deleteLast() {if(isEmpty()) {return false;}r = r==0?limit-1:r-1;size--;return true;}public int getFront() {return isEmpty()?-1:queue[l];}public int getRear() {return isEmpty()?-1:queue[r==0?limit-1:r-1];}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == limit;}