GATE CS 2018 (Forenoon) — Question 13

Data StructuresAbstract Data Types (ADTs), Stacks, QueuesMCQ1 mark · −1/3 if wrongEasy

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let \(n\) denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.
Question image
Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
  1. A
    \(\theta(1), \theta(1)\)
  2. B
    \(\theta(1), \theta(n)\)
  3. C
    \(\theta(n), \theta(1)\)
  4. D
    \(\theta(n), \theta(n)\)
Practise the full 2018-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Abstract Data Types (ADTs), Stacks, QueuesTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group