Queue&Stack
Stack
Stack 一种后进先出（LIFO）的线性表.
栈的操作很简单。只要是具有最近相关性的题目都可以使用Stack这种数据结构来解决。
需要注意的是可以用Stack解决的问题都可以使用Deque（Double End Queue）来代替.
Stack相关LeetCode 题目
1.括号匹配
class Solution {
Map<Character,Character> mappings;
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
//stack里边存储的一定是有括号 如果map get到左括号 就比较 没有就push
public boolean isValid(String s) {
if(s == null || (s.length() % 2) == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
for(int i = 0 ; i < s.length() ;i++ ) {
Character c = s.charAt(i);
Character cc = mappings.get(c);
if(cc != null) {
Character topEle = stack.empty() ? '#' : stack.pop();
if(! topEle.equals(cc)) {
return false;
}
}else {
stack.push(c);
}
}
return stack.isEmpty();
}
复制代码2最小栈
使用了aider 栈保存了当前的最小值，以及在此之前的最小值。
class MinStack {
private Stack<Integer> data;
private Stack<Integer> aider;
/** initialize your data structure here. */
public MinStack() {
data = new Stack<>();
aider = new Stack<>();
}
public void push(int x) {
data.push(x);
if(aider.isEmpty() || aider.peek() >= x) {
aider.push(x);
}
}
public void pop() {
if(!data.isEmpty()) {
int x =data.pop();
if(x == aider.peek()) {
aider.pop();
}
}
}
public int top() {
if(!data.isEmpty()) {
return data.peek();
}
throw new RuntimeException("data is empty");
}
public int getMin() {
if(!aider.isEmpty()) {
return aider.peek();
}
throw new RuntimeException("aider is empty");
}
}
复制代码3.柱状图最大面积
使用栈辅助的，比当前栈顶元素大push如栈，小于栈顶元素则进行比较计算，栈顶元素的左边界为栈顶元素的上一个元素，有边界为当前小于栈顶元素的值。
//解法一
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
Stack<Integer> leftBorder = new Stack<>();
leftBorder.push(-1);
for (int i = 0; i < heights.length; i++) {
while(leftBorder.peek() != -1 && heights[leftBorder.peek()] > heights[i]) {
maxArea = Math.max(maxArea,heights[leftBorder.pop()] * (i - 1 - leftBorder.peek()));
}
leftBorder.push(i);
}
while(leftBorder.peek() != -1){
maxArea = Math.max(maxArea,heights[leftBorder.pop()] * (heights.length - 1 - leftBorder.peek()));
}
return maxArea;
}
/**
* 解决办法二分治算法
*
* @param heights
* @return
*/
public int largestRectangleArea4(int[] heights) {
if (heights.length == 0) {
return 0;
}
return largestRecusion(heights, 0, heights.length - 1, heights[0]);
}
private int largestRecusion(int[] heights, int start, int end, int max) {
if (start >= end) {
return max;
}
int minIndex = getMinIndex(heights, start, end);
int currentArea = heights[minIndex] * (end - start + 1);
max = Math.max(max, currentArea);
int max1 = largestRecusion(heights, start, minIndex - 1, heights[start]);
int max2 = largestRecusion(heights, minIndex + 1, end, heights[end]);
return Math.max(max, Math.max(max1, max2));
}
private int getMinIndex(int[] heights, int start, int end) {
int min = Integer.MAX_VALUE;
int minIndex = start;
for (int i = start; i <= end; i++) {
if (min > heights[i]) {
min = heights[i];
minIndex = i;
}
}
return minIndex;
}
复制代码Queue
队列的种类很多
- 队列
- 环形队列
- 阻塞队列
- 优先级队列
- 并发队列
- ...等等
Queue也是一种线性表，特性就是先进先出（FIFO）.
Queue代码分析
Queue是一个接口，有六个方法
| -throw Exception- | -return default result - | |
|---|---|---|
| add(E e) | offer(E e) | 添加元素（head） |
| remove() | poll() | 删除元素（head） |
| element() | peek() | 获取元素（head） |
public interface Queue<E> extends Collection<E> {
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
}
复制代码自己实现一个双端环形队列
class MyCircularDeque {
private int[] elements;
private int head;
private int tail;
private int len;
/**
* Initialize your data structure here. Set the size of the deque to be k.
*/
public MyCircularDeque(int k) {
this.elements = new int[k + 1];
len = k + 1;
}
/**
* Adds an item at the front of Deque. Return true if the operation is successful.
*/
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
elements[head = (head - 1 + len) % len] = value;
return true;
}
/**
* Adds an item at the rear of Deque. Return true if the operation is successful.
*/
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
elements[tail] = value;
tail = (tail + 1) % len;
return true;
}
/**
* Deletes an item from the front of Deque. Return true if the operation is successful.
*/
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
head = (head + 1) % len;
return true;
}
/**
* Deletes an item from the rear of Deque. Return true if the operation is successful.
*/
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
tail = (tail - 1 + len) % len;
return true;
}
/**
* Get the front item from the deque.
*/
public int getFront() {
if(isEmpty()) {
return -1;
}
return elements[head];
}
/**
* Get the last item from the deque.
*/
public int getRear() {
if(isEmpty()) {
return -1;
}
return elements[(tail - 1 + len) % len];
}
/**
* Checks whether the circular deque is empty or not.
*/
public boolean isEmpty() {
return (head == tail);
}
/**
* Checks whether the circular deque is full or not.
*/
public boolean isFull() {
return ((tail + 1) % len) == head;
}
}
复制代码Priority Queue代码分析
java的Priority Queue 是依靠heap（小顶堆）来进行存储数据的，它的核心代码就是建堆的操作，主要就是Priority Queue 的两个方法 add() 和 pop()
add(),代码分析 siftUp（由下向上建堆）。代码注释如下。
/**
* 添加代元素
*/
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
//如果队列满了 扩容
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
//新添加的元素从下向上进行堆化
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
//自定义比较器
siftUpUsingComparator(k, x);
else
//默认比较器
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
//堆元素的父亲节点的索引
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//比较与父亲节点的大小，因为是小顶堆如果 小于父亲元素交换，大于结束。
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
复制代码poll() 的代码其实就是删除他的heap顶元素并且返回。满足删除条件的情况下，进行由上向下堆化的过程，代码如下。
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
复制代码
