Stacks and Queues in C

Stacks can be implemented using either arrays or linked lists. Each approach has its trade-offs in terms of memory usage and flexibility.

Array-Based Stack

// stack_array.h
#ifndef STACK_ARRAY_H
#define STACK_ARRAY_H

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

// Function prototypes
void initStack(Stack *s);
bool isEmpty(Stack *s);
bool isFull(Stack *s);
void push(Stack *s, int value);
int pop(Stack *s);
int peek(Stack *s);
int size(Stack *s);
void printStack(Stack *s);

#endif

// stack_array.c
#include "stack_array.h"

// Initialize stack
void initStack(Stack *s) {
    s->top = -1;  // Empty stack has top = -1
}

// Check if stack is empty
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// Check if stack is full
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// Push element onto stack
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack Overflow! Cannot push %d\n", value);
        return;
    }
    s->items[++s->top] = value;
    printf("Pushed %d onto stack\n", value);
}

// Pop element from stack
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow! Cannot pop from empty stack\n");
        return -1;  // Error value
    }
    return s->items[s->top--];
}

// Peek at top element without removing
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->items[s->top];
}

// Get number of elements
int size(Stack *s) {
    return s->top + 1;
}

// Print all elements
void printStack(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack (top to bottom): ");
    for (int i = s->top; i >= 0; i--) {
        printf("%d ", s->items[i]);
    }
    printf("\n");
}

Linked List-Based Stack

// stack_linked.h
#ifndef STACK_LINKED_H
#define STACK_LINKED_H

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

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

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

// Function prototypes
void initLinkedStack(LinkedStack *s);
bool isEmptyLinked(LinkedStack *s);
void pushLinked(LinkedStack *s, int value);
int popLinked(LinkedStack *s);
int peekLinked(LinkedStack *s);
int sizeLinked(LinkedStack *s);
void freeStack(LinkedStack *s);

#endif

// stack_linked.c
#include "stack_linked.h"

// Initialize stack
void initLinkedStack(LinkedStack *s) {
    s->top = NULL;
    s->count = 0;
}

// Check if stack is empty
bool isEmptyLinked(LinkedStack *s) {
    return s->top == NULL;
}

// Push element - O(1)
void pushLinked(LinkedStack *s, int value) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    
    newNode->data = value;
    newNode->next = s->top;  // Point to current top
    s->top = newNode;        // New node becomes top
    s->count++;
    
    printf("Pushed %d onto stack\n", value);
}

// Pop element - O(1)
int popLinked(LinkedStack *s) {
    if (isEmptyLinked(s)) {
        printf("Stack Underflow!\n");
        return -1;
    }
    
    StackNode *temp = s->top;
    int value = temp->data;
    s->top = s->top->next;
    free(temp);
    s->count--;
    
    return value;
}

// Peek at top - O(1)
int peekLinked(LinkedStack *s) {
    if (isEmptyLinked(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->top->data;
}

// Get size - O(1)
int sizeLinked(LinkedStack *s) {
    return s->count;
}

// Free all memory
void freeStack(LinkedStack *s) {
    while (!isEmptyLinked(s)) {
        popLinked(s);
    }
}

Using the Stack

// main.c - Stack demonstration
#include "stack_array.h"
// Or: #include "stack_linked.h"

int main() {
    // Array-based stack
    Stack stack;
    initStack(&stack);
    
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    
    printStack(&stack);  // Stack (top to bottom): 30 20 10
    
    printf("Top element: %d\n", peek(&stack));  // 30
    printf("Stack size: %d\n", size(&stack));   // 3
    
    printf("Popped: %d\n", pop(&stack));  // 30
    printf("Popped: %d\n", pop(&stack));  // 20
    
    printStack(&stack);  // Stack (top to bottom): 10
    
    return 0;
}

// Use two stacks: main stack and min stack
typedef struct {
    Stack mainStack;
    Stack minStack;  // Stores minimum at each level
} MinStack;

void initMinStack(MinStack *ms) {
    initStack(&ms->mainStack);
    initStack(&ms->minStack);
}

void pushMin(MinStack *ms, int value) {
    push(&ms->mainStack, value);
    
    // Push to minStack if empty or value <= current min
    if (isEmpty(&ms->minStack) || value <= peek(&ms->minStack)) {
        push(&ms->minStack, value);
    }
}

int popMin(MinStack *ms) {
    int value = pop(&ms->mainStack);
    
    // If popped value is the current min, pop from minStack too
    if (value == peek(&ms->minStack)) {
        pop(&ms->minStack);
    }
    
    return value;
}

int getMin(MinStack *ms) {
    return peek(&ms->minStack);  // O(1)!
}

// Example:
// push(5): main=[5], min=[5]
// push(3): main=[5,3], min=[5,3]
// push(7): main=[5,3,7], min=[5,3]  (7 > 3, don't add to min)
// getMin(): returns 3
// pop(): returns 7, main=[5,3], min=[5,3]
// pop(): returns 3, main=[5], min=[5] (3 was min, remove)

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

void initDynamicStack(DynamicStack *s, int initialCapacity) {
    s->items = (int *)malloc(initialCapacity * sizeof(int));
    s->top = -1;
    s->capacity = initialCapacity;
}

void resize(DynamicStack *s) {
    s->capacity *= 2;
    s->items = (int *)realloc(s->items, s->capacity * sizeof(int));
    if (s->items == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    printf("Stack resized to capacity %d\n", s->capacity);
}

void pushDynamic(DynamicStack *s, int value) {
    // Resize if full
    if (s->top == s->capacity - 1) {
        resize(s);
    }
    s->items[++s->top] = value;
}

int popDynamic(DynamicStack *s) {
    if (s->top == -1) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return s->items[s->top--];
}

void freeDynamicStack(DynamicStack *s) {
    free(s->items);
    s->items = NULL;
    s->top = -1;
    s->capacity = 0;
}

A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle. Think of a line at a ticket counter - the first person in line is the first to be served. Elements are added at the rear and removed from the front.

Visual Representation

// Queue visualization (FIFO - First In, First Out)
//
//    enqueue(10)   enqueue(20)   enqueue(30)   dequeue()     dequeue()
//    ----------    ----------    ----------    ----------    ----------
//    front→ 10     front→ 10     front→ 10     front→ 20     front→ 30
//           ↑            20           20             30             ↑
//          rear         ↑            30             ↑             rear
//                      rear          ↑             rear
//                                   rear
//                                               returns 10    returns 20

// Elements enter at rear, exit from front

Queue Operations

Types of Queues

// Trace:
// enqueue(A) → Queue: [A]        front=A, rear=A
// enqueue(B) → Queue: [A, B]     front=A, rear=B
// dequeue()  → Queue: [B]        front=B, rear=B, returns A
// enqueue(C) → Queue: [B, C]     front=B, rear=C
// enqueue(D) → Queue: [B, C, D]  front=B, rear=D
// dequeue()  → Queue: [C, D]     front=C, rear=D, returns B
// dequeue()  → Queue: [D]        front=D, rear=D, returns C

// Output (dequeue returns): A, B, C
// Final queue: [D]

Queues can be implemented using arrays (simple or circular) or linked lists. Circular arrays are preferred for fixed-size queues as they efficiently reuse space.

Circular Array Queue

// queue_circular.h
#ifndef QUEUE_CIRCULAR_H
#define QUEUE_CIRCULAR_H

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
    int count;
} CircularQueue;

void initQueue(CircularQueue *q);
bool isQueueEmpty(CircularQueue *q);
bool isQueueFull(CircularQueue *q);
void enqueue(CircularQueue *q, int value);
int dequeue(CircularQueue *q);
int front(CircularQueue *q);
int queueSize(CircularQueue *q);
void printQueue(CircularQueue *q);

#endif

// queue_circular.c
#include "queue_circular.h"

// Initialize queue
void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = -1;
    q->count = 0;
}

// Check if queue is empty
bool isQueueEmpty(CircularQueue *q) {
    return q->count == 0;
}

// Check if queue is full
bool isQueueFull(CircularQueue *q) {
    return q->count == MAX_SIZE;
}

// Add element at rear - O(1)
void enqueue(CircularQueue *q, int value) {
    if (isQueueFull(q)) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
        return;
    }
    
    // Circular increment: wrap around to 0 if at end
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = value;
    q->count++;
    
    printf("Enqueued %d\n", value);
}

// Remove element from front - O(1)
int dequeue(CircularQueue *q) {
    if (isQueueEmpty(q)) {
        printf("Queue Underflow! Cannot dequeue from empty queue\n");
        return -1;
    }
    
    int value = q->items[q->front];
    // Circular increment
    q->front = (q->front + 1) % MAX_SIZE;
    q->count--;
    
    return value;
}

// Get front element without removing - O(1)
int front(CircularQueue *q) {
    if (isQueueEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->items[q->front];
}

// Get number of elements - O(1)
int queueSize(CircularQueue *q) {
    return q->count;
}

// Print all elements
void printQueue(CircularQueue *q) {
    if (isQueueEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    
    printf("Queue (front to rear): ");
    int i = q->front;
    for (int c = 0; c < q->count; c++) {
        printf("%d ", q->items[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

Linked List Queue

// queue_linked.h
#ifndef QUEUE_LINKED_H
#define QUEUE_LINKED_H

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

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

typedef struct {
    QueueNode *front;
    QueueNode *rear;
    int count;
} LinkedQueue;

void initLinkedQueue(LinkedQueue *q);
bool isLinkedQueueEmpty(LinkedQueue *q);
void enqueueLinked(LinkedQueue *q, int value);
int dequeueLinked(LinkedQueue *q);
int frontLinked(LinkedQueue *q);
int rearLinked(LinkedQueue *q);
void freeQueue(LinkedQueue *q);

#endif

// queue_linked.c
#include "queue_linked.h"

// Initialize queue
void initLinkedQueue(LinkedQueue *q) {
    q->front = NULL;
    q->rear = NULL;
    q->count = 0;
}

// Check if queue is empty
bool isLinkedQueueEmpty(LinkedQueue *q) {
    return q->front == NULL;
}

// Enqueue at rear - O(1)
void enqueueLinked(LinkedQueue *q, int value) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    
    newNode->data = value;
    newNode->next = NULL;
    
    if (isLinkedQueueEmpty(q)) {
        // First element: both front and rear point to it
        q->front = newNode;
        q->rear = newNode;
    } else {
        // Add at rear
        q->rear->next = newNode;
        q->rear = newNode;
    }
    
    q->count++;
    printf("Enqueued %d\n", value);
}

// Dequeue from front - O(1)
int dequeueLinked(LinkedQueue *q) {
    if (isLinkedQueueEmpty(q)) {
        printf("Queue Underflow!\n");
        return -1;
    }
    
    QueueNode *temp = q->front;
    int value = temp->data;
    
    q->front = q->front->next;
    
    // If queue becomes empty, update rear too
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    q->count--;
    
    return value;
}

// Get front element - O(1)
int frontLinked(LinkedQueue *q) {
    if (isLinkedQueueEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->front->data;
}

// Get rear element - O(1)
int rearLinked(LinkedQueue *q) {
    if (isLinkedQueueEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->rear->data;
}

// Free all memory
void freeQueue(LinkedQueue *q) {
    while (!isLinkedQueueEmpty(q)) {
        dequeueLinked(q);
    }
}

Using the Queue

// main.c - Queue demonstration
#include "queue_circular.h"

int main() {
    CircularQueue queue;
    initQueue(&queue);
    
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    
    printQueue(&queue);  // Queue (front to rear): 10 20 30
    
    printf("Front: %d\n", front(&queue));  // 10
    printf("Size: %d\n", queueSize(&queue));  // 3
    
    printf("Dequeued: %d\n", dequeue(&queue));  // 10
    printf("Dequeued: %d\n", dequeue(&queue));  // 20
    
    enqueue(&queue, 40);
    enqueue(&queue, 50);
    
    printQueue(&queue);  // Queue (front to rear): 30 40 50
    
    return 0;
}

// Queue using two stacks
typedef struct {
    Stack stack1;  // For enqueue
    Stack stack2;  // For dequeue
} QueueUsingStacks;

void initQueueStacks(QueueUsingStacks *q) {
    initStack(&q->stack1);
    initStack(&q->stack2);
}

// Enqueue: push to stack1 - O(1)
void enqueueStacks(QueueUsingStacks *q, int value) {
    push(&q->stack1, value);
}

// Dequeue: pop from stack2, if empty transfer from stack1
int dequeueStacks(QueueUsingStacks *q) {
    // If stack2 is empty, transfer all from stack1
    if (isEmpty(&q->stack2)) {
        while (!isEmpty(&q->stack1)) {
            push(&q->stack2, pop(&q->stack1));
        }
    }
    
    if (isEmpty(&q->stack2)) {
        printf("Queue is empty!\n");
        return -1;
    }
    
    return pop(&q->stack2);
}

// Example:
// enqueue(1), enqueue(2), enqueue(3)
// stack1 = [1, 2, 3], stack2 = []
//
// dequeue():
// Transfer: stack1 = [], stack2 = [3, 2, 1]
// pop(stack2) returns 1 (FIFO!)
//
// Time: Amortized O(1) for dequeue

// Deque using circular array
typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
    int count;
} Deque;

void initDeque(Deque *d) {
    d->front = 0;
    d->rear = MAX_SIZE - 1;
    d->count = 0;
}

// Insert at front
void insertFront(Deque *d, int value) {
    if (d->count == MAX_SIZE) {
        printf("Deque Overflow!\n");
        return;
    }
    // Move front backward (with wrap)
    d->front = (d->front - 1 + MAX_SIZE) % MAX_SIZE;
    d->items[d->front] = value;
    d->count++;
}

// Insert at rear
void insertRear(Deque *d, int value) {
    if (d->count == MAX_SIZE) {
        printf("Deque Overflow!\n");
        return;
    }
    // Move rear forward (with wrap)
    d->rear = (d->rear + 1) % MAX_SIZE;
    d->items[d->rear] = value;
    d->count++;
}

// Delete from front
int deleteFront(Deque *d) {
    if (d->count == 0) {
        printf("Deque Underflow!\n");
        return -1;
    }
    int value = d->items[d->front];
    d->front = (d->front + 1) % MAX_SIZE;
    d->count--;
    return value;
}

// Delete from rear
int deleteRear(Deque *d) {
    if (d->count == 0) {
        printf("Deque Underflow!\n");
        return -1;
    }
    int value = d->items[d->rear];
    d->rear = (d->rear - 1 + MAX_SIZE) % MAX_SIZE;
    d->count--;
    return value;
}

Stacks and queues are fundamental to many algorithms and real-world applications. Understanding when to use each is crucial for solving problems efficiently.

Stack Applications

1. Balanced Parentheses Checker

// Check if parentheses/brackets are balanced
#include <string.h>

bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

bool isBalanced(const char *expr) {
    Stack stack;
    initStack(&stack);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        
        // Push opening brackets
        if (ch == '(' || ch == '{' || ch == '[') {
            push(&stack, ch);
        }
        // Check closing brackets
        else if (ch == ')' || ch == '}' || ch == ']') {
            if (isEmpty(&stack)) {
                return false;  // No matching open bracket
            }
            
            char top = pop(&stack);
            if (!isMatchingPair(top, ch)) {
                return false;  // Mismatched pair
            }
        }
    }
    
    return isEmpty(&stack);  // Should be empty if balanced
}

// Examples:
// isBalanced("({[]})") → true
// isBalanced("([)]")   → false
// isBalanced("(()")    → false

2. Infix to Postfix Conversion

// Convert infix expression to postfix (Reverse Polish Notation)
int precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '^': return 3;
        default: return 0;
    }
}

void infixToPostfix(const char *infix, char *postfix) {
    Stack stack;
    initStack(&stack);
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];
        
        // Operand: add to output
        if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
            (ch >= '0' && ch <= '9')) {
            postfix[j++] = ch;
        }
        // Left parenthesis: push to stack
        else if (ch == '(') {
            push(&stack, ch);
        }
        // Right parenthesis: pop until '('
        else if (ch == ')') {
            while (!isEmpty(&stack) && peek(&stack) != '(') {
                postfix[j++] = pop(&stack);
            }
            pop(&stack);  // Remove '('
        }
        // Operator
        else {
            while (!isEmpty(&stack) && 
                   precedence(peek(&stack)) >= precedence(ch)) {
                postfix[j++] = pop(&stack);
            }
            push(&stack, ch);
        }
    }
    
    // Pop remaining operators
    while (!isEmpty(&stack)) {
        postfix[j++] = pop(&stack);
    }
    postfix[j] = '\0';
}

// Example:
// Infix:   "a+b*c"
// Postfix: "abc*+"

3. Undo/Redo Functionality

// Simple text editor with undo/redo using stacks
typedef struct {
    char text[1000];
    Stack undoStack;
    Stack redoStack;
} TextEditor;

void initEditor(TextEditor *editor) {
    editor->text[0] = '\0';
    initStack(&editor->undoStack);
    initStack(&editor->redoStack);
}

void typeChar(TextEditor *editor, char c) {
    // Save current state to undo stack
    int len = strlen(editor->text);
    push(&editor->undoStack, len);
    
    // Add character
    editor->text[len] = c;
    editor->text[len + 1] = '\0';
    
    // Clear redo stack (new action invalidates redo)
    while (!isEmpty(&editor->redoStack)) {
        pop(&editor->redoStack);
    }
}

void undo(TextEditor *editor) {
    if (isEmpty(&editor->undoStack)) {
        printf("Nothing to undo\n");
        return;
    }
    
    int prevLen = pop(&editor->undoStack);
    int currLen = strlen(editor->text);
    
    // Save current state for redo
    push(&editor->redoStack, currLen);
    
    // Restore previous state
    editor->text[prevLen] = '\0';
}

void redo(TextEditor *editor) {
    if (isEmpty(&editor->redoStack)) {
        printf("Nothing to redo\n");
        return;
    }
    
    int len = pop(&editor->redoStack);
    push(&editor->undoStack, strlen(editor->text));
    // ... restore text to length 'len'
}

Queue Applications

1. BFS (Breadth-First Search)

// BFS traversal of a graph
#define MAX_VERTICES 100

typedef struct {
    int adj[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

void BFS(Graph *g, int startVertex) {
    bool visited[MAX_VERTICES] = {false};
    CircularQueue queue;
    initQueue(&queue);
    
    // Start with the initial vertex
    visited[startVertex] = true;
    enqueue(&queue, startVertex);
    
    printf("BFS traversal: ");
    
    while (!isQueueEmpty(&queue)) {
        int current = dequeue(&queue);
        printf("%d ", current);
        
        // Visit all adjacent vertices
        for (int i = 0; i < g->numVertices; i++) {
            if (g->adj[current][i] && !visited[i]) {
                visited[i] = true;
                enqueue(&queue, i);
            }
        }
    }
    printf("\n");
}

// BFS explores level by level
// Used for: shortest path (unweighted), level order traversal

2. Task Scheduling / Print Queue

// Print job scheduler
typedef struct {
    int jobId;
    char document[100];
    int pages;
} PrintJob;

typedef struct {
    PrintJob jobs[50];
    int front, rear, count;
} PrintQueue;

void addPrintJob(PrintQueue *pq, int id, const char *doc, int pages) {
    if (pq->count == 50) {
        printf("Print queue full!\n");
        return;
    }
    
    pq->rear = (pq->rear + 1) % 50;
    pq->jobs[pq->rear].jobId = id;
    strcpy(pq->jobs[pq->rear].document, doc);
    pq->jobs[pq->rear].pages = pages;
    pq->count++;
    
    printf("Job %d added: %s (%d pages)\n", id, doc, pages);
}

void processNextJob(PrintQueue *pq) {
    if (pq->count == 0) {
        printf("No jobs in queue\n");
        return;
    }
    
    PrintJob job = pq->jobs[pq->front];
    printf("Printing: %s (%d pages)...\n", job.document, job.pages);
    
    pq->front = (pq->front + 1) % 50;
    pq->count--;
    
    printf("Job %d completed!\n", job.jobId);
}

3. Producer-Consumer Problem

// Simple producer-consumer buffer (conceptual)
typedef struct {
    int buffer[10];
    int front, rear, count;
    int maxSize;
} BoundedBuffer;

// Producer adds items
void produce(BoundedBuffer *buf, int item) {
    if (buf->count == buf->maxSize) {
        printf("Buffer full! Producer waiting...\n");
        return;  // In real implementation: wait/block
    }
    
    buf->rear = (buf->rear + 1) % buf->maxSize;
    buf->buffer[buf->rear] = item;
    buf->count++;
    printf("Produced: %d\n", item);
}

// Consumer removes items
int consume(BoundedBuffer *buf) {
    if (buf->count == 0) {
        printf("Buffer empty! Consumer waiting...\n");
        return -1;  // In real implementation: wait/block
    }
    
    int item = buf->buffer[buf->front];
    buf->front = (buf->front + 1) % buf->maxSize;
    buf->count--;
    printf("Consumed: %d\n", item);
    return item;
}

Comparison Summary

int evaluatePostfix(const char *postfix) {
    Stack stack;
    initStack(&stack);
    
    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];
        
        // If operand, push to stack
        if (ch >= '0' && ch <= '9') {
            push(&stack, ch - '0');
        }
        // If operator, pop two operands and apply
        else {
            int op2 = pop(&stack);
            int op1 = pop(&stack);
            int result;
            
            switch (ch) {
                case '+': result = op1 + op2; break;
                case '-': result = op1 - op2; break;
                case '*': result = op1 * op2; break;
                case '/': result = op1 / op2; break;
            }
            
            push(&stack, result);
        }
    }
    
    return pop(&stack);
}

// Example:
// "23*5+" = (2*3)+5 = 11
// "234*+" = 2+(3*4) = 14

// Stack using two queues (costly push approach)
typedef struct {
    CircularQueue q1;
    CircularQueue q2;
} StackUsingQueues;

void initStackQueues(StackUsingQueues *s) {
    initQueue(&s->q1);
    initQueue(&s->q2);
}

// Push: Make new element front by transferring
void pushQueues(StackUsingQueues *s, int value) {
    // Add to q2
    enqueue(&s->q2, value);
    
    // Move all from q1 to q2
    while (!isQueueEmpty(&s->q1)) {
        enqueue(&s->q2, dequeue(&s->q1));
    }
    
    // Swap q1 and q2
    CircularQueue temp = s->q1;
    s->q1 = s->q2;
    s->q2 = temp;
}

// Pop: Simply dequeue from q1 - O(1)
int popQueues(StackUsingQueues *s) {
    if (isQueueEmpty(&s->q1)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return dequeue(&s->q1);
}

// Example:
// push(1): q1=[1], q2=[]
// push(2): q2=[2], move q1 to q2: q2=[2,1], swap: q1=[2,1]
// push(3): q2=[3], move q1 to q2: q2=[3,2,1], swap: q1=[3,2,1]
// pop(): returns 3, q1=[2,1] (LIFO!)