Stacks and Queues

Question 1

Stacks

Answer 1

• Imagine a stack of books on a table. You add/remove books only from the top (LIFO)
• It’s a dynamic array under the hood. Also can be implemented with a singly linked list
• Push and pop are synonyms for add/remove operations

Question 2

Queues

Answer 2

• Imagine a line of people waiting to get into a theater. The first person that is in the line is the first that enters the theater (FIFO)
• Typically implemented with a doubly linked list
• Enqueue and dequeue are synonyms for add/remove operations

Question 3

Space-time complexities - Stack

Answer 3

• Pushing and popping operations are constant operations. They’re O(1) ST
• Peeking operation on the top of the stack is a constant operation. It’s O(1) ST
• Searching for an element is a linear operation. It’s O(N) T, O(1) S
• Initializing a stack is a linear operation. It’s O(N) ST

Question 4

Space-time complexities - Queue

Answer 4

• Enqueuing and dequeuing operations are constant operations. They’re O(1) ST
• The peeking operation on the top of the queue is a constant operation. It’s O(1) ST
• Searching for an element is a linear operation. It’s O(N) T, O(1) S
• Initializing a queue is a linear operation. It’s O(N) ST

Question 5

Complex structures

Answer 5

• A stack can be transformed into a max/min stack, where you have also a reference to the maximum/minimum element
• Priority queues are those where you have references to elements with more priority