A stack is a linear data structure adhering to the Last-In-First-Out (LIFO) principle. The top of the stack is where elements are added and removed, while the bottom remains fixed.

Common Stack Operations

Standard stack operations include push (add to top), pop (remove from top), and peek (inspect top element), all typically executed in constant O(1) time.

Implementing a Stack with a Linked List

When using a linked list, the head node serves as the stack top. Pushing involves inserting a new node at the head, and popping removes the head node.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node {
    int data;
    struct Node* next;
};

typedef struct {
    struct Node* top;
    int count;
} LinkedStack;

LinkedStack* createStack() {
    LinkedStack* s = (LinkedStack*)malloc(sizeof(LinkedStack));
    s->top = NULL;
    s->count = 0;
    return s;
}

bool isStackEmpty(LinkedStack* s) {
    return s->count == 0;
}

void stackPush(LinkedStack* s, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    s->count++;
}

int stackPop(LinkedStack* s) {
    if (isStackEmpty(s)) {
        printf("Stack underflow.\n");
        exit(1);
    }
    struct Node* temp = s->top;
    int poppedValue = temp->data;
    s->top = s->top->next;
    free(temp);
    s->count--;
    return poppedValue;
}

int stackPeek(LinkedStack* s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return s->top->data;
}

void freeStack(LinkedStack* s) {
    while (!isStackEmpty(s)) {
        stackPop(s);
    }
    free(s);
}

int main() {
    LinkedStack* myStack = createStack();
    stackPush(myStack, 10);
    stackPush(myStack, 20);
    stackPush(myStack, 30);
    printf("Top element: %d\n", stackPeek(myStack));
    printf("Popped: %d\n", stackPop(myStack));
    printf("Popped: %d\n", stackPop(myStack));
    freeStack(myStack);
    return 0;
}

Implementing a Stack with an Array

Using an array, the end of the array is treated as the stack top. A dynamic array can handle resizing automatically.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int* items;
    int capacity;
    int topIndex;
} ArrayStack;

ArrayStack* initArrayStack(int cap) {
    ArrayStack* stk = (ArrayStack*)malloc(sizeof(ArrayStack));
    stk->capacity = cap;
    stk->items = (int*)malloc(cap * sizeof(int));
    stk->topIndex = -1;
    return stk;
}

bool isArrayStackFull(ArrayStack* stk) {
    return stk->topIndex == stk->capacity - 1;
}

bool isArrayStackEmpty(ArrayStack* stk) {
    return stk->topIndex == -1;
}

void arrayStackPush(ArrayStack* stk, int val) {
    if (isArrayStackFull(stk)) {
        printf("Stack overflow.\n");
        return;
    }
    stk->items[++(stk->topIndex)] = val;
}

int arrayStackPop(ArrayStack* stk) {
    if (isArrayStackEmpty(stk)) {
        printf("Stack underflow.\n");
        exit(1);
    }
    return stk->items[(stk->topIndex)--];
}

int arrayStackPeek(ArrayStack* stk) {
    if (isArrayStackEmpty(stk)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return stk->items[stk->topIndex];
}

void destroyArrayStack(ArrayStack* stk) {
    free(stk->items);
    free(stk);
}

int main() {
    ArrayStack* stack = initArrayStack(5);
    arrayStackPush(stack, 5);
    arrayStackPush(stack, 15);
    arrayStackPush(stack, 25);
    printf("Top: %d\n", arrayStackPeek(stack));
    printf("Popped: %d\n", arrayStackPop(stack));
    destroyArrayStack(stack);
    return 0;
}

Comparison of Implementations

An array-based stack generally offers better cache locality and average performance, though occasional resizing can cause O(n) push operations. A linked-list stack provides more consistent O(1) performance for all operations but uses more memory per element due to pointer storage.

Typical Stack Applications

• Browser Navigation: The back button uses a stack; each new page is pushed onto a stack, and going back pops the top page.
• Function Call Management: The call stack manages function contexts, pushing frames for new calls and popping them upon return.
• Undo/Redo Operations: Many applications use stacks to record actions for undo functionality.

Queue

A queue is a linear data structure following the First-In-First-Out (FIFO) rule. Elements are added at the rear and removed from the front.

Common Queue Operations

Standard operations are enqueue (add to rear), dequeue (remove from front), and front (inspect first element), all typically O(1).

Implementing a Queue with a Linked List

The front of the list serves as the queue head, and the rear as the tail. Enqueue adds a node after the tail, dequeue removes the head node.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct QNode {
    int key;
    struct QNode* link;
};

typedef struct {
    struct QNode *head, *tail;
    int length;
} ListQueue;

ListQueue* createQueue() {
    ListQueue* q = (ListQueue*)malloc(sizeof(ListQueue));
    q->head = q->tail = NULL;
    q->length = 0;
    return q;
}

void enqueue(ListQueue* q, int k) {
    struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));
    temp->key = k;
    temp->link = NULL;
    if (q->tail == NULL) {
        q->head = q->tail = temp;
    } else {
        q->tail->link = temp;
        q->tail = temp;
    }
    q->length++;
}

int dequeue(ListQueue* q) {
    if (q->head == NULL) {
        printf("Queue is empty.\n");
        return -1;
    }
    struct QNode* oldHead = q->head;
    int item = oldHead->key;
    q->head = q->head->link;
    if (q->head == NULL) {
        q->tail = NULL;
    }
    free(oldHead);
    q->length--;
    return item;
}

int queueFront(ListQueue* q) {
    if (q->head == NULL) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->head->key;
}

bool isQueueEmpty(ListQueue* q) {
    return q->head == NULL;
}

void freeQueue(ListQueue* q) {
    while (!isQueueEmpty(q)) {
        dequeue(q);
    }
    free(q);
}

int main() {
    ListQueue* q = createQueue();
    enqueue(q, 100);
    enqueue(q, 200);
    printf("Front: %d\n", queueFront(q));
    printf("Dequeued: %d\n", dequeue(q));
    freeQueue(q);
    return 0;
}

Implementing a Circular Queue with an Array

A standard array queue suffers from O(n) dequeue operations due to shifting. A circular array implementation uses front and rear indices with modulo arithmetic to wrap around.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int* arr;
    int frontIdx;
    int rearIdx;
    int maxSize;
    int currentSize;
} CircularQueue;

CircularQueue* initCircularQueue(int size) {
    CircularQueue* cq = (CircularQueue*)malloc(sizeof(CircularQueue));
    cq->maxSize = size;
    cq->arr = (int*)malloc(size * sizeof(int));
    cq->frontIdx = 0;
    cq->rearIdx = -1;
    cq->currentSize = 0;
    return cq;
}

bool isCQFull(CircularQueue* cq) {
    return cq->currentSize == cq->maxSize;
}

bool isCQEmpty(CircularQueue* cq) {
    return cq->currentSize == 0;
}

void cqEnqueue(CircularQueue* cq, int val) {
    if (isCQFull(cq)) {
        printf("Queue is full.\n");
        return;
    }
    cq->rearIdx = (cq->rearIdx + 1) % cq->maxSize;
    cq->arr[cq->rearIdx] = val;
    cq->currentSize++;
}

int cqDequeue(CircularQueue* cq) {
    if (isCQEmpty(cq)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int item = cq->arr[cq->frontIdx];
    cq->frontIdx = (cq->frontIdx + 1) % cq->maxSize;
    cq->currentSize--;
    return item;
}

int cqPeek(CircularQueue* cq) {
    if (isCQEmpty(cq)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return cq->arr[cq->frontIdx];
}

void destroyCQ(CircularQueue* cq) {
    free(cq->arr);
    free(cq);
}

int main() {
    CircularQueue* myQueue = initCircularQueue(3);
    cqEnqueue(myQueue, 7);
    cqEnqueue(myQueue, 14);
    printf("Front: %d\n", cqPeek(myQueue));
    printf("Dequeued: %d\n", cqDequeue(myQueue));
    destroyCQ(myQueue);
    return 0;
}

Typical Queue Applications

• Task Scheduling: Print job queues, restaurant order systems, and network packet buffers.
• Order Processing: E-commerce platforms manage incoming orders in queues.

Double-Ended Queue (Deque)

A deque allows insertion and deletion at both ends, combining stack and queue capabilities.

Common Deque Operations

Operations include addFront, addRear, removeFront, removeRear, getFront, and getRear, all O(1).

Implementing a Deque with a Doubly Linked List

A doubly linked list, with pointers to both next and previous nodes, naturally supports operations at both ends.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct DNode {
    int info;
    struct DNode* prev;
    struct DNode* next;
};

typedef struct {
    struct DNode* first;
    struct DNode* last;
    int numElements;
} DoublyLinkedDeque;

DoublyLinkedDeque* createDeque() {
    DoublyLinkedDeque* dq = (DoublyLinkedDeque*)malloc(sizeof(DoublyLinkedDeque));
    dq->first = dq->last = NULL;
    dq->numElements = 0;
    return dq;
}

bool isDequeEmpty(DoublyLinkedDeque* dq) {
    return dq->first == NULL;
}

void insertFront(DoublyLinkedDeque* dq, int data) {
    struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->info = data;
    newNode->prev = NULL;
    newNode->next = dq->first;
    if (isDequeEmpty(dq)) {
        dq->last = newNode;
    } else {
        dq->first->prev = newNode;
    }
    dq->first = newNode;
    dq->numElements++;
}

void insertRear(DoublyLinkedDeque* dq, int data) {
    struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->info = data;
    newNode->next = NULL;
    newNode->prev = dq->last;
    if (isDequeEmpty(dq)) {
        dq->first = newNode;
    } else {
        dq->last->next = newNode;
    }
    dq->last = newNode;
    dq->numElements++;
}

int deleteFront(DoublyLinkedDeque* dq) {
    if (isDequeEmpty(dq)) {
        printf("Deque empty.\n");
        return -1;
    }
    struct DNode* temp = dq->first;
    int value = temp->info;
    dq->first = dq->first->next;
    if (dq->first == NULL) {
        dq->last = NULL;
    } else {
        dq->first->prev = NULL;
    }
    free(temp);
    dq->numElements--;
    return value;
}

int deleteRear(DoublyLinkedDeque* dq) {
    if (isDequeEmpty(dq)) {
        printf("Deque empty.\n");
        return -1;
    }
    struct DNode* temp = dq->last;
    int value = temp->info;
    dq->last = dq->last->prev;
    if (dq->last == NULL) {
        dq->first = NULL;
    } else {
        dq->last->next = NULL;
    }
    free(temp);
    dq->numElements--;
    return value;
}

int getFront(DoublyLinkedDeque* dq) {
    if (isDequeEmpty(dq)) {
        printf("Deque empty.\n");
        return -1;
    }
    return dq->first->info;
}

int getRear(DoublyLinkedDeque* dq) {
    if (isDequeEmpty(dq)) {
        printf("Deque empty.\n");
        return -1;
    }
    return dq->last->info;
}

void freeDeque(DoublyLinkedDeque* dq) {
    while (!isDequeEmpty(dq)) {
        deleteFront(dq);
    }
    free(dq);
}

int main() {
    DoublyLinkedDeque* d = createDeque();
    insertRear(d, 8);
    insertFront(d, 4);
    insertRear(d, 12);
    printf("Front: %d, Rear: %d\n", getFront(d), getRear(d));
    printf("Removed from front: %d\n", deleteFront(d));
    freeDeque(d);
    return 0;
}

Deque Applications

Deques are versatile. A common use is an undo/redo system with history limits: actions are pushed onto a deque. When the capacity is exceeded, the oldest action (at the front) can be removed, which a simple stack cannot do efficiently.