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

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

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