Queue & Stack

Yue included in Algorithms

2022-04-03 691 words 4 minutes

Contents

Theory

Integer –> null (Zero False Null principle)

Queue

First In First Out: Breadth-First Search related problems.

Java api:

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

Stack

Last In First Out

Java api:

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

Characteristics

Move all elements from stack1 to stack2, the order in the stack2 is reversed.
Move all elements from stack1 to stack2 and then move back to stack1, the amortized time complexity for every element which is moved is O(1).

Amortized time vs Average time

Average case running time: The expected behavior when the input is randomly drawn from a given distribution. The average case running time of an algorithm is an estimate of the running time for an “average” input. Often it is assumed that all inputs of a given size are equally likely.
Amortized running time: Here the tiem required to perform a sequence of operations is averaged over all the operations performed. Amortized analysis can be used to show that the average cost of an operation is small, if one averages over a sequences of operations, even though a simple operation a expensive. Amortized analysis guarantees the average performance of each operation in the worst case.
Worst case running time: The behavior of the algorithm with respect to the worst possible case of the input instance. The worst case running time of an algorithm is an upper bound on th erunning time for any input. Knowing it gives us a guarantee that the algorithm will never take any longer.

When we need to linearly scan a string/array and continuously look back the newest element in the left, we can use stack.

Data Structure	In Memory	Java Class	Java Interface
queue (FIFO)	array/linked list	ArrayDeuqe/ArrayList	Queue
stack (LIFO)	array/linked list	ArrayDeuqe/ArrayList	Deque
deque	array/linked list	ArrayDeuqe/ArrayList	Deque

Algorithm Problems

Using `linked list` to implement a `Stack`

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


public class Stack {
	private ListNode head;
	private int size;

	public Stack() {
		this.head = null;
		this.size = 0;
	}

	public Integer pop() {
		if (size == 0) {
			return null;
		} else {
			ListNode prevHead = head; //
			prevHead.next = null;
			head = head.next;
			size --;
			return prevHead.value; //
		}
	}

	public Integer peek() {
		if (size == 0) {
			return null;
		} else {
			return head.value;
		}
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		if (size == 0) {
			return false;
		} else {
			return true;
		}
	}

	public boolean push(int ele) {
		ListNode newHead = new ListNode(ele);
		newHead.next = head;
		head = newHead;
		size ++; //
		return true;
	}
}

Using `linked list` to implement a `Queue`

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Queue {
	ListNode head;
	ListNode tail;
	int size;

	public void offer(int value) {
		if (head == null) {
			head = new ListNode(value);
			tail = head; 
		} else {
			tail.next = new ListNode(value);
			tail = tail.next;
		}
	}


}

Using `Array` to implement a `Stack`

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


public class Stack {
	private int[] array;
	private int head;

	public Stack(int cap) {
		this.array = new int[cap];
		this.head = 0;
	}

	public Integer pop() {
		return isEmpty() ? null : array[--head];
	}

	public Integer peek() {
		return isEmpty() ? null : array[head-1];
	}

	public boolean push(int ele) {
		if (isFull()) {
			return false;
		}
		array[head++] = ele;
		return true;
	}

	public int size() {
		return head;
	}

	public boolean isEmpty() {
		return head == 0;
	}

	public boolean isFull() {
		return head == array.length;
	}
}

Contents

Queue & Stack

Theory

Queue

Stack

Characteristics

Algorithm Problems

Using linked list to implement a Stack

Using linked list to implement a Queue

Using Array to implement a Stack

Using Array to implement a Queue

Using `linked list` to implement a `Stack`

Using `linked list` to implement a `Queue`

Using `Array` to implement a `Stack`

Using `Array` to implement a `Queue`