Core Concepts of Stack and Queue

A stack follows the Last-In-First-Out (LIFO) principle, while a queue operates on First-In-First-Out (FIFO). In C++'s Standard Template Library (STL), both std::stack and std::queue are implemented as container adapters rather than standalone containers. They provide a specific interface by wrapping an underlying container type, which is std::deque by default.

Container adapters do not expose iterators because their access patterns are restricted: stacks only allow access at the top, and queues only at the front and back. The underlying container can be changed; for example, a stack can be initialized with std::vector or std::list as its internal data structure.

Common STL implementations include HP STL, P.J. Plauger STL, and SGI STL. The GCC compiler typically uses SGI STL.

---

Parentheses Validation Using Stack

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed in the correct order by the same type of brackets.

The stack data structure is ideal for this symmetrical matching problem. When an opening bracket is encountered, push the corresponding closing bracket onto the stack. When a closing bracket is encountered, check if it matches the top of the stack. If the stack is empty when processing a closing bracket or if the types mismatch, the string is invalid.

Mismatch conditions include:

1. More left brackets than right brackets (stack not empty after traversal).
2. Mismatched bracket types.
3. More right brackets than left brackets (stack empty before traversal finishes).

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

bool checkPair(char top, char current) {
    if (top == '(') return current == ')';
    if (top == '[') return current == ']';
    if (top == '{') return current == '}';
    return false;
}

bool isValidParentheses(char* expr) {
    int len = strlen(expr);
    char bracketStack[len];
    int topIndex = -1;

    for (int i = 0; i < len; i++) {
        char ch = expr[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            bracketStack[++topIndex] = ch;
        } else {
            if (topIndex == -1) return false;
            if (!checkPair(bracketStack[topIndex], ch)) return false;
            topIndex--;
        }
    }
    return topIndex == -1;
}

---

Adjacent Duplicate Removal with Stack

Given a string S consisting of lowercase English letters, repeatedly remove adjacent duplicate letters. Return the final string after all such removals.

This is essentially a matching problem similar to parentheses validation. Use a stack to store characters. For each character, if it matches the top of the stack, pop the stack. Otherwise, push the character onto the stack.

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

char* deduplicateAdjacent(char* str) {
    int n = strlen(str);
    char* resStack = (char*)malloc((n + 1) * sizeof(char));
    int stackPtr = 0;

    for (int i = 0; i < n; i++) {
        char curr = str[i];
        if (stackPtr > 0 && resStack[stackPtr - 1] == curr) {
            stackPtr--;
        } else {
            resStack[stackPtr++] = curr;
        }
    }
    resStack[stackPtr] = '\0';
    return resStack;
}

---

Evaluating Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN). Valid operators are +, -, *, /. Each operand may be an integer or another RPN expression. Division truncates toward zero.

In RPN, operators follow their operands. A stack is used: push numbers on to the stack; when an operator is encountered, pop two numbers, perform the operation, and push the result back.

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

typedef struct {
    int* items;
    int capacity;
    int top;
} IntStack;

IntStack* createStack(int cap) {
    IntStack* s = (IntStack*)malloc(sizeof(IntStack));
    s->items = (int*)malloc(cap * sizeof(int));
    s->capacity = cap;
    s->top = -1;
    return s;
}

void push(IntStack* s, int val) { s->items[++(s->top)] = val; }
int pop(IntStack* s) { return s->items[(s->top)--]; }
int isEmpty(IntStack* s) { return s->top == -1; }

int evalRPN(char** tokens, int tokenCount) {
    IntStack* numStack = createStack(tokenCount);
    for (int i = 0; i < tokenCount; i++) {
        if (strcmp(tokens[i], "+") == 0) {
            int b = pop(numStack);
            int a = pop(numStack);
            push(numStack, a + b);
        } else if (strcmp(tokens[i], "-") == 0) {
            int b = pop(numStack);
            int a = pop(numStack);
            push(numStack, a - b);
        } else if (strcmp(tokens[i], "*") == 0) {
            int b = pop(numStack);
            int a = pop(numStack);
            push(numStack, a * b);
        } else if (strcmp(tokens[i], "/") == 0) {
            int b = pop(numStack);
            int a = pop(numStack);
            push(numStack, a / b);
        } else {
            push(numStack, atoi(tokens[i]));
        }
    }
    int result = pop(numStack);
    free(numStack->items);
    free(numStack);
    return result;
}

---

Sliding Window Maximum Using Deque

Given an array nums and a sliding window of size k moving from the left to the right, return an array containing the maximum element in each window position.

A monotonic decreasing deque is used to achieve O(n) time complexity. The deque stores indices of array elements in decreasing order of their values. For each new element, remove from the back of the deque indices of elemants smaller than the current one, then add the current index. The front of the deque always holds the index of the current window's maximum.

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

typedef struct Node {
    int idx;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct {
    Node* head;
    Node* tail;
} Deque;

Deque* createDeque() {
    Deque* dq = (Deque*)malloc(sizeof(Deque));
    dq->head = dq->tail = NULL;
    return dq;
}

void pushBack(Deque* dq, int idx) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->idx = idx;
    newNode->next = NULL;
    newNode->prev = dq->tail;
    if (dq->tail) dq->tail->next = newNode;
    dq->tail = newNode;
    if (!dq->head) dq->head = newNode;
}

void popFront(Deque* dq) {
    if (!dq->head) return;
    Node* temp = dq->head;
    dq->head = dq->head->next;
    if (dq->head) dq->head->prev = NULL;
    else dq->tail = NULL;
    free(temp);
}

void popBack(Deque* dq) {
    if (!dq->tail) return;
    Node* temp = dq->tail;
    dq->tail = dq->tail->prev;
    if (dq->tail) dq->tail->next = NULL;
    else dq->head = NULL;
    free(temp);
}

int* maxSlidingWindow(int* nums, int n, int k, int* returnSize) {
    if (n == 0) {
        *returnSize = 0;
        return NULL;
    }
    int* result = (int*)malloc((n - k + 1) * sizeof(int));
    Deque* dq = createDeque();
    *returnSize = 0;

    for (int i = 0; i < n; i++) {
        while (dq->head && dq->head->idx <= i - k) {
            popFront(dq);
        }
        while (dq->tail && nums[dq->tail->idx] <= nums[i]) {
            popBack(dq);
        }
        pushBack(dq, i);
        if (i >= k - 1) {
            result[(*returnSize)++] = nums[dq->head->idx];
        }
    }
    // Cleanup deque nodes omitted for brevity
    free(dq);
    return result;
}

---

Top K Frequent Elements Using Min-Heap

Given an integer array nums and an integer k, return the k most frequent elements.

First, use a hash map to count frequencies. Then, maintain a min-heap (priority queue) of size k ordered by frequency. Iterate through frequency counts; if the heap size exceeds k, remove the element with the smallest frequency. The heap will contain the top k frequent elements.

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

typedef struct {
    int val;
    int freq;
} Element;

typedef struct {
    Element* arr;
    int size;
} MinHeap;

void swap(Element* a, Element* b) {
    Element temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyDown(Element arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left].freq < arr[smallest].freq) smallest = left;
    if (right < n && arr[right].freq < arr[smallest].freq) smallest = right;
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapifyDown(arr, n, smallest);
    }
}

void pushHeap(MinHeap* heap, Element e) {
    heap->arr[heap->size++] = e;
    for (int i = heap->size / 2 - 1; i >= 0; i--)
        heapifyDown(heap->arr, heap->size, i);
}

Element popHeap(MinHeap* heap) {
    Element root = heap->arr[0];
    heap->arr[0] = heap->arr[--heap->size];
    heapifyDown(heap->arr, heap->size, 0);
    return root;
}

int* topKFrequent(int* nums, int n, int k, int* returnSize) {
    // Frequency counting omitted for brevity. Assume freqMap.
    // Create min-heap of size k.
    MinHeap heap = { .arr = (Element*)malloc(k * sizeof(Element)), .size = 0 };
    // Iterate through frequency map:
    // for each (value, frequency) pair:
    //     if heap.size < k: pushHeap(&heap, (Element){value, frequency})
    //     else if frequency > heap.arr[0].freq:
    //         popHeap(&heap); pushHeap(&heap, (Element){value, frequency})
    // Extract results from heap.
    *returnSize = k;
    int* res = (int*)malloc(k * sizeof(int));
    // Fill res in descending order.
    free(heap.arr);
    return res;
}