Queue & Stack

Java Basic Knowledge 2:01:53
- Student[] array = new Student[10]; 表示10size(个) null
- 八种primitive type：(整数)int, short, long, (小数)float, double,|| boolean, char, byte
- List: no consecutive memory, reference by next by O(n) time.
- Array & List 2:09:13
  - size: array not changeable final; List dynamic, changeable
  - access: array O(1) List(n)

库函数当中，list怎么定义 2:13:47

overloading:只能根据input的个数或数据类型产生不同的do sth
overloading: in compelling time to check
overriding: in running time

class listNode<K,V>{ //TODO: Generics
    //fields
    V val;
    ListNode prev;
    ListNode next;
    K key; //两个范型，eg: Map
    
    //methods
    ListNode(V val){// overloading
        value = val;
        prev = null;
        next = null;
    } 
    ListNode(){         /// No!  不是在进行函数调用而是创建class
        this(0);  ///dont use ListNode(0);avoid stack overflow
    }             // null
}

Design a LinkedList 2:37:47

linked class里有什么
- fields: head(single linkedList); head & tail(double linkedList)
- methods:
  - constructor: 初始化fields
  - getVal: return the value that index contains(input: index; output: 范型value)； while loop: 所停留的cur; need corner case
  - addHead: input(is value); output()
    need a boolean to so can be added in or not
    涉及size增减
  - addTail:
    new node
    head also need to be renewed

public class linkedList<V>{ //TODO:Generics
    //fields
    private ListNode<V> head;
    private ListNode<V> tail;
    private int size;
    
    
    //methods
    LinkedList(){
        head = null;
        tail = null;
        size = 0;
    }
    
    public E getVal(int index){
        if(head == null || index < 0 || index > size-1){
            return -1; // throw new IllegalArgumentsException("getval()")
        }
        ListNode<E> cur = head;
        while(index > 0){
            cur = cur.next;
            Index--;
        }
        return cur.val;
    }
    
    public void addHead(E val){
        ListNode<E> newHead = new ListNode<E>(val);
        if(head == null){
            tail = newHead;
        }else{
            newHead.next = head;
            head.prev = newHead;
        }
        head = newHead;
        size++;
    }
    
    public void addTail(E val){
        ListNode<E> newTail = newListNode<E>(val);
        if(tail == null){
            head = newTail
        }else{
            tail.next = newTail;
            newTail.prev = tail;
        }
        tail = newTail;
        size++
    }
    public int getSize(){
        return size;
    }

}

interface & class 第八节10：10
- list is an interface with methods to be implemented
- interface里面只有methods,只有function signature，没有具体实现
- concrete class既有fields 也有methods, and all are implemented
  - abstract class 是抽象的 methods可以不实现
ArrayList 21:55
- 注意什么：expand的method
  - capacity and size: capacity能放多少，size真正放了多少
- ArrayList is used as a resizable array, initial 10 capacity, 1.5/2 times if expand. 20 size 的连续内存空间

Stack is like a cup, we need to push the ball(elements) into the cup,
- first in last out.
Queue is like a tube
- first in first out

Q1 L232 How to implement queue by stacks 1:56:22

stack 1 is used to store/receive the new offered/coming elements/data
stack 2 is used to pop out the elements/data, check stack2 is empty before pop
offer an new element
- just push it into stack1
poll an element form MyQueue:
- case1: if stack2 is empty, move all the elements from 1 to 2
- case2: if stack2 is not empty, just go ahead to pop out
- (if both are empty ,return null)

public class MyQueue<E> implements Queue{ //TODO Generics
    //fields
    private Stack<E> stackIn;
    private Stack<E> stackOut;

    //methods
    public MyQueue(){
        stackIn = new Stack<E>;
        stackOut = new Stack<E>;
    }
    public void offer(E val){
        stackIn.push(val);//boxing
    }
    public E poll(){
        move();
        return stackOut.isEmpty()?null : stackOut.pop();
    }
    public E peek(){
        move();
        return stackOut.isEmpty()?null : stackOut.peek();
    }
    private void move(){
        if(stackOut.isEmpty()){
            while(isStackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }
    }
}

Q2 L225 How to implement stack by queues 第九节

clarify the limitation of queues
S1: Deque is Queue?
S2: use two Queues push is O(1), pop is O(n)
- one is for store
- one is for pop out
if we want to decrease the TC for pop S3: use one Queue

Q3 L155 min Stack

middle: array2/n medium: need to be sorted

S1:--> wrapper into one pair so one stack
- stack1:used to store the data
- stack2: to store the minimum value consistent with stack1
- stack2.push(stack2.peek())
- if stack2 is null, push into stack2

public class minStack{ // TODO: Generics
    //fields
    private Stack<Integer> stackEle;
    private Stack<Integer> stackMin;
    
    //methods
    public MinStack(){
        stackEle = new Stack<Integer>();
        stackMin = new Stack<Integer>();
    }
    public void push(int val){
        stackEle.push(val);
        if(stackMin.empty() || stackMin.top()>= val){
            stackMin.puch(val);
        }else{
            stackMin.push(stackMin.top);
        }
    }
    public Integer pop(){
        if(stackEle.empty()) return null;
        stackMin.pop();
        return stackEle.pop();
    }
    public Integer top(){
        if(stackEle.empty()) return null;
        return stackEle.top();
    }
    public Integer getMin(){
        if(stack_min.empty()) return null;
        return stackMin.top();
    }


}

public class MinStack{ //TODO: Generics
    //fields
    private Stack<Integer> stack;
    
    //methods
    public MinStack(){
        stack = new Stack<Integer>();
    }
    public void push(int val){
        int a = val;
        int b =(stack.empty() || stack.top() >= val)?
            stack.push(val):stack.push(stack.top());
        stack.push(new Pair(a,b));
    }
    pubilc Integer pop(){
        if(stack.empty()) return null;
        Pair p = stack.pop();
        return p.a;
    }

    public Integer top(){
        if(stack.empty()) return null;
        Pair p = stack.pop();
        return p.a;
    }
    public Integer getMin(){
        if(stack.empty()) return null;
        Pair p = stack.top()
        return p.b;
    }
}

S2: optimize
- repeat use stack1
- 避免冗余，不push
- 大于最小值的时候，不往里push，小于等于ok

public class MinStack{//TODO: Generics
    //fields
    private Stack<Integer> minStack;
    private Stack<Integer> eleStack;
    
    //methods
    public MinStack(){
        eleStack = new Stack<Integer>;
        minStack = new Stack<Integer>;
        
    }
    public void push(int val){
        if(minStack.isEmpty() || val <= minStack.top()){
            minStack.push(val);
        }
    }
    
    public Integer pop(){ // ==??
        if(eleStack.isEmoty()) return null;
        if(eleStack.top() == minStack.top()) minStack.pop();
        return mainStack.pop();
    }
    public Integer top(){
        if(eleStack.empty()) return null;
        return minStack.top();
    }
    public Integer min(){
        if(minStack.isEmpty()) return null;
        return minStack.top();
    }
    

}

S4：不考虑时间复杂度
- 非线性数据结构
Github
- 存对于上一个版本的偏移量

Q4 汉诺塔

把一个unsorted stack 用3个stack进行sort
- selection sort; use a min
2个stack
- use a counter = how many rounds
- stack只能从尾出，total - counter = 从尾巴出几个回到stack1里

由近及远看的时候会用到stack

Calculator:

a + b * c: use two stacks
- stack1 is for numbers
- stack2 is for the calculate sign
- should read the sign first
a * b + c * d --> ab* cd* + --> reverse polish notation
- use only one stack
binary expression tress vs syntax tree
- 自下向上 recursion

* *

a b c d

PreviousLinkedList NextBinary (Search) Tree & Divide Conquer

Last updated 4 years ago

Was this helpful?