Introduction to Stack

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Elements are added and removed from the same end, called the top. Stacks are fundamental in computer science and are used in function calls, expression evaluation, undo operations, and many other applications.

Stack Architecture Overview

Stack Structure ├── Physical Storage │ ├── Array-based (static/dynamic) │ └── Linked List-based (dynamic) ├── Operations │ ├── push() - Add element to top │ ├── pop() - Remove element from top │ ├── peek()/top() - View top element │ ├── isEmpty() - Check if empty │ ├── isFull() - Check if full (array-based) │ └── size() - Get number of elements └── Stack State ├── Empty stack: top = -1 ├── Stack with elements: 0 <= top < capacity └── Full stack: top = capacity - 1

Stack Visualization

 Stack Operations ================ push(10) push(20) push(30) pop() top() +-----+ +-----+ +-----+ +-----+ +-----+ | | | | | 30 | ← top | | | 20 | ← top +-----+ +-----+ +-----+ +-----+ +-----+ | | | 20 | ← top | 20 | | 20 | ← top | 10 | +-----+ → +-----+ → +-----+ → +-----+ → +-----+ | 10 | ← top | 10 | | 10 | | 10 | | | +-----+ +-----+ +-----+ +-----+ +-----+

Array-Based Stack Implementation

1. Static Array Stack

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } Stack; // Initialize stack void initStack(Stack* stack) { stack->top = -1; } // Check if stack is empty bool isEmpty(Stack* stack) { return stack->top == -1; } // Check if stack is full bool isFull(Stack* stack) { return stack->top == MAX_SIZE - 1; } // Push element onto stack bool push(Stack* stack, int value) { if (isFull(stack)) { printf("Stack Overflow! Cannot push %d\n", value); return false; } stack->data[++stack->top] = value; printf("Pushed %d onto stack\n", value); return true; } // Pop element from stack int pop(Stack* stack) { if (isEmpty(stack)) { printf("Stack Underflow! Cannot pop from empty stack\n"); return -1; } int value = stack->data[stack->top--]; printf("Popped %d from stack\n", value); return value; } // Peek at top element int peek(Stack* stack) { if (isEmpty(stack)) { printf("Stack is empty!\n"); return -1; } return stack->data[stack->top]; } // Get stack size int size(Stack* stack) { return stack->top + 1; } // Display stack elements void display(Stack* stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return; } printf("Stack elements (top to bottom): "); for (int i = stack->top; i >= 0; i--) { printf("%d ", stack->data[i]); } printf("\n"); } int main() { Stack stack; initStack(&stack); printf("=== Array-based Stack Demo ===\n\n"); // Push elements push(&stack, 10); push(&stack, 20); push(&stack, 30); push(&stack, 40); push(&stack, 50); printf("\nStack after pushes:\n"); display(&stack); printf("Stack size: %d\n", size(&stack)); printf("Top element: %d\n\n", peek(&stack)); // Pop elements pop(&stack); pop(&stack); printf("\nStack after pops:\n"); display(&stack); printf("Stack size: %d\n", size(&stack)); printf("Top element: %d\n\n", peek(&stack)); // Push more push(&stack, 60); push(&stack, 70); printf("\nFinal stack:\n"); display(&stack); return 0; }

Output:

=== Array-based Stack Demo === Pushed 10 onto stack Pushed 20 onto stack Pushed 30 onto stack Pushed 40 onto stack Pushed 50 onto stack Stack after pushes: Stack elements (top to bottom): 50 40 30 20 10 Stack size: 5 Top element: 50 Popped 50 from stack Popped 40 from stack Stack after pops: Stack elements (top to bottom): 30 20 10 Stack size: 3 Top element: 30 Pushed 60 onto stack Pushed 70 onto stack Final stack: Stack elements (top to bottom): 70 60 30 20 10

2. Dynamic Array Stack (Resizable)

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct { int* data; int top; int capacity; } DynamicStack; // Create stack with initial capacity DynamicStack* createStack(int initialCapacity) { DynamicStack* stack = (DynamicStack*)malloc(sizeof(DynamicStack)); if (!stack) return NULL; stack->data = (int*)malloc(initialCapacity * sizeof(int)); if (!stack->data) { free(stack); return NULL; } stack->top = -1; stack->capacity = initialCapacity; return stack; } // Destroy stack and free memory void destroyStack(DynamicStack* stack) { if (stack) { free(stack->data); free(stack); } } // Check if stack is empty bool isEmpty(DynamicStack* stack) { return stack->top == -1; } // Resize stack (double capacity) bool resize(DynamicStack* stack) { int newCapacity = stack->capacity * 2; int* newData = (int*)realloc(stack->data, newCapacity * sizeof(int)); if (!newData) { printf("Memory allocation failed during resize\n"); return false; } stack->data = newData; stack->capacity = newCapacity; printf("Stack resized to capacity: %d\n", newCapacity); return true; } // Push element onto stack bool push(DynamicStack* stack, int value) { if (stack->top == stack->capacity - 1) { if (!resize(stack)) { printf("Stack Overflow! Cannot push %d\n", value); return false; } } stack->data[++stack->top] = value; printf("Pushed %d onto stack (top=%d, capacity=%d)\n", value, stack->top, stack->capacity); return true; } // Pop element from stack int pop(DynamicStack* stack) { if (isEmpty(stack)) { printf("Stack Underflow! Cannot pop from empty stack\n"); return -1; } int value = stack->data[stack->top--]; printf("Popped %d from stack\n", value); // Shrink if necessary (when size < capacity/4) if (stack->top + 1 < stack->capacity / 4 && stack->capacity > 10) { int newCapacity = stack->capacity / 2; int* newData = (int*)realloc(stack->data, newCapacity * sizeof(int)); if (newData) { stack->data = newData; stack->capacity = newCapacity; printf("Stack shrunk to capacity: %d\n", newCapacity); } } return value; } // Peek at top element int peek(DynamicStack* stack) { if (isEmpty(stack)) { printf("Stack is empty!\n"); return -1; } return stack->data[stack->top]; } // Get stack size int size(DynamicStack* stack) { return stack->top + 1; } // Get stack capacity int capacity(DynamicStack* stack) { return stack->capacity; } // Display stack elements void display(DynamicStack* stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return; } printf("Stack elements (top to bottom): "); for (int i = stack->top; i >= 0; i--) { printf("%d ", stack->data[i]); } printf("\n"); printf("Size: %d, Capacity: %d\n", size(stack), capacity(stack)); } int main() { printf("=== Dynamic Array Stack Demo ===\n\n"); DynamicStack* stack = createStack(5); if (!stack) { printf("Failed to create stack\n"); return 1; } // Push elements (will trigger resize) for (int i = 1; i <= 10; i++) { push(stack, i * 10); display(stack); printf("\n"); } // Pop elements (may trigger shrink) for (int i = 1; i <= 8; i++) { pop(stack); display(stack); printf("\n"); } // Clean up destroyStack(stack); return 0; }

Linked List-Based Stack Implementation

1. Singly Linked List Stack

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // Node structure typedef struct Node { int data; struct Node* next; } Node; // Stack structure typedef struct { Node* top; int size; } LinkedListStack; // Create new node Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); if (!newNode) return NULL; newNode->data = data; newNode->next = NULL; return newNode; } // Initialize stack LinkedListStack* createStack() { LinkedListStack* stack = (LinkedListStack*)malloc(sizeof(LinkedListStack)); if (!stack) return NULL; stack->top = NULL; stack->size = 0; return stack; } // Check if stack is empty bool isEmpty(LinkedListStack* stack) { return stack->top == NULL; } // Push element onto stack void push(LinkedListStack* stack, int value) { Node* newNode = createNode(value); if (!newNode) { printf("Memory allocation failed! Cannot push %d\n", value); return; } newNode->next = stack->top; stack->top = newNode; stack->size++; printf("Pushed %d onto stack\n", value); } // Pop element from stack int pop(LinkedListStack* stack) { if (isEmpty(stack)) { printf("Stack Underflow! Cannot pop from empty stack\n"); return -1; } Node* temp = stack->top; int value = temp->data; stack->top = stack->top->next; free(temp); stack->size--; printf("Popped %d from stack\n", value); return value; } // Peek at top element int peek(LinkedListStack* stack) { if (isEmpty(stack)) { printf("Stack is empty!\n"); return -1; } return stack->top->data; } // Get stack size int size(LinkedListStack* stack) { return stack->size; } // Display stack elements void display(LinkedListStack* stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return; } printf("Stack elements (top to bottom): "); Node* current = stack->top; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); printf("Stack size: %d\n", stack->size); } // Destroy stack and free all memory void destroyStack(LinkedListStack* stack) { Node* current = stack->top; Node* next; while (current != NULL) { next = current->next; free(current); current = next; } free(stack); printf("Stack destroyed\n"); } int main() { printf("=== Linked List Stack Demo ===\n\n"); LinkedListStack* stack = createStack(); // Push elements push(stack, 10); push(stack, 20); push(stack, 30); push(stack, 40); push(stack, 50); printf("\nStack after pushes:\n"); display(stack); printf("Top element: %d\n\n", peek(stack)); // Pop elements pop(stack); pop(stack); printf("\nStack after pops:\n"); display(stack); printf("Top element: %d\n\n", peek(stack)); // Push more push(stack, 60); push(stack, 70); printf("\nFinal stack:\n"); display(stack); // Clean up destroyStack(stack); return 0; }

**2. Generic Stack (void*)**

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> // Node structure for generic stack typedef struct GenericNode { void* data; size_t dataSize; struct GenericNode* next; } GenericNode; // Generic stack structure typedef struct { GenericNode* top; int size; } GenericStack; // Create new node with data copy GenericNode* createGenericNode(const void* data, size_t dataSize) { GenericNode* node = (GenericNode*)malloc(sizeof(GenericNode)); if (!node) return NULL; node->data = malloc(dataSize); if (!node->data) { free(node); return NULL; } memcpy(node->data, data, dataSize); node->dataSize = dataSize; node->next = NULL; return node; } // Initialize generic stack GenericStack* createGenericStack() { GenericStack* stack = (GenericStack*)malloc(sizeof(GenericStack)); if (!stack) return NULL; stack->top = NULL; stack->size = 0; return stack; } // Check if stack is empty bool isGenericEmpty(GenericStack* stack) { return stack->top == NULL; } // Push element onto generic stack void pushGeneric(GenericStack* stack, const void* data, size_t dataSize) { GenericNode* node = createGenericNode(data, dataSize); if (!node) { printf("Memory allocation failed! Cannot push\n"); return; } node->next = stack->top; stack->top = node; stack->size++; } // Pop element from generic stack (caller must free data) void* popGeneric(GenericStack* stack) { if (isGenericEmpty(stack)) { printf("Stack Underflow! Cannot pop from empty stack\n"); return NULL; } GenericNode* temp = stack->top; void* data = temp->data; // Caller must free this stack->top = stack->top->next; free(temp); // Free node but not data stack->size--; return data; } // Peek at top element (returns pointer to data) void* peekGeneric(GenericStack* stack) { if (isGenericEmpty(stack)) { printf("Stack is empty!\n"); return NULL; } return stack->top->data; } // Get stack size int genericSize(GenericStack* stack) { return stack->size; } // Destroy stack and free all data void destroyGenericStack(GenericStack* stack, bool freeData) { GenericNode* current = stack->top; GenericNode* next; while (current != NULL) { next = current->next; if (freeData) { free(current->data); } free(current); current = next; } free(stack); } // Print integer stack (helper function) void printIntStack(GenericStack* stack) { if (isGenericEmpty(stack)) { printf("Stack is empty\n"); return; } printf("Stack elements (top to bottom): "); // We need to traverse without modifying the stack // Create a temporary array to store elements int* temp = malloc(genericSize(stack) * sizeof(int)); int index = 0; // Pop all elements to temp array while (!isGenericEmpty(stack)) { int* val = (int*)popGeneric(stack); temp[index++] = *val; free(val); // Free the popped data } // Print in reverse order for (int i = index - 1; i >= 0; i--) { printf("%d ", temp[i]); } printf("\n"); // Push them back for (int i = index - 1; i >= 0; i--) { pushGeneric(stack, &temp[i], sizeof(int)); } free(temp); } int main() { printf("=== Generic Stack Demo ===\n\n"); GenericStack* stack = createGenericStack(); // Push integers int intVals[] = {10, 20, 30, 40, 50}; for (int i = 0; i < 5; i++) { pushGeneric(stack, &intVals[i], sizeof(int)); printf("Pushed integer: %d\n", intVals[i]); } printf("\nInteger stack:\n"); printIntStack(stack); // Pop and print integers printf("\nPopping integers:\n"); while (!isGenericEmpty(stack)) { int* val = (int*)popGeneric(stack); printf("Popped: %d\n", *val); free(val); } printf("\n--- String Stack ---\n\n"); // Push strings const char* strings[] = {"Hello", "World", "from", "Generic", "Stack"}; for (int i = 0; i < 5; i++) { pushGeneric(stack, strings[i], strlen(strings[i]) + 1); printf("Pushed string: %s\n", strings[i]); } printf("\nString stack (top to bottom):\n"); while (!isGenericEmpty(stack)) { char* str = (char*)popGeneric(stack); printf(" %s\n", str); free(str); } destroyGenericStack(stack, true); return 0; }

Stack Applications

1. Balanced Parentheses Checker

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> // Simple character stack typedef struct { char data[1000]; int top; } CharStack; void initCharStack(CharStack* stack) { stack->top = -1; } bool isCharStackEmpty(CharStack* stack) { return stack->top == -1; } bool isCharStackFull(CharStack* stack) { return stack->top == 999; } void pushChar(CharStack* stack, char c) { if (!isCharStackFull(stack)) { stack->data[++stack->top] = c; } } char popChar(CharStack* stack) { if (!isCharStackEmpty(stack)) { return stack->data[stack->top--]; } return '\0'; } char peekChar(CharStack* stack) { if (!isCharStackEmpty(stack)) { return stack->data[stack->top]; } return '\0'; } // Check if parentheses are balanced bool isBalanced(const char* expression) { CharStack stack; initCharStack(&stack); for (int i = 0; expression[i] != '\0'; i++) { char c = expression[i]; // Push opening brackets if (c == '(' || c == '{' || c == '[') { pushChar(&stack, c); } // Check closing brackets else if (c == ')' || c == '}' || c == ']') { if (isCharStackEmpty(&stack)) { return false; // Closing bracket with no opening } char top = popChar(&stack); if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) { return false; // Mismatched brackets } } } return isCharStackEmpty(&stack); // All brackets should be closed } int main() { printf("=== Balanced Parentheses Checker ===\n\n"); const char* testExpressions[] = { "()", "()[]{}", "({[]})", "((()))", "([)]", "(((", "))", "({[}])", NULL }; for (int i = 0; testExpressions[i] != NULL; i++) { const char* expr = testExpressions[i]; bool balanced = isBalanced(expr); printf("%-15s -> %s\n", expr, balanced ? "Balanced" : "Not Balanced"); } return 0; }

Output:

=== Balanced Parentheses Checker === () -> Balanced ()[]{} -> Balanced ({[]}) -> Balanced ((())) -> Balanced ([)] -> Not Balanced ((( -> Not Balanced )) -> Not Balanced ({[}]) -> Not Balanced

2. Infix to Postfix Conversion

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAX 100 typedef struct { char items[MAX]; int top; } CharStack; void initStack(CharStack* s) { s->top = -1; } void push(CharStack* s, char c) { if (s->top < MAX - 1) { s->items[++(s->top)] = c; } } char pop(CharStack* s) { if (s->top >= 0) { return s->items[(s->top)--]; } return '\0'; } char peek(CharStack* s) { if (s->top >= 0) { return s->items[s->top]; } return '\0'; } int isEmpty(CharStack* s) { return s->top == -1; } int precedence(char op) { switch (op) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; default: return 0; } } int isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'; } void infixToPostfix(const char* infix, char* postfix) { CharStack stack; initStack(&stack); int i, j = 0; for (i = 0; infix[i] != '\0'; i++) { char c = infix[i]; // If operand, add to output if (isalnum(c)) { postfix[j++] = c; } // If '(', push to stack else if (c == '(') { push(&stack, c); } // If ')', pop until '(' else if (c == ')') { while (!isEmpty(&stack) && peek(&stack) != '(') { postfix[j++] = pop(&stack); } pop(&stack); // Remove '(' } // If operator else if (isOperator(c)) { while (!isEmpty(&stack) && precedence(peek(&stack)) >= precedence(c)) { postfix[j++] = pop(&stack); } push(&stack, c); } } // Pop remaining operators while (!isEmpty(&stack)) { postfix[j++] = pop(&stack); } postfix[j] = '\0'; } int evaluatePostfix(const char* postfix) { int stack[MAX]; int top = -1; for (int i = 0; postfix[i] != '\0'; i++) { char c = postfix[i]; if (isdigit(c)) { stack[++top] = c - '0'; } else { int b = stack[top--]; int a = stack[top--]; switch (c) { case '+': stack[++top] = a + b; break; case '-': stack[++top] = a - b; break; case '*': stack[++top] = a * b; break; case '/': stack[++top] = a / b; break; } } } return stack[top]; } int main() { printf("=== Infix to Postfix Converter ===\n\n"); const char* expressions[] = { "a+b*c", "a+b*c-d", "(a+b)*c", "a*(b+c)/d", "a+b*(c^d-e)^(f+g*h)-i", NULL }; for (int i = 0; expressions[i] != NULL; i++) { char postfix[MAX]; infixToPostfix(expressions[i], postfix); printf("%-30s -> %s\n", expressions[i], postfix); } printf("\n=== Postfix Evaluation ===\n\n"); // Evaluate numeric expressions const char* numeric[] = {"23+", "234*+", "23*54*+", "53*2+", NULL}; for (int i = 0; numeric[i] != NULL; i++) { int result = evaluatePostfix(numeric[i]); printf("%-10s = %d\n", numeric[i], result); } return 0; }

3. Stack-Based Calculator

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> #define MAX 100 typedef struct { double items[MAX]; int top; } DoubleStack; void initDoubleStack(DoubleStack* s) { s->top = -1; } void pushDouble(DoubleStack* s, double val) { if (s->top < MAX - 1) { s->items[++(s->top)] = val; } } double popDouble(DoubleStack* s) { if (s->top >= 0) { return s->items[(s->top)--]; } return 0; } double peekDouble(DoubleStack* s) { if (s->top >= 0) { return s->items[s->top]; } return 0; } int isDoubleStackEmpty(DoubleStack* s) { return s->top == -1; } int precedence(char op) { switch (op) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; default: return 0; } } double applyOp(double a, double b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; case '^': return pow(a, b); default: return 0; } } double evaluateExpression(const char* expr) { DoubleStack values; CharStack ops; initDoubleStack(&values); initStack(&ops); for (int i = 0; expr[i] != '\0'; i++) { if (expr[i] == ' ') continue; if (isdigit(expr[i]) || expr[i] == '.') { // Parse number char numStr[20]; int j = 0; while (isdigit(expr[i]) || expr[i] == '.') { numStr[j++] = expr[i++]; } numStr[j] = '\0'; i--; // Adjust for loop increment pushDouble(&values, atof(numStr)); } else if (expr[i] == '(') { push(&ops, expr[i]); } else if (expr[i] == ')') { while (!isEmpty(&ops) && peek(&ops) != '(') { double b = popDouble(&values); double a = popDouble(&values); char op = pop(&ops); pushDouble(&values, applyOp(a, b, op)); } pop(&ops); // Remove '(' } else if (isOperator(expr[i])) { while (!isEmpty(&ops) && precedence(peek(&ops)) >= precedence(expr[i])) { double b = popDouble(&values); double a = popDouble(&values); char op = pop(&ops); pushDouble(&values, applyOp(a, b, op)); } push(&ops, expr[i]); } } // Apply remaining operators while (!isEmpty(&ops)) { double b = popDouble(&values); double a = popDouble(&values); char op = pop(&ops); pushDouble(&values, applyOp(a, b, op)); } return popDouble(&values); } int main() { printf("=== Stack-Based Calculator ===\n"); printf("Enter expressions (or 'quit' to exit)\n\n"); char input[100]; while (1) { printf("> "); fgets(input, sizeof(input), stdin); input[strcspn(input, "\n")] = 0; // Remove newline if (strcmp(input, "quit") == 0 || strcmp(input, "exit") == 0) { break; } if (strlen(input) == 0) continue; try { double result = evaluateExpression(input); printf("= %.6f\n\n", result); } catch (...) { printf("Error: Invalid expression\n\n"); } } printf("Goodbye!\n"); return 0; }

4. Undo/Redo System

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_HISTORY 100 // Operation types typedef enum { OP_INSERT, OP_DELETE, OP_REPLACE } OpType; // Operation structure typedef struct { OpType type; char text[100]; int position; } Operation; // Stack for undo/redo typedef struct { Operation ops[MAX_HISTORY]; int top; } HistoryStack; void initHistory(HistoryStack* stack) { stack->top = -1; } void pushHistory(HistoryStack* stack, Operation op) { if (stack->top < MAX_HISTORY - 1) { stack->ops[++stack->top] = op; } } Operation popHistory(HistoryStack* stack) { Operation empty = {0, "", 0}; if (stack->top >= 0) { return stack->ops[stack->top--]; } return empty; } Operation peekHistory(HistoryStack* stack) { Operation empty = {0, "", 0}; if (stack->top >= 0) { return stack->ops[stack->top]; } return empty; } int isHistoryEmpty(HistoryStack* stack) { return stack->top == -1; } int isHistoryFull(HistoryStack* stack) { return stack->top == MAX_HISTORY - 1; } // Text editor with undo/redo typedef struct { char text[1000]; int length; HistoryStack undoStack; HistoryStack redoStack; } Editor; void initEditor(Editor* editor) { editor->text[0] = '\0'; editor->length = 0; initHistory(&editor->undoStack); initHistory(&editor->redoStack); } void insertText(Editor* editor, const char* text, int position) { if (position < 0 || position > editor->length) { printf("Invalid position\n"); return; } // Create operation for undo Operation op; op.type = OP_INSERT; strcpy(op.text, text); op.position = position; // Perform insert memmove(editor->text + position + strlen(text), editor->text + position, editor->length - position + 1); memcpy(editor->text + position, text, strlen(text)); editor->length += strlen(text); // Push to undo stack pushHistory(&editor->undoStack, op); // Clear redo stack initHistory(&editor->redoStack); printf("Inserted: '%s' at position %d\n", text, position); } void deleteText(Editor* editor, int position, int length) { if (position < 0 || position + length > editor->length) { printf("Invalid position or length\n"); return; } // Save deleted text for undo char deleted[100]; strncpy(deleted, editor->text + position, length); deleted[length] = '\0'; // Create operation for undo Operation op; op.type = OP_DELETE; strcpy(op.text, deleted); op.position = position; // Perform delete memmove(editor->text + position, editor->text + position + length, editor->length - position - length + 1); editor->length -= length; // Push to undo stack pushHistory(&editor->undoStack, op); // Clear redo stack initHistory(&editor->redoStack); printf("Deleted %d chars at position %d: '%s'\n", length, position, deleted); } void undo(Editor* editor) { if (isHistoryEmpty(&editor->undoStack)) { printf("Nothing to undo\n"); return; } Operation op = popHistory(&editor->undoStack); switch (op.type) { case OP_INSERT: // Undo insert by deleting memmove(editor->text + op.position, editor->text + op.position + strlen(op.text), editor->length - op.position - strlen(op.text) + 1); editor->length -= strlen(op.text); break; case OP_DELETE: // Undo delete by inserting memmove(editor->text + op.position + strlen(op.text), editor->text + op.position, editor->length - op.position + 1); memcpy(editor->text + op.position, op.text, strlen(op.text)); editor->length += strlen(op.text); break; default: break; } // Push to redo stack pushHistory(&editor->redoStack, op); printf("Undo performed\n"); } void redo(Editor* editor) { if (isHistoryEmpty(&editor->redoStack)) { printf("Nothing to redo\n"); return; } Operation op = popHistory(&editor->redoStack); switch (op.type) { case OP_INSERT: // Redo insert memmove(editor->text + op.position + strlen(op.text), editor->text + op.position, editor->length - op.position + 1); memcpy(editor->text + op.position, op.text, strlen(op.text)); editor->length += strlen(op.text); break; case OP_DELETE: // Redo delete memmove(editor->text + op.position, editor->text + op.position + strlen(op.text), editor->length - op.position - strlen(op.text) + 1); editor->length -= strlen(op.text); break; default: break; } // Push back to undo stack pushHistory(&editor->undoStack, op); printf("Redo performed\n"); } void displayEditor(Editor* editor) { printf("\n=== Current Text ===\n"); printf("\"%s\"\n", editor->text); printf("Length: %d\n", editor->length); printf("Undo count: %d, Redo count: %d\n", editor->undoStack.top + 1, editor->redoStack.top + 1); printf("====================\n\n"); } int main() { Editor editor; initEditor(&editor); printf("=== Undo/Redo Text Editor ===\n\n"); // Perform some operations insertText(&editor, "Hello", 0); displayEditor(&editor); insertText(&editor, " World", 5); displayEditor(&editor); insertText(&editor, "!!!", 11); displayEditor(&editor); deleteText(&editor, 5, 6); // Delete " World" displayEditor(&editor); undo(&editor); displayEditor(&editor); undo(&editor); displayEditor(&editor); redo(&editor); displayEditor(&editor); redo(&editor); displayEditor(&editor); return 0; }

Stack Implementation Comparison

Feature	Array Stack	Dynamic Array	Linked List
Memory	Fixed size	Dynamic	Dynamic
Access Time	O(1)	O(1)	O(1)
Memory Overhead	Low	Medium	High (per node)
Resizing	N/A	O(n) when full	No resizing
Max Size	Fixed	Limited by memory	Limited by memory
Cache Locality	Excellent	Excellent	Poor
Implementation	Simple	Moderate	Moderate

Best Practices

1. Error Handling

// Always check for stack overflow/underflow bool safePush(Stack* stack, int value) { if (stack->top >= MAX_SIZE - 1) { fprintf(stderr, "Stack overflow\n"); return false; } stack->data[++stack->top] = value; return true; } int safePop(Stack* stack) { if (stack->top < 0) { fprintf(stderr, "Stack underflow\n"); return -1; // Or use error flag } return stack->data[stack->top--]; }

2. Memory Management

// For dynamic stacks, always free memory void destroyStack(DynamicStack* stack) { if (stack) { free(stack->data); free(stack); } } // For linked list stacks void destroyLinkedListStack(LinkedListStack* stack) { Node* current = stack->top; while (current) { Node* temp = current; current = current->next; free(temp); } free(stack); }

3. Thread Safety

#include <pthread.h> typedef struct { int* data; int top; int capacity; pthread_mutex_t mutex; } ThreadSafeStack; void threadSafePush(ThreadSafeStack* stack, int value) { pthread_mutex_lock(&stack->mutex); // Push operation pthread_mutex_unlock(&stack->mutex); }

Common Applications Summary

Application	Description	Stack Usage
Function Calls	Call stack for function returns	Store return addresses
Expression Evaluation	Postfix/infix conversion	Store operators/operands
Syntax Parsing	Balanced parentheses	Track opening brackets
Undo Operations	Text editors, applications	Store operation history
Backtracking	Maze solving, N-Queens	Store path/state
DFS	Graph algorithms	Store vertices to visit
Memory Management	Stack allocation	Local variables
Browser History	Back/forward navigation	Store visited pages

Conclusion

Stacks are fundamental data structures with numerous applications:

Key Operations

push() - Add element to top (O(1))
pop() - Remove element from top (O(1))
peek()/top() - View top element (O(1))
isEmpty() - Check if empty (O(1))

Implementation Choices

Array-based: Fast, memory efficient, fixed size
Dynamic array: Flexible, resizable, occasional O(n) resize
Linked list: Truly dynamic, no size limit, more memory overhead

Best Practices

Always check for overflow/underflow
Free memory in dynamic implementations
Consider thread safety for concurrent access
Choose implementation based on requirements
Document the stack's behavior and limitations

Mastering stack implementation is essential for understanding many algorithms and data structures in computer science.

Complete C Programming Guide + Compilers Collection

1. C srand() Function – Understanding Seed Initialization

https://macronepal.com/understanding-the-c-srand-function
Explains how srand() initializes the pseudo-random number generator in C by setting a seed value. Using the same seed produces the same sequence, while time(NULL) gives different results each run.

2. C rand() Function Mechanics and Limitations

https://macronepal.com/c-rand-function-mechanics-and-limitations
Explains how rand() generates pseudo-random numbers between 0 and RAND_MAX, its deterministic nature, and limitations for security use cases.

3. C log() Function

https://macronepal.com/c-log-function-2
Covers natural logarithm calculation using <math.h> and its applications.

4. Mastering Date and Time in C

https://macronepal.com/mastering-date-and-time-in-c
Explains <time.h> functions like time(), clock(), difftime(), and struct tm.

5. Mastering time_t Type in C

https://macronepal.com/mastering-the-c-time_t-type-for-time-management
Explains time representation as seconds since Unix epoch and conversion functions.

6. C exp() Function

https://macronepal.com/c-exp-function-mechanics-and-implementation
Explains exponential function exp(x) and its scientific applications.

7. C log() Function (Alternate Guide)

https://macronepal.com/c-log-function
Comparison of log() and log10() with usage examples.

8. C log10() Function

https://macronepal.com/mastering-the-log10-function-in-c
Explains base-10 logarithm for engineering and scientific applications.

9. C tan() Function

https://macronepal.com/understanding-the-c-tan-function
Explains tangent function and radian-based calculations.

10. Random Numbers in C (Secure vs Predictable)

https://macronepal.com/mastering-c-random-numbers-for-secure-and-predictable-applications
Explains difference between rand() and secure randomness methods.

11. Free Online C Compiler

https://macronepal.com/free-online-c-code-compiler-2
Browser-based compiler for testing C programs instantly.

C Functions, Arguments, Parameters & Flow

Mastering Functions in C – Complete Guide

https://macronepal.com/c/mastering-functions-in-c-a-complete-guide/
Covers function structure, modular programming, and real-world usage.

Function Arguments in C

https://macronepal.com/c-function-arguments/
Explains how arguments are passed and used in function calls.

Function Parameters in C

https://macronepal.com/c-function-parameters/
Explains defining inputs for functions and matching them with arguments.

Function Declarations in C

https://macronepal.com/c-function-declarations-syntax-rules-and-best-practices/
Covers prototypes, syntax rules, and best practices.

Function Calls in C

https://macronepal.com/understanding-function-calls-in-c-syntax-mechanics-and-best-practices/
Explains execution flow and parameter handling during function calls.

Void Functions in C

https://macronepal.com/understanding-void-functions-in-c-syntax-patterns-and-best-practices/
Explains functions that do not return values.

Return Values in C

https://macronepal.com/c-return-values-mechanics-types-and-best-practices/
Explains different return types and how functions return results.

Pass-by-Value in C

https://macronepal.com/aws/understanding-pass-by-value-in-c-mechanics-implications-and-best-practices/
Explains how copies of variables are passed into functions.

Pass-by-Reference in C

https://macronepal.com/c/understanding-pass-by-reference-in-c-pointers-semantics-and-safe-practices/
Explains using pointers to modify original variables.

C strstr() Function

https://macronepal.com/aws/c-strstr-function/
Explains substring search inside strings in C.

C Preprocessor & Macros

C Structures, Memory, Scope & Linkage

C Scope, Storage Classes & Typedef

Extra Articles

https://macronepal.com/13757-2/
https://macronepal.com/13748-2/
https://macronepal.com/13747-2/
https://macronepal.com/13746-2/
https://macronepal.com/13745-2/
https://macronepal.com/13708-2/
https://macronepal.com/13707-2/
https://macronepal.com/13702-2/

Online Compilers

Introduction to Stack

Stack Architecture Overview

Stack Visualization

Array-Based Stack Implementation

1. Static Array Stack

2. Dynamic Array Stack (Resizable)

Linked List-Based Stack Implementation

1. Singly Linked List Stack

2. Generic Stack (void*)

Stack Applications

1. Balanced Parentheses Checker

2. Infix to Postfix Conversion

3. Stack-Based Calculator

4. Undo/Redo System

Stack Implementation Comparison

Best Practices

1. Error Handling

2. Memory Management

3. Thread Safety

Common Applications Summary

Conclusion

Key Operations

Implementation Choices

Best Practices

Complete C Programming Guide + Compilers Collection

1. C srand() Function – Understanding Seed Initialization

2. C rand() Function Mechanics and Limitations

3. C log() Function

4. Mastering Date and Time in C

5. Mastering time_t Type in C

6. C exp() Function

7. C log() Function (Alternate Guide)

8. C log10() Function

9. C tan() Function

10. Random Numbers in C (Secure vs Predictable)

11. Free Online C Compiler

C Functions, Arguments, Parameters & Flow

Mastering Functions in C – Complete Guide

Function Arguments in C

Function Parameters in C

Function Declarations in C

Function Calls in C

Void Functions in C

Return Values in C

Pass-by-Value in C

Pass-by-Reference in C

C strstr() Function

C Preprocessor & Macros

C Structures, Memory, Scope & Linkage

C Scope, Storage Classes & Typedef

Extra Articles

Online Compilers

Leave a Reply Cancel reply

Macro Nepal Helper

**2. Generic Stack (void*)**