Queue-Stack related questions

Date: March 31, 2023

Topic: Queue & Stack

Recall

Queue

Usages: Breadth - First Search related problems

Stack

Amortized time vs average time

Notes

• FIFO, First in first out

• 内存里的存放方法：array/ linked list

• 对应java class： ArrayDeque/ LinkedList

• 对应java interface：Queue

• Java api：

  • enqueue：offer( ) - offer at the tail
  • dequeue: poll( ) - poll at the head
  • peek( ) - look at the head without polling it out

• 典型问题: Tree printout by level, Sliding window problems. (Deque: double ends manipulation)

• LIFO, last in first out

• 内存里的存放方法：array/ linked list

• 对应java class： ArrayDeque/ LinkedList

• 对应java interface：Deque

• Java api

  • push: offerFirst( )
  • pop: pollFirst( )
  • top: peekFirst( )

• Stack 移动操作常见特性：

  • 把element从Stack1移到Stack2是反序；
  • 把Stack 1所有元素move到Stack2， 然后直接元素全部（部分）move回Stack1， 则回到原来Stack1元素的顺序不变，amortized的时间复杂度分摊到每一个move的元素的时间往往可以变回O(1)

• average time: 离散变量，数据之间没有联系，比如平均身高

• Amortized time: 数据之间有联系，存在着此消彼长的关系

• Deque：double direction queue

<aside> 📌 SUMMARY:

== 是一个引用比较，即两个对象都指向同一个内存位置 .equals()评估为对象中数值的比较

</aside>

Date: April 1, 2023

Topic: Practice 6 Queue, stack and Deque

Recall

Notes

• 最popular的两种implementation class：ArrayDeque和LinkedList

• ArrayDeque 里不能放null，但LinkedList里可以

• 当你需要一个Queue，使用Queue作为interface，虽然使用Deque也可以实现，但是会让代码想要表达的意思模糊，不推荐使用

• 尽量不要return null，而应该抛出一个带有明确信息的异常，如 "找不到名为'PatientDb'的连接字符串"。这不仅使软件快速失败，而且与常见的空引用异常相比，错误信息也更容易诊断。

• 怎么写一个OOP：

  • 根据use case设计public API（包括signature）
  • 思考实现算法，写出class filed
  • 先实现简单的，再实现复杂的

• Implementation of Stack using LinkedList

  • head 做栈顶

  public class Stack {
  	ListNode head;
  	int size;
  	public Integer pop() {
  		if (head == null) {
  			return null;
  		}
  		size—;
  		ListNode node = head;
  		head = head.next;
      node.next = null;
  		return node.value;
  	} 
  
  	public Integer peek() {
  		if (head == null) {
  			return null;
  		}
  		return head.value;
  	}
  
  	public boolean push(int element) {
  		ListNode newNode = new ListNode(element);
  		newNode.next = head;
  		head = newNode;
  		size++;
  		return true;
  	}
  
  	public int size() {
  		return size;
  	}
  	public boolean isEmpty() {
  		return (size == 0);
  	}
  }
  

• Implementation of Stack using Array

  • 物理意义：head永远指向Stack的顶部，第一个有意义的element，head start with -1；
  • push的逻辑：如果没有full，Array[++head] = val, 否则return false
  • pop的逻辑：如果不是Empty，return Array[head—]; 否则return null

  public class Stack {
  	private int[] stack;
  	private int head;
  	public Stack(int cap) {
  		stack = new int[cap];
  		head = -1;
  	}
  	public Integer pop() {
  		return (head == -1) ? null : stack[head--]; //先return 再- -
  	}
   
  	public Integer peek() {
  		return (head == -1) ? null : stack[head];
  	}
  
  	public boolean push(int element) {
  		if (ifFull()) {
  			return false;
  		}
  		stack[++head] = element;
  		return true;
  	}
  
  	public int size() {
  		return head + 1;
  	}
  
  	public boolean isEmpty() {
  		return (head == -1);
  	}
  
  	public boolean isFull() {
  		size() == stack.length;
  	}
  }
  

• Queue by LinkedList

  public class Queue {
  	ListNode head, tail;
  	int size;
  	public Queue() {
  		
  }
  public Integer pop() {
  	if (head == null) return null; //case 0: empty Queue
  	//case 1: 1 node
  	else if (head.next == null) {
  		ListNode node = head;
  		head = tail = null;
  size--;
  		return node.value;
  } else { 
  	ListNode node = head;
  	head = head.next;
  	node.next = null;
  	size--;
  	return node.value;
  }
  	
  }
   
  	public Integer peek() {
  	if (head == null) return null;
  	return head.value;
  }
  
  	public boolean push(int element) {
  	ListNode newNode = new ListNode(element);
  	if (head == null)
  		head = tail = newNode;
  	else {
  		tail.next = newNode;
  		tail = newNode;
  }
  size++;
  return true;
  }
  
  	public int size() {
  	return size;
  }
  
  	public boolean isEmpty() {
  	return size == 0;
  }
  
  }
  

• Queue by Array

• Circular Array环形数组： index of array.length ≤> index of 0

<aside> 📌 SUMMARY:

</aside>