Implement a Queue Using a Linked List

Easy15 min

Topics

BasicsQueueLinked List

Companies

TCSInfosysWipro

Implement a queue with a linked list and run a list of operations on it. ops[i] is one of "enqueue" (add args[i] at the back), "dequeue" (remove and report the front item, or −1 if empty), "front" (report the front item, or −1), "isEmpty" (1 or 0) and "size". Return everything reported, in order. A linked list grows one node at a time, so the queue never fills up and nothing is ever shifted. The front is easy to reach through head; the back is the interesting part. Keeping a tail pointer alongside head turns enqueue from an O(n) walk into an O(1) link.

Test Case 1:

Input:ops = ["enqueue","enqueue","dequeue","front","size"], args = [5, 8, 0, 0, 0]

Output:[5, 8, 1]

Explanation:The same queue behaviour as with an array — only the storage differs.

Test Case 2:

Input:ops = ["front","enqueue","front"], args = [0, 3, 0]

Output:[-1, 3]

Explanation:front on an empty queue is −1.

Constraints

◆1 ≤ ops.length ≤ 1000
◆ops[i] is one of "enqueue", "dequeue", "front", "isEmpty", "size"
◆args[i] is the value for "enqueue" and 0 otherwise

Try the Dry Run

Mode

Approach

Approach & Solutions

Head Pointer OnlyBrute

Store the items as a chain of nodes, each pointing to the next, with a head pointer at the front. Dequeue is easy: move head to head.next. But to enqueue, the code must walk from head to the last node to attach the new one, which takes O(n) steps.

TimeO(n) per enqueue

SpaceO(n)

Java

Try it out

class Solution {
    static class QNode {
        int value;
        QNode next;

        QNode(int value) {
            this.value = value;
        }
    }

    public int[] queueOps(String[] ops, int[] args) {
        QNode head = null;
        int size = 0;
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < ops.length; i++) {
            if (ops[i].equals("enqueue")) {
                QNode node = new QNode(args[i]);
                if (head == null) {
                    head = node;
                } else {
                    QNode cur = head;
                    while (cur.next != null) {
                        cur = cur.next;
                    }
                    cur.next = node;
                }
                size++;
            } else if (ops[i].equals("dequeue")) {
                if (head == null) {
                    out.add(-1);
                } else {
                    out.add(head.value);
                    head = head.next;
                    size--;
                }
            } else if (ops[i].equals("front")) {
                out.add(head == null ? -1 : head.value);
            } else if (ops[i].equals("isEmpty")) {
                out.add(head == null ? 1 : 0);
            } else if (ops[i].equals("size")) {
                out.add(size);
            }
        }
        return out.stream().mapToInt(Integer::intValue).toArray();
    }
}

Head and Tail PointersOptimal

Keep a second pointer, tail, at the last node. Enqueue attaches the new node after tail and moves tail to it — no walk needed. Dequeue moves head forward; if that empties the queue, tail must be cleared too. Both ends are now reachable in one step, so every operation is O(1).

TimeO(1) per operation