Chapter 5: Stacks and Queues

Question 1

Which of the following options is a true queue implementation using linked lists?

1. If, in the enqueue operation, new data elements are added at the start of the list, then the dequeue operation must be performed from the end.
2. If, in the enqueue operation, new data elements are added to the end of the list, then the enqueue operation must be performed from the start of the list.
3. Both of the above.
4. None of the above.

Solution

B is correct. The queue data structure follows a FIFO order, hence data elements must be added to the end of the list, and then removed from the front.

Question 2

Assume a queue is implemented using a singly linked list that has head and tail pointers. The enqueue operation is implemented at head, and the dequeue operation is implemented at the tail of the queue. What will be the time complexity of the enqueue and dequeue operations?

Solution

The time complexity...