Stack/Queue

Question 1

What are the 4 operations of queues?

Answer 1

enqueue(i)–inserts element i at the tail end of the queue;
dequeue()–removes the element at the head of the queue and return its value.

And two additional operators provided for convenience:

size()–returns current size of the queue;
peek()–peeks at the element at the head of the queue without changing the queue.

Question 2

How does the average runtime for “popping” elements off the top of a stack compare with the average runtime for “dequeuing” elements from a queue?

Answer 2

To pop an element off of a stack, you just need to remove that element and the rest of the elements stay where they are. So the runtime is O(1).

However, to dequeue the element at the head of a queue, all the other elements need to move forward one, so the runtime isO(n) , with n being the number of elements before any number is dequeued.

Question 3

What is one of the major downfalls of linear queues?

Answer 3

one of the major downfalls of traditional linear queues is that they can be slow. It takes time to shift all the elements along during a dequeuing.

Question 4

What are circular queues?

Answer 4

circular queues, instead of all the elements needing to shift toward the head, we simply change the position of the head!

Question 5

What is the runtime of circular queues?

Answer 5

In fact, circular queues take the runtime down fromO(n) to O(1).