Summary of Data Structure and Algorithm (III)

• Title: Implement a special stack, in addition to the basic function, and then implement the function of returning the smallest element in the stack
  • Add a new stack to manage the minimum value. Each push will compare the minimum value with the data at the top of the stack

class MyMinStack { private Stack<Integer> minStack; private Stack<Integer> stack; public MyMinStack() { minStack = new Stack<>(); stack = new Stack<>(); } public void push(Integer i) { stack.push(i); if (! minStack.isEmpty()) { Integer peek = minStack.peek(); minStack.push(Math.min(peek, i)); } else { minStack.push(i); } } public Integer pop() { if (! stack.isEmpty()) { minStack.pop(); return stack.pop(); } else {throw new RuntimeException(" there is no data in the stack "); } } public Integer getMin() { if (! minStack.isEmpty()) { return minStack.peek(); } else {throw new RuntimeException(" there is no data in the stack "); }}}Copy the code

• Topic two: Using stacks to implement queues
  • Use two stacks, negative and negative equals positive. Note that data can only be pushed completely before popping

Public StackToQueue {static class MyQueue<T> {private Stack<T> stack1; //pop Stack private Stack<T> stack2; public MyQueue() { stack1 = new Stack<T>(); stack2 = new Stack<T>(); } public void add(T value) { stack1.push(value); pushToPop(); } private void pushToPop() { if (stack2.isEmpty()) { while (! stack1.isEmpty()) { stack2.push(stack1.pop()); }} public poll() {if(isEmpty()){throw new RuntimeException(" queue data isEmpty "); } pushToPop(); return stack2.pop(); } public boolean isEmpty() { return stack2.isEmpty() && stack1.isEmpty(); } public T peek(){if(isEmpty()){throw new RuntimeException(" queue data isEmpty "); } pushToPop(); return stack2.peek(); }}}Copy the code

• Use queues to implement stacks
  • The two queues alternate with each other, keeping only one number at a time

public class QueueToStack { static class MyStack<T> { private Queue<T> queue; private Queue<T> help; public MyStack() { queue = new LinkedList<>(); help = new LinkedList<>(); } public void push(T value) { queue.add(value); } public T pop() { if (! queue.isEmpty()) { while (queue.size() > 1) { help.add(queue.poll()); } T poll = queue.poll(); Queue<T> tmp = queue; queue = help; help = tmp; return poll; } else {throw new RuntimeException(" no data yet "); } } public T peek() { if (! queue.isEmpty()) { while (queue.size() > 1) { help.add(queue.poll()); } T poll = queue.poll(); help.add(poll); Queue<T> tmp = queue; queue = help; help = tmp; return poll; } else {throw new RuntimeException(" no data yet "); } } public boolean isEmpty() { return queue.isEmpty(); }}}Copy the code

• Recursion (using the system stack)

The recursion of Master formula is as follows: T (N) = a * O (N/b) + O (N ^ d) if the log (b, a) > d complexity is O (N ^ log (b, a)) if the log (b, a) < d complexity is O (N ^ d) if the log (b, a) = d, complexity O (N ^ d * logN)Copy the code