Preface: The structure of this paper
1. What is stack
2. How to implement stack –> how to implement stack in JDK
3. Stack application
4. Stack common algorithm ——> monotone stack
4. 5. Smart refrigerator
All problem solving ideas: ** stack first – in – out data structure
1. What is stack?
A Stack is a special kind of linear table that restricts the insertion and deletion of elements in a linear table to the same end of the linear table. The end that allows insertion and deletion is the changing end, called the Top (the insertion and deletion we do at the Top of the stack is called loading and unloading) and the fixed end is called the Bottom of the stack. 3) According to the definition of the stack, the first element to be added to the stack is at the bottom of the stack, and the last element to be added is at the top of the stack, while the last element to be deleted is just the opposite. The last element to be added is deleted first, and the first element to be added is deleted last
The stack is like our bucket(We want to add water and take water into and out of the stack, and then can only operate at the end of the mouth (top of the stack), the sealing end (bottom of the stack) can not operate)
2. How to implement stack?
2.1 Implement stack of columnsIllustration:
Code:
class MyStack { Queue<Integer> queue; public MyStack() { queue = new LinkedList<Integer>(); } public void push(int x) {int n = queue. Size (); // Insert a new element queue.offer(x); For (int I = 0; i < n; i++) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } public int top() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); }}Copy the codeScheme 2:
class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; Public MyStack() {queue1 = new LinkedList<Integer>(); queue2 = new LinkedList<Integer>(); } public void push(int x) {// The element is inserted into the secondary queue queue2.offer(x); // The primary queue element is inserted into the secondary queue while (! queue1.isEmpty()) { queue2.offer(queue1.poll()); } // The secondary Queue becomes empty. Queue<Integer> temp = queue1; queue1 = queue2; queue2 = temp; } public int pop() { return queue1.poll(); } /** Get the top element. */ public int top() { return queue1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue1.isEmpty(); }}Copy the code2.2: Array implementation stack
class ArrayStack { private int maxSize; // stack size private int[] stack; Private int top = -1; private int top = -1; Public ArrayStack(int maxSize) {this.maxSize = maxSize; stack = new int[this.maxSize]; } public Boolean isFull() {return top == maxSize - 1; } public Boolean isEmpty() {return top == -1; } public void push(int value) {if(isFull()) {throw new RuntimeException(" full "); } top++; stack[top] = value; Public int pop() {if(isEmpty()) {throw new RuntimeException(" empty, no data ~"); } int value = stack[top]; top--; return value; Public void list() {if(isEmpty()) {system.out.println (" empty, no data ~~"); return; } for(int I = top; i >= 0 ; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); }}}Copy the code2.3: How to implement Stack in JDK
1. The operation of Vector 2.push(),pop(),empty() and peek() is mainly inherited, and synchronized modification is added to the method, so the efficiency is slow and it is not recommended.
public class Stack<E> extends Vector<E> { private static final long serialVersionUID = 1224463164541339165L; public Stack() { } public E push(E item) { this.addElement(item); return item; } public synchronized E pop() { int len = this.size(); E obj = this.peek(); this.removeElementAt(len - 1); return obj; } public synchronized E peek() { int len = this.size(); if (len == 0) { throw new EmptyStackException(); } else { return this.elementAt(len - 1); } } public boolean empty() { return this.size() == 0; } public synchronized int search(Object o) { int i = this.lastIndexOf(o); return i >= 0 ? this.size() - i : -1; }}Copy the code3: Stack application?
1) Function calls such as Java virtual machine stack (the virtual machine creates a private stack for each thread, and each method call creates a stack frame, and each method from call to return corresponds to a stack frame in and out of the stack process.
2) Recursive call –> Deep search (DFS) —-> binary tree traversal (recursive implementation)
3) Matching parentheses
4) suffix expression evaluation, etc
4. Stack common algorithm questions (from simple to difficult)
- Valid parentheses
Method 1: auxiliary stack
class Solution {
public boolean isValid(String s) {
Stack<Character>stack = new Stack<Character>();
for(char c: s.toCharArray()){
if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;
}
return stack.isEmpty();
}
}
Copy the codeMethod 2: Auxiliary stack +HashMap
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
Copy the code- Evaluate the inverse Polish expression
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for (int i = 0; i < n; i++) {
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}
Copy the code- The largest rectangle in a bar chart
1. Brute force: Go beyond the time limit, whoo-whoo-whoo-whoo-hoo
class Solution { public int largestRectangleArea(int[] heights) { int len=heights.length; if (len==0){ return 0; } int res=0; for (int i=0; i<len; i++){ int left=i; int right=i; int cur=heights[i]; While (left>0&&heights[left-1]>=cur){left--; } while (right<len-1&&heights[right+1]>=cur){ right++; } res= Math.max((right-left+1)*heights[i],res); } return res; }}Copy the code2. The monotonous stack
Class Solution {public int rectangleArea (int[] heights) {int res=0; int len=heights.length; If (len==0){return 0; } if (len==1){ return heights[0]; Int [] newHeight=new int[len+2]; newHeight[0]=0; System.arraycopy(heights,0,newHeight,1,len); newHeight[len+1]=0; len+=2; Deque<Integer> stack=new LinkedList<>(); stack.addLast(0); for (int i=1; i<len; i++){ while (newHeight[i]<newHeight[stack.peekLast()]){ int curHigh=newHeight[stack.pollLast()]; int curWidth=i-stack.peekLast()-1; res=Math.max(curHigh*curWidth,res); } stack.addLast(i); } return res; }}Copy the codeTOList has the foundation of the front, this has to be solved, oh hahahahaha
- The daily temperature
1. Violent method 2. Drab stack 42
Supplement: 232. Implement queue with stack 225. Implement stack with queue
4. 5. Smart refrigerator