Linked Representation Of Stack And Queue

Linked lists can be used to build stacks and queues.

Linked Stack

A stack follows:

LIFO = Last In, First Out

Like a pile of plates.

Representation

Use the head of the linked list as the top of the stack.

Top
 |
 v
[30|*] -> [20|*] -> [10|NULL]

Stack Operations

Push

Insert at the front.

push(top, x):
    newNode = create node
    newNode.data = x
    newNode.next = top
    top = newNode

Time: O(1)

Pop

Delete from the front.

pop(top):
    if top == NULL:
        underflow
    temp = top
    top = top.next
    delete temp

Time: O(1)

Peek

Read the front node.

Time: O(1)

Linked Queue

A queue follows:

FIFO = First In, First Out

Like people standing in a line.

Representation

Keep two pointers:

• front
• rear

Front                         Rear
 |                              |
 v                              v
[10|*] -> [20|*] -> [30|NULL]

Queue Operations

Enqueue

Insert at the rear.

enqueue(front, rear, x):
    newNode = create node
    newNode.data = x
    newNode.next = NULL

    if rear == NULL:
        front = rear = newNode
        return

    rear.next = newNode
    rear = newNode

Time: O(1)

Dequeue

Delete from the front.

dequeue(front, rear):
    if front == NULL:
        underflow

    temp = front
    front = front.next

    if front == NULL:
        rear = NULL

    delete temp

Time: O(1)

Complexity Summary

Why Linked Lists Work Well Here

• insertion/deletion at ends can be done with pointer updates
• no fixed size is required
• overflow happens only when memory is full