Unit 1: Stacks, queues and lists

A stack is a linear data structure that follows LIFO (Last In, First Out): the last element inserted is the first removed. Insertion is PUSH and deletion is POP, both at the TOP.

• Array representation: an array STACK[MAX] and a variable TOP (−1 when empty).
• Linked representation: each push adds a node at the start of a linked list; the list's head is TOP. No overflow until memory runs out.

Other operations: PEEK (read the top without removing it), isEmpty and isFull. All are O(1).

• Infix: operator between operands — A + B
• Prefix (Polish): operator before operands — + A B
• Postfix (Reverse Polish): operator after operands — A B +

Postfix needs no brackets and is easy for a computer to evaluate with a stack.

Scan left to right: push operands; when an operator appears, pop two operands (the first popped is the right operand), apply the operator and push the result. The final value on the stack is the answer.

So 5 3 + 2 × = 16.

• Prefix evaluation: scan right to left; push operands; on an operator pop two operands (first popped is the left operand), apply and push. − × + 2 3 4 5 → (2 + 3) × 4 − 5 = 15.

A queue is a linear data structure that follows FIFO (First In, First Out). Insertion (enqueue) happens at the REAR; deletion (dequeue) happens at the FRONT.

• Array representation: QUEUE[MAX] with FRONT and REAR (both −1 when empty).
• Linked representation: a linked list with pointers to the front and rear nodes; insert at the rear, delete from the front.

A circular queue connects the last position back to the first, so freed spaces are reused. Positions move with modulo arithmetic:

• REAR = (REAR + 1) mod MAX, FRONT = (FRONT + 1) mod MAX
• Full when (REAR + 1) mod MAX = FRONT; empty when FRONT = −1.

cstruct node { int data; struct node *next; };

/* Linked stack: push and pop at the head (top) */
struct node *top = NULL;
void push(int x) {
    struct node *n = malloc(sizeof *n);
    n->data = x; n->next = top; top = n;
}
int pop(void) {
    if (top == NULL) { printf("Underflow\n"); return -1; }
    struct node *t = top; int x = t->data;
    top = top->next; free(t); return x;
}

/* Linked queue: insert at rear, delete at front */
struct node *front = NULL, *rear = NULL;
void enqueue(int x) {
    struct node *n = malloc(sizeof *n);
    n->data = x; n->next = NULL;
    if (rear == NULL) front = rear = n;
    else { rear->next = n; rear = n; }
}
int dequeue(void) {
    if (front == NULL) { printf("Underflow\n"); return -1; }
    struct node *t = front; int x = t->data;
    front = front->next; if (front == NULL) rear = NULL;
    free(t); return x;
}

• Linked versions never overflow (until memory runs out) and grow and shrink as needed, at the cost of a pointer per element.

A linked list is a linear collection of nodes, where each node contains data and a pointer (link) to the next node. The first node is reached through a pointer called START (or HEAD); the last node's link is NULL.

• Traversal: start with ptr = start; while ptr != NULL, process ptr->data and move ptr = ptr->next.
• Search: traverse and compare each node's data with the item: O(n).

• Insert at end: traverse to the last node and set last->next = newnode, with newnode->next = NULL.
• Insert after a given node: newnode->next = loc->next; loc->next = newnode;
• Delete: make the previous node skip the deleted one: prev->next = loc->next; then free(loc). Deleting the first node changes START.

• Doubly linked list: each node has two pointers, prev and next, so it can be traversed in both directions and a node can be deleted without searching for its predecessor. It uses more memory.
• Circular linked list: the last node points back to the first instead of NULL, so the list can be traversed from any node. It is useful for round-robin scheduling.