Stack: A LIFO Structure

A stack is a linear data structure that restricts ensertion and deletion to one end—the top. This end is known as the top, while the opposite end is the bottom. Inserting an element into a stack is called pushing, which places the new item above the current top. Removing an element is referred to as popping, which removes the topmost item, promoting the next item to become the new top.

Stacks follow the Last In, First Out (LIFO) principle. They can be implemented using either static arrays (static stack) or dynamic linked lists (linked stack). Here, we focus on implementing a dynamic array-based stack.

Stack Structure Definition

#define StackDataType int

typedef struct Stack {
    StackDataType* data;
    int top;         // Points to the next available position
    int capacity;
} Stack;

The top field starts at 0, indicating the first free slot—this allows it to double as a size counter. The data pointer manages dynamically allocated memory for elements.

Initialization

void StackInit(Stack* pST) {
    assert(pST);
    pST->data = NULL;
    pST->top = pST->capacity = 0;
}

Push Operation

Before inserting, insure there's space:

static void ResizeIfNecessary(Stack* pST) {
    assert(pST);
    if (pST->top == pST->capacity) {
        int new_capacity = (pST->capacity == 0) ? 5 : pST->capacity * 2;
        StackDataType* tmp = (StackDataType*)realloc(pST->data, sizeof(StackDataType) * new_capacity);
        if (!tmp) {
            printf("Memory reallocation failed\n");
            exit(-1);
        }
        pST->data = tmp;
        pST->capacity = new_capacity;
    }
}

void StackPush(Stack* pST, const StackDataType val) {
    assert(pST);
    ResizeIfNecessary(pST);
    pST->data[pST->top] = val;
    pST->top++;
}

Pop Operation

void StackPop(Stack* pST) {
    assert(pST);
    assert(pST->top > 0);  // Ensure stack is not empty
    pST->top--;
}

Access Top Element

StackDataType StackTop(const Stack* pST) {
    assert(pST);
    assert(!StackEmpty(pST));
    return pST->data[pST->top - 1];
}

Since top points to the next position, subtracting 1 gives the actual top value.

Check for Empty Stack

bool StackEmpty(const Stack* pST) {
    assert(pST);
    return pST->top == 0;
}

Get Stack Size

int StackSize(const Stack* pST) {
    assert(pST);
    return pST->top;
}

Destroy Stack

void StackDestroy(Stack* pST) {
    assert(pST);
    free(pST->data);
    pST->data = NULL;
    pST->top = pST->capacity = 0;
}

---

Queue: A FIFO Structure

A queue is a linear structure where insertions ocurr at the rear and deletions happen at the front. It follows the First In, First Out (FIFO) model. The front is the head, and the rear is the tail.

We implement a linked queue without a sentinel node.

Queue Node and Structure

typedef int QueueDataType;

typedef struct QueueNode {
    QueueDataType data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* head;
    QueueNode* tail;
} Queue;

Tracking both head and tail simplifies enqueue and dequeue operations.

Initialization

void QueueInit(Queue* pQue) {
    assert(pQue);
    pQue->head = pQue->tail = NULL;
}

Enqueue (Insert at Rear)

static QueueNode* CreateNode(const QueueDataType val) {
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if (!new_node) {
        printf("Allocation failed\n");
        exit(-1);
    }
    new_node->data = val;
    new_node->next = NULL;
    return new_node;
}

void QueuePush(Queue* pQue, const QueueDataType val) {
    assert(pQue);
    QueueNode* new_node = CreateNode(val);
    if (!pQue->head) {
        pQue->head = pQue->tail = new_node;
    } else {
        pQue->tail->next = new_node;
        pQue->tail = new_node;
    }
}

Dequeue (Remove from Front)

void QueuePop(Queue* pQue) {
    assert(pQue);
    assert(!QueueEmpty(pQue));
    QueueNode* temp = pQue->head;
    pQue->head = pQue->head->next;
    free(temp);
    if (!pQue->head) {
        pQue->tail = NULL;  // Reset tail if queue becomes empty
    }
}

Always update tail when removing the last node to prevent dangling pointers.

Check if Queue is Empty

bool QueueEmpty(const Queue* pQue) {
    assert(pQue);
    return pQue->head == NULL;
}

Retrieve Front and Rear Values

QueueDataType QueueFront(const Queue* pQue) {
    assert(pQue);
    assert(!QueueEmpty(pQue));
    return pQue->head->data;
}

QueueDataType QueueBack(const Queue* pQue) {
    assert(pQue);
    assert(!QueueEmpty(pQue));
    return pQue->tail->data;
}

Count Elements

size_t QueueSize(const Queue* pQue) {
    assert(pQue);
    size_t count = 0;
    QueueNode* curr = pQue->head;
    while (curr) {
        count++;
        curr = curr->next;
    }
    return count;
}

Destroy Queue

void QueueDestroy(Queue* pQue) {
    assert(pQue);
    QueueNode* curr = pQue->head;
    while (curr) {
        QueueNode* next = curr->next;
        free(curr);
        curr = next;
    }
    pQue->head = pQue->tail = NULL;
}

---

Practice Challenges

• Implement a queue using two stacks (LeetCode 232)
• Implement a stack using a queue (LeetCode 225)