---
title: "Stack and queue using linked list"
subject: "Data Structure and Algorithm"
chapter: 4
key: "semester_4/data_structure_and_algorithm:stack-queue-singly-linked-list"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/stack-queue-singly-linked-list
site: BCT Engineering
---

# Stack and queue using linked list

Data Structure and Algorithm · Chapter 4: Linked lists

- Asked in: 2075 Baisakh, 10 marks; 2070 Magh, 5 marks (asked 2 times)
- Video: [Linked List Implementation of Stacks (Part 1)](https://www.youtube.com/watch?v=0-kkDfCOXOI) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/stack-queue-singly-linked-list
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-4

## Question

Write algorithms of implementation of stack and queue using singly linked list.

## Short answer

Stack: push inserts a node at head, pop removes from head; top pointer tracks the list. Queue: enqueue adds a node at rear, dequeue removes from front; front and rear pointers are maintained. Both use dynamic allocation, offer O(1) operations, and check for underflow/overflow.

## Answer

Both use the node `struct node { int info; struct node *next; };`. Memory is taken from the heap with `malloc`, so there is no fixed limit (overflow only when the heap is full).

#### Stack using a singly linked list
The **top** is the head of the list: push and pop both work at the front, so both are O(1).
```text
top
 |
 v
[30|*]->[20|*]->[10|NULL]
```
```c
struct node { int info; struct node *next; };
struct node *top = NULL;

void push(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (p == NULL) { printf("Overflow\n"); return; }
    p->info = x;
    p->next = top;        /* new node points to old top */
    top = p;              /* top moves to the new node  */
}

int pop(void) {
    struct node *p; int x;
    if (top == NULL) { printf("Underflow\n"); return -1; }
    p = top;
    x = p->info;
    top = top->next;      /* second node becomes top */
    free(p);
    return x;
}
```
Algorithm for push: (1) create node p; (2) p->info = x; (3) p->next = top; (4) top = p.
Algorithm for pop: (1) if top = NULL, underflow; (2) p = top; (3) x = p->info; (4) top = top->next; (5) free(p); return x.

#### Queue using a singly linked list
Keep two pointers: **front** (where deletion occurs) and **rear** (where insertion occurs). Insert at the rear, delete from the front.
```text
front                    rear
 |                        |
 v                        v
[10|*]->[20|*]->[30|NULL]
```
```c
struct node *front = NULL, *rear = NULL;

void enqueue(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (p == NULL) { printf("Overflow\n"); return; }
    p->info = x;  p->next = NULL;
    if (rear == NULL)          /* queue empty */
        front = rear = p;
    else {
        rear->next = p;        /* link after the last node */
        rear = p;
    }
}

int dequeue(void) {
    struct node *p; int x;
    if (front == NULL) { printf("Underflow\n"); return -1; }
    p = front;
    x = p->info;
    front = front->next;
    if (front == NULL) rear = NULL;   /* queue became empty */
    free(p);
    return x;
}
```
Enqueue steps: create node with next = NULL; if queue empty then front = rear = node; else rear->next = node, rear = node.
Dequeue steps: if front = NULL underflow; p = front; front = front->next; if front becomes NULL set rear = NULL; free(p).

Both operations are O(1) and no shifting is needed.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In a stack built on a singly linked list, where is the top?
   A. At the last node
   B. At the middle node
   C. At a separate array
   D. At the head of the list, so push and pop work at the front
   Answer: D. Working at the head makes both push and pop O(1). (Key point: Stack top)

2. Which sequence correctly pushes x?
   A. Create p; p->info = x; p->next = top; top = p
   B. top = p; p->next = top
   C. Create p; top->next = p; top = NULL
   D. p->next = NULL; top = top->next
   Answer: A. The new node must point to the old top before top is moved to it. (Key point: Push steps)

3. In a linked queue, where do insertion and deletion occur?
   A. Insert at the front, delete from the rear
   B. Insert at the rear, delete from the front
   C. Both at the front
   D. Both at the rear
   Answer: B. FIFO order requires adding at one end and removing at the other, using front and rear pointers. (Key point: Queue ends)

4. In dequeue, why is rear set to NULL when front becomes NULL?
   A. To make the queue circular
   B. To free the front node
   C. The queue became empty and rear would otherwise point to a freed node
   D. To reset the node count
   Answer: C. Without this, rear dangles and the next enqueue would fail. (Key point: Dequeue special case)

## Related in Data Structure and Algorithm

- [Insert and delete before a node, singly linked](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asingly-insert-delete-before) — Data Structure and Algorithm, chapter 4
- [Doubly vs singly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-vs-singly-linked) — Data Structure and Algorithm, chapter 4, asked 2×
- [Singly vs doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asingly-vs-doubly-linked) — Data Structure and Algorithm, chapter 4
- [Dynamic implementation of queue](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adynamic-queue-linked-algorithm) — Data Structure and Algorithm, chapter 4
- [Circular queue using linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-queue-linked-list) — Data Structure and Algorithm, chapter 4
- [Static vs dynamic implementation of stack](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-static-vs-dynamic) — Data Structure and Algorithm, chapter 2