栈和队列
- 栈也是一种线性构造
- 相比数组，栈对应的操作是数组的子集
- 只能从一端增加元素，也只能从一端取出元素
- 这一端称为栈顶
- 栈是一种后进先出的数据结构（LIFO）
举一个例子，咱们平时敲代码都常常撤销，而撤销操作的原理就是靠栈来实现的。
比方咱们先打出 "沉迷"、"学习"、"不法"，这个时候咱们发现打错了无奈两个字，而这个时候栈是这样的。
通过应用撤销性能，不法将从栈顶取出，而后删除不法两个字。这个时候栈中就只有两个元素。
再举一个深刻的例子：程序调用的零碎栈
假如咱们有三个函数。
咱们通过调用函数A，在执行第二行执行B函数的时候，暂停函数A。这个时候就会将暂停的函数A压入栈中。
而后调用函数B里的C函数时候，也会将函数B压入栈中，
当函数C执行完了当前，会首先取出栈中的B2，而后继续执行B2剩下的函数，执行实现当前执行A2。
栈的根本实现
定义一个Stack接口和实现类
public interface Stack<E> { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek();} public class ArrayStack<E> implements Stack<E>{ private Array<E> array; public ArrayStack(){ array = new Array<>(); } public ArrayStack(int capacity){ array = new Array<>(capacity); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } //增加到栈顶 @Override public void push(E e) { array.addLast(e); } //取出并移除栈顶元素 @Override public E pop() { return array.removeLast(); } //查看栈顶元素 @Override public E peek() { return array.get(array.getSize() - 1); } public int getCapacity(){ return array.getCapacity(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack: "); res.append("["); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1) { res.append(", "); } } res.append("] top"); return res.toString(); }}创立测试类
public class Main { public static void main(String[] args) { ArrayStack<Integer> arrayStack = new ArrayStack<>(); for (int i = 0; i < 5; i++) { arrayStack.push(i); System.out.println(arrayStack); } System.out.println("取出栈顶元素"+arrayStack.pop()); System.out.println(arrayStack); }} Stack: [0] top Stack: [0, 1] top Stack: [0, 1, 2] top Stack: [0, 1, 2, 3] top Stack: [0, 1, 2, 3, 4] top 取出栈顶元素4 Stack: [0, 1, 2, 3] top栈的复杂度剖析
ArrayStack<E>
- void push(E)
O(1) - E pop()
O(1) - E peek()
O(1) - int getSize()
O(1) - boolean isEmpty()
O(1)
栈的利用-括号匹配器
援用 LeetCode 上 20. 无效的括号
给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否无效。
无效字符串需满足：
- 左括号必须用雷同类型的右括号闭合。
- 左括号必须以正确的程序闭合。
- 留神空字符串可被认为是无效字符串。
具体思路就是判断以后是左侧括号还是右侧，如果是左侧就压入栈，当是右侧的时候就取出栈顶元素进行顺次匹配。
class Solution { public boolean isValid(String s) { if(s.isEmpty()) { return true; } if (s.length() % 2 != 0){ return false; } Stack<Character> stack=new Stack<>(); for(char c:s.toCharArray()){ if(c=='(') { stack.push(')'); } else if(c=='{') { stack.push('}'); } else if(c=='[') { stack.push(']'); } else if(stack.empty()||c!=stack.pop()) { return false; } } return stack.empty(); }}队列的根本实现
- 队列也是一种线性构造
- 相比数组，队列对应的操作是数组的子集
- 只能从队尾增加元素，只能从队首取出元素
- 队列是一种先进先出的数据结构（FIFO）
很容易了解，和生存中的排队是一样的。
public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront();}public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue() { array = new Array<>(); } public ArrayQueue(int capacity) { array = new Array<>(capacity); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } //插入队尾 @Override public void enqueue(E e) { array.addLast(e); } //拿出队首元素 @Override public E dequeue() { return array.removeFirst(); } //查看队首元素 @Override public E getFront() { return array.get(0); } public int getCapacity(){ return array.getCapacity(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: "); res.append("front ["); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1) { res.append(", "); } } res.append("] tail"); return res.toString(); }}数组队列的复杂度剖析
ArrayQueue<E>
- void enqueue(E)
O(1) - E dequeue()
O(n) - E front()
O(1) - int getSize()
O(1) - boolean isEmpty
O(1)
循环队列
因为数组队列的出队操作是O(n)的，是存在肯定的局限性，应用循环队列来解决这个问题。
因为咱们在删除索引为0的数据时候，会导致前面的数据前移，所以是O(n)级别。
循环队列其实就是在队首移除的时候，咱们不进行前面数据的挪动，而是应用front变量进行自增，而后指向下一个元素，tail变量来保护队尾的地位。
一开始的时候，front和tail都指向索引0的地位。
当新增一个元素后，tail进行自增而后指向下一个元素的地位，而front放弃不变。
而移除一个队首元素的时候，front要进行自增而后指向下一个元素的地位，tail放弃不变，这样的话咱们不须要挪动对象，只须要更改front的指向即可。
那为什么叫循环队列呢，因为咱们当队列满了的时候，咱们须要进行(tail+1) % capacity操作，而后将tail指向新的地位。
当咱们在0的地位再新增一个元素的时候，咱们如何判断队列是否满了呢，因为咱们之前说过 front == tail的时候阐明数组为空，而咱们应用循环队列的话，咱们须要应用 (tail + 1) % capacity == front 就阐明队列满了须要进行扩容。须要阐明循环队列会节约一个空间。
循环队列的实现
public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront();}public class LoopQueue<E> implements Queue<E> { private E[] data; private int front, tail; private int size; public LoopQueue(int capacity) { //因为循环队列须要节约一个空间，所以要将数组大小+1 data = (E[]) new Object[capacity + 1]; front = 0; tail = 0; size = 0; } public LoopQueue() { this(10); } public int getCapacity() { return data.length - 1; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return front == tail; } @Override public void enqueue(E e) { if ((tail + 1) % data.length == front) { resize(getCapacity() * 2); } data[tail] = e; tail = (tail + 1) % data.length; size++; } @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } E ret = data[front]; data[front] = null; front = (front + 1) % data.length; size--; if (size == getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / 2); } return ret; } @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } return data[front]; } private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity + 1]; for (int i = 0; i < size; i++) { newData[i] = data[(i + front) % data.length]; } data = newData; front = 0; tail = size; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity())); res.append("front ["); for(int i = front ; i != tail ; i = (i + 1) % data.length){ res.append(data[i]); if((i + 1) % data.length != tail) { res.append(", "); } } res.append("] tail\n"); res.append("front = "+front); res.append("， tail = "+tail); res.append("， data.length = "+data.length); return res.toString(); }}循环队列的复杂度剖析
LoopQueue<E>
- void enqueue(e)
O(1) - E dequeue()
O(1) - E getFront()
O(1) - int getSize()
O(1) - boolean isEmpty()
O(1)