本文带大家,理解什么是栈结构和队列结构,学习栈和队列能够帮住大家解决什么问题? 栈和队列很相似两个结构一同讲解. 你需要有上一节讲解的知识 数组结构 栈 FLFO 什么是栈,栈是后进先出.就像放盘子一样,从下往上一个一个放,取盘子时从上往下一个一个取出,也就是后进入的盘子先取出来. 可以叫做后进先出或者先进后出.栈显然是一种操作受限的结构,我们完全可以使用上一节讲解的:数组结构来代替栈结构,那么为什么要使用栈结构呢? 满足后进先出这种特性的优先选择栈结构. 栈的应用
栈可以应用到撤销操作中,比如我们输入了:“举”-》“头“-〉”网“. 其实想输入”望”结果写成了”网”,需要把“网”删除掉,重新写入.
如下,使用栈结构操作. “网”这个错别字在栈顶,“网”改成”望”只需要将“网”从栈顶移除重新写入”望”.
| 网 |
| 头 |
| 举 |
|____|
如何实现一个栈呢? 栈主要有两个操作就是入栈和出栈,都是对栈顶的操作,栈可以通过数组和链表来实现,这里我们根据上一节中的数组的结构来实现栈.
代码实现如下: 下面代码非常简单,基于我们上一节中写的动态数组Array
来实现.
栈的时间复杂度:入栈和出栈在最好的情况下是O(1),在上一节中我们实现的Array
已经实现了动态扩容的方法,那么栈在入栈和出栈最坏的情况下时间复杂度为:O(n)
Array 内部实现了动态扩容和缩容机制,当栈空间不够时,进行两倍的扩容,当栈中的元素个数小于栈空间的1/4时,进行缩容处理.
极客时间 如上图摘自极客时间.
/**
* 基于动态数组的栈
*
* @param <E>
*/
public class ArrayStack<E> extends Array<E> implements Stack<E> {
private Array<E> array;
public ArrayStack(int capacity) {
this.array = new Array<>(capacity);
}
public ArrayStack() {
this.array = new Array<>();
}
@Override
public void push(E e) {//O(1)
array.addLast(e);
}
@Override
public E pop() {//O(1)
return array.removeLast();
}
@Override
public E peek() {
return array.getLast();
}
@Override
public int size() {
return array.getSize();
}
public int getCapacity() {
return array.getCapacity();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack:");
res.append("[");
for (int i = 0; i < size(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1) {
res.append(", ");
}
}
res.append("] top");
return res.toString();
}
}
括号匹配问题是LeetCode上的一个经典问题. 当我们匹配到左括号的时候进行入栈操作,当匹配到右扩号到时候进行栈顶出队操作来匹配两个括号
匹配[]{}()
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
//将左括号添加到栈中 ()[]{}
if (c == '(' || c == '[' || c == '{')
stack.push(c);
else {
//如果栈中没有都没有返回false
if (stack.isEmpty()) return false;
Character top = stack.pop();
if (c == ')' && top != '(') {
return false;
}
if (c == ']' && top != '[') {
return false;
}
if (c == '}' && top != '{') {
return false;
}
}
}
return stack.isEmpty();
}
栈还有一个重要的应用就是函数的调用栈. 我们可以根据如下代码理解:
int A(){
1...
2 B();
3...
}
int B(){
1...
2 C();
3...
}
int C(){
...
}
当开始执行A函数,当程序执行到A的第二行时,需要去执行B函数,此时将栈中压入一个信息叫做A2.这是执行B函数当执行到B函数的第二行时,需要去执行C函数,此时将在栈中压入一个信息叫做B2,然后执行C函数,当C函数执行完成之后,此时系统从栈顶中查找信息,找到B2然后出栈,执行完B函数.系统在从栈顶中查找信息,找到A2然后出栈,执行完A函数,栈顶没有任何信息时,A函数就执行完毕了. 运用栈结构实现了函数的调用
在算术中的加减乘除四则运算比如:3+5x6-1. 我们通过心算就能算出结果,但是计算机是如何计算的呢? 编译器就是通过两个栈结构来实现的,一个栈A保存数,一个栈B保存运算符,当遇到数字压入栈A中,当遇到运算符与栈B的栈顶运算符比较,如果优先级高于栈顶运算符则压入栈.如果低于栈顶运算符的优先级,则从运算符栈B中取出栈顶运算符,与数字栈A中从栈顶取出俩个数字进行运算,把运算结果压入数字栈A中继续比较. 最后清空栈得到运算结果.
图片来自极客时间 了解了原理就可以用代码来实现了,这里我就不贴代码了,大家可以自己实现一下. 栈解决浏览器前进和后退问题 了解了栈结构,我们如何用栈来实现浏览器的前进和后退功能呢? 其实我们只需要两个栈即可,一个栈X记录页面,一个栈Y记录后退的页面 点击前进按钮,依次从Y 栈中取出页面添加到X栈中,当Y栈为空时,就不能在前进了. 点击后退按钮,一次从X栈中取出页面添加到Y栈中,当X栈为空时,就不能在后退了.
如下图所示
|c | | |
|b | | |
|a | | |
|__| |__|
X栈 Y栈
点击了后退按钮,将c页面存储到了Y栈中.此时显示的是b页面
| | | |
|b | | |
|a | |c |
|__| |__|
X栈 Y栈
点击了前进按钮,将c从Y栈中取出,放入X栈中,此时显示的是c页面
|c | | |
|b | | |
|a | | |
|__| |__|
X栈 Y栈
代码实现如下:
public class BrowserStack {
//前进栈froward
private ArrayStack<String> forwardStack = new ArrayStack<>();
//后退栈
private ArrayStack<String> backStack = new ArrayStack<>();
private String currentPage;
public void open(String url) {
this.currentPage = url;
forwardStack.push(url);
System.out.println("open forwardStack:" + forwardStack);
}
/**
* 后退操作
* f:a b
* b: d c
*
* @return
*/
public boolean goBack() {
if (forwardStack.isEmpty()) {
System.out.println("Not Go Back");
return false;
}
//将当前页面加入后退栈中
//前进栈移除此页面
String pop = forwardStack.pop();
backStack.push(pop);
showUrl(forwardStack.peek(), "Back");
System.out.println("backStack:" + backStack);
System.out.println("forwardStack:" + forwardStack);
return true;
}
/**
* 前进操作
* F:a b
* B:c
* F:a b c
*
* @return
*/
public boolean goForward() {
if (backStack.isEmpty()) {
System.out.println("Not Go Forward");
return false;
}
String pop = backStack.pop();
showUrl(pop, "Forward");
forwardStack.push(pop);
System.out.println("backStack:" + backStack);
System.out.println("forwardStack:" + forwardStack);
return true;
}
public void showUrl(String url, String p) {
this.currentPage = url;
System.out.println("showUrl = [" + url + "] " + p);
}
public void checkCurrentPage() {
System.out.println("showUrl = [" + currentPage + "]");
}
public static void main(String[] args) {
BrowserStack browser = new BrowserStack();
browser.open("a");
browser.open("b");
browser.open("c");
browser.checkCurrentPage();//c
browser.goBack();//b
browser.goBack();//a
browser.goForward();//b
browser.open("d");
browser.goForward();//c
browser.goBack();//d
browser.goForward();//c
browser.goBack();//d
browser.goBack();//b
browser.goBack();//a
browser.goBack();//nul
browser.checkCurrentPage();
System.out.println();
}
}
同样的原理我们使用两个栈,其中一个作为辅助栈,存储的是x - min
public class MinStack {
/**
* initialize your data structure here.
*/
List<Long> array;
//assist stack records min stack
Stack<Long> assistStack;
private long min;
public MinStack() {
array = new ArrayList<>();
assistStack = new Stack<>();
}
//1 2 3 -1 -2 -4
public void push(long x) {
array.add(x);
//
if (assistStack.isEmpty()) {
assistStack.push(0L);
min = x;
} else {
System.out.println("x = [" + x + "]" + ",min = [" + min + "]" + "data = [" + (x - min) + "]");
assistStack.push(x - min);//如果x-min>0 则说明 最小的是min 如果<0
if (x < min) {
min = x;
}
}
}
public Long pop() {
if (array.isEmpty()) return -1l;
Long remove = array.remove(array.size() - 1);
Long pop = assistStack.pop();
if (pop < 0) {
min = min - pop;
}
System.out.println("min:" + min + " pop:" + pop);
return remove;
}
public Long top() {
if (array.isEmpty()) return -1l;
return array.get(array.size() - 1);
}
public Long getMin() {
return min;
}
}
队列是先进先出的结构,可以理解为队列是两端开口的,栈是一端开口的,队列从一端进入另一段取出,栈只能从一端进入,同一端取出.
可以理解队列是排队买票,先来的先买,后来的后买,不允许插队.队列和栈一样只有两个操作,入队和出队操作,队尾入队,队头出队.
理解了栈,队列就更容易理解了,我们使用数组来对队列的实现代码如下:
import datastructure.array.Array;
/**
* 动态队列结构
*
* @param <E>
*/
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(int capacity) {
array = new Array<>(capacity);
}
public ArrayQueue() {
this(10);
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
/**
* 每次移除的是数组的第一个,会导致所有数据的移动 性能低效
*/
@Override
public E dequeue() {
if (isEmpty()) return null;
return array.removeFirst();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public int size() {
return array.getSize();
}
@Override
public E getTopQueue() {
return array.get(0);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue: \n");
res.append("top: ");
for (int i = 0; i < size(); i++) {
res.append(array.get(i));
if (i < size() - 1) {
res.append(", ");
}
}
return res.toString();
}
public static void main(String[] args) {
// ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
// for (int i = 0; i < 6; i++) {
// arrayQueue.enqueue(i);
// }
// System.out.println(arrayQueue);
// arrayQueue.dequeue();
// System.out.println(arrayQueue);
// arrayQueue.enqueue(7);
// System.out.println(arrayQueue);
// arrayQueue.dequeue();
// System.out.println(arrayQueue);
System.out.println("求余:"+1%2);
}
}
上述队列的实现不知道大家有没有看出一个问题,在出队的时候需要移除数组的第0个元素,这个会导致,从第0个元素之后的所有的元素都要往前移动1位,出队的时间复杂度为O(n),如何优化出队操作呢? 使用循环队列.
图片来自-极客时间
如上图所示,我们通过head来标记队头,tail来标记队尾,当head==tail时队列为空.当(tail+1)%length == head时队列满了.循环队列会浪费1个存储空间
循环队列的实现代码如下:
求余公式:a%b = a-(int)(a/b)*b
/**
* 循环队列
*
* @param <E>
*/
public class LoopQueue<E> implements Queue<E> {
private E[] array;
private int size;
//标记队头
private int front;
//标记队尾
private int tail;
public LoopQueue(int capacity) {
array = (E[]) new Object[capacity + 1];//容器的大小要多申请一个空间 因为循环队列需要有一个额外的空间占用 否则无法判断队列是否满了
size = 0;
front = 0;
tail = 0;
}
public LoopQueue() {
this(10);
}
public int getCapacity() {
return array.length - 1;
}
@Override
public void enqueue(E e) {
//首先判断队列容器是否满了?如果tail的下一个等于front则表示队列已经满了
if ((tail + 1) % array.length == front) {
//进行扩容操作
resize(getCapacity() * 2);
}
array[tail] = e;
tail = (tail + 1) % array.length;
size++;
}
/**
* 对数组进行扩容和缩容
*
* @param capacity 大小
*/
private void resize(int capacity) {
E[] newData = (E[]) new Object[capacity + 1];//同样我们需要预留一个空间来判断队列是否满了
for (int i = 0; i < size; i++) {
newData[i] = array[(i + front) % array.length];
}
//优化循环 每次循环
// for (int i = front, j = 0; i != tail; i = (i + 1) % array.length, j++) {
// newData[j] = array[i];
// }
array = newData;
front = 0;
tail = size;
}
@Override
public E dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("LoopQueue is Empty!");
}
E res = array[front];
array[front] = null;
front = (front + 1) % array.length;
size--;
if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
//缩容
resize(getCapacity() / 2);
}
return res;
}
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public int size() {
return array.length - 1;//注意要减掉占用的一个空间的大小
}
@Override
public E getTopQueue() {
return array[front];//查看队头数据
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("LoopQueue:size:%d,capacity:%d\n", size, getCapacity()));
builder.append("front:");
for (int i = front; i != tail; i = (i + 1) % array.length) {
builder.append(array[i]);
if ((i + 1) % array.length != tail)
builder.append(", ");
}
// for (int i = 0; i < array.length; i++) {
// builder.append(array[i]);
// if (i<array.length-1)
// builder.append(", ");
// }
builder.append(" tail");
return builder.toString();
}
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<Integer>(5);
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if (i % 3 == 2) {
queue.dequeue();
System.out.println(queue);
}
}
}
}
我们可以对比一下两个队列的运行时间:
// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
private static double testQueue(Queue<Integer> q, int opCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for (int i = 0; i < opCount; i++)
q.dequeue();
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
}
输出结果如下:很明显循环队列的性能要高于普通的队列.
ArrayQueue, time: 3.089252806 s
LoopQueue, time: 0.015925464 s
队列在Java中应用广泛,如阻塞队列和并发队列. 这些队列实现较为复杂我会在后面进行讲解.