Introduction to Stacks

Stacks are one of the fundamental data structures in computer science, essential for a wide range of algorithms and applications. A stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In, First Out), which means that the last element added to the stack will be the first one to be removed. This characteristic makes stacks particularly useful in scenarios where you need to reverse the order of items or handle nested structures, such as in recursive algorithms.

Basic Operations

A stack typically supports the following core operations:

1. Push: Add an item to the top of the stack.

2. Pop: Remove the item from the top of the stack.

3. Peek (or Top): Get the value of the top item without removing it.

4. IsEmpty: Check whether the stack is empty.

5. IsFull (optional, for fixed-size stacks): Check whether the stack is full.

These operations are designed to have an O(1) time complexity, meaning they can be performed in constant time.

Real-World Analogy

A common analogy to understand how a stack works is to think of a stack of plates. You add plates to the stack one by one, and when you need a plate, you take the one on top. You can't take a plate from the middle or the bottom without first removing the ones on top. This is exactly how a stack operates.

Representation of Stacks

Stacks can be implemented in various ways, but the two most common methods are:

1. Array-Based Implementation: This approach uses an array to store the stack elements. It's simple and efficient but requires a predefined size. If the stack exceeds this size, it either needs to be resized (which can be costly) or throws an overflow error.

2. Linked List-Based Implementation: This method uses a linked list where each node points to the next node in the sequence. This implementation is more flexible in terms of size but may require more memory due to the storage of pointers.

Applications of Stacks

Stacks are used in numerous algorithms and real-world applications:

• Expression Evaluation: Stacks are used to evaluate expressions in postfix (Reverse Polish notation) and convert infix expressions (common arithmetic notation) to postfix or prefix.

• Backtracking: Many algorithms, like solving mazes or puzzles, use stacks to remember paths and backtrack when a dead-end is reached.

• Function Calls: In most programming languages, the call stack is used to manage function calls, local variables, and return addresses.

• Undo Mechanism: Many software applications use stacks to implement the undo feature, where the last operation can be undone first.

Implementing Stacks Using Arrays

Implementing a stack using an array is one of the simplest and most efficient ways to represent a stack. In this guide, we'll walk through the process of creating a stack using an array in the C programming language. We'll cover the core stack operations: push, pop, peek, isEmpty, and isFull.

Step 1: Define the Stack Structure

First, let's define the structure of the stack. We need to store the stack's elements in an array, keep track of the top element, and define the maximum size of the stack.

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

#define MAX 100  // Define the maximum size of the stack

typedef struct Stack {
    int items[MAX];  // Array to store the stack elements
    int top;         // Index of the top element in the stack
} Stack;

Step 2: Initialize the Stack

Next, we'll create a function to initialize the stack. Initially, the stack is empty, so we set top to -1.

void initStack(Stack* stack) {
    stack->top = -1;
}

Step 3: Check if the Stack is Full

Before pushing an element onto the stack, we need to ensure there's enough space. The stack is full when top equals MAX - 1.

int isFull(Stack* stack) {
    return stack->top == MAX - 1;
}

Step 4: Check if the Stack is Empty

Similarly, before popping an element, we should check if the stack is empty. The stack is empty when top equals -1.

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

Step 5: Push an Element onto the Stack

To push an element onto the stack, we first check if the stack is full. If not, we increment top and add the new element at that position.

void push(Stack* stack, int item) {
    if (isFull(stack)) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++(stack->top)] = item;
    printf("%d pushed to stack\n", item);
}

Step 6: Pop an Element from the Stack

To pop an element, we first check if the stack is empty. If it's not, we return the element at the top and decrement the top index.

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1;  // Return an invalid value to indicate underflow
    }
    return stack->items[(stack->top)--];
}

Step 7: Peek at the Top Element of the Stack

The peek operation returns the element at the top of the stack without removing it.

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;  // Return an invalid value to indicate the stack is empty
    }
    return stack->items[stack->top];
}

Step 8: Demonstrate the Stack Operations

Finally, let's create a main function to demonstrate the stack operations.

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("%d popped from stack\n", pop(&stack));
    printf("Top element is %d\n", peek(&stack));

    return 0;
}

Step 9: Compile and Run the Program

To compile and run the program, you can use the following commands in your terminal or command prompt:

gcc -o stack stack.c
./stack

Expected Output

When you run the program, you should see the following output:

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20

Explanation

1. The push operation adds elements 10, 20, and 30 to the stack.

2. The pop operation removes the top element (30) from the stack.

3. The peek operation returns the current top element (20) without removing it.

Implementing Stacks Using Linked Lists

A stack can also be implemented using a linked list, which offers greater flexibility than an array-based implementation. Unlike an array, a linked list does not require a predetermined size, making it a dynamic structure that can grow or shrink as needed. In this guide, we'll walk through implementing a stack using a linked list in C, followed by a comparison of the pros and cons relative to an array-based stack.

Step 1: Define the Node Structure

In a linked list, each element (node) contains the data and a pointer to the next node. For a stack, we need to define a node structure that holds an integer value and a pointer to the next node.

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

// Define the structure of a node in the linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

Step 2: Define the Stack Structure

For the stack, we only need a pointer to the top node of the linked list.

typedef struct Stack {
    Node* top;  // Pointer to the top node
} Stack;

Step 3: Initialize the Stack

We'll create a function to initialize the stack. Initially, the stack is empty, so the top pointer is set to NULL.

void initStack(Stack* stack) {
    stack->top = NULL;
}

Step 4: Check if the Stack is Empty

Before performing operations like pop or peek, we should check if the stack is empty. The stack is empty when top is NULL.

int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

Step 5: Push an Element onto the Stack

To push an element onto the stack, we need to create a new node, set its data field, and point its next field to the current top node. Then, we update the top pointer to point to this new node.

void push(Stack* stack, int item) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Stack Overflow\n");
        return;
    }
    newNode->data = item;
    newNode->next = stack->top;
    stack->top = newNode;
    printf("%d pushed to stack\n", item);
}

Step 6: Pop an Element from the Stack

To pop an element from the stack, we first check if the stack is empty. If it's not, we store the current top node's data, update the top pointer to point to the next node, free the old top node, and return the stored data.

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1;
    }
    Node* temp = stack->top;
    int poppedData = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return poppedData;
}

Step 7: Peek at the Top Element of the Stack

The peek operation returns the element at the top of the stack without removing it.

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->top->data;
}

Step 8: Demonstrate the Stack Operations

Let's create a main function to demonstrate the stack operations.

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("%d popped from stack\n", pop(&stack));
    printf("Top element is %d\n", peek(&stack));

    return 0;
}

Step 9: Compile and Run the Program

To compile and run the program, you can use the following commands in your terminal or command prompt:

gcc -o stack stack.c
./stack

Expected Output

When you run the program, you should see the following output:

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20

Pros and Cons of Linked List-Based Stacks

Pros:

1. Dynamic Size: Unlike array-based stacks, linked list-based stacks can grow or shrink dynamically, so there's no need to worry about stack overflow (as long as there is memory available).

2. No Wasted Space: Memory is allocated as needed, so there’s no need to allocate a fixed-size block of memory upfront.

3. No Resizing Needed: There’s no need to resize the stack, as would be necessary with an array when the number of elements exceeds its capacity.

Cons:

1. Memory Overhead: Each node requires additional memory for the pointer to the next node, which can lead to higher memory usage compared to array-based stacks, especially for small data elements.

2. Slower Access: Linked list elements are not stored in contiguous memory locations, leading to potentially slower access times compared to arrays due to cache misses.

3. Complexity: Linked list-based implementations are generally more complex to implement and manage due to the need for dynamic memory allocation and deallocation.

Stack ADT: Interface and Descriptions

A Stack Abstract Data Type (ADT) defines a stack as a collection of elements with specific operations, regardless of the underlying implementation (array-based, linked list-based, etc.). The Stack ADT provides a clear and consistent way to interact with the stack, ensuring that users of the stack can perform the necessary operations without needing to know the details of how the stack is implemented.

Following is the typical interface of a Stack ADT and what each function provides:

1. push(item)

   • Description: Adds an item to the top of the stack.

   • Purpose: This operation increases the size of the stack by one. The newly added element becomes the top element of the stack.

   • Preconditions: The stack must not be full (if there's a maximum capacity).

   • Postconditions: The stack contains the new item at the top.

2. pop()

   • Description: Removes and returns the item at the top of the stack.

   • Purpose: This operation decreases the size of the stack by one. It provides access to the most recently added item and removes it from the stack.

   • Preconditions: The stack must not be empty.

   • Postconditions: The stack no longer contains the item that was at the top, and the new top is the element that was below the removed item.

3. peek() (or top())

   • Description: Returns the item at the top of the stack without removing it.

   • Purpose: Allows the user to view the top element of the stack without altering the stack’s state.

   • Preconditions: The stack must not be empty.

   • Postconditions: The stack remains unchanged.

4. isEmpty()

   • Description: Returns true if the stack is empty, false otherwise.

   • Purpose: This operation checks if the stack contains any elements.

   • Preconditions: None.

   • Postconditions: None, the stack remains unchanged.

5. isFull() (optional, for fixed-size stacks):

   • Description: Returns true if the stack is full, false otherwise.

   • Purpose: This operation checks if the stack has reached its maximum capacity, preventing further push operations if true.

   • Preconditions: The stack has a maximum size.

   • Postconditions: None, the stack remains unchanged.

6. size() (optional):

   • Description: Returns the number of elements currently in the stack.

   • Purpose: This operation allows the user to query how many items are currently stored in the stack.

   • Preconditions: None.

   • Postconditions: None, the stack remains unchanged.

Arithmetic Expressions: Infix, Prefix, and Postfix Notations

Arithmetic expressions can be represented in three different notations: Infix, Prefix, and Postfix. Understanding how to convert between these notations is essential for working with expression evaluation algorithms, especially in the context of compilers and interpreters.

1. Infix Notation

Infix notation is the most common way of writing expressions, where operators are placed between operands.

Example:

• Infix: A + B

2. Prefix Notation (Polish Notation)

In prefix notation, also known as Polish notation, the operator precedes its operands. This notation eliminates the need for parentheses to indicate operator precedence, as the order of operations is dictated by the position of the operators.

Example:

• Infix: A + B

• Prefix: + A B

3. Postfix Notation (Reverse Polish Notation)

In postfix notation, also known as Reverse Polish Notation (RPN), the operator follows its operands. Like prefix notation, postfix notation does not require parentheses to enforce operator precedence.

Example:

• Infix: A + B

• Postfix: A B +

Example 1: Infix to Prefix and Postfix

Infix Expression:
(A + B) * (C - D)

Step-by-Step Conversion:

1. Infix to Prefix:

   • Start by identifying the operator with the lowest precedence that is outside parentheses. In this case, the multiplication operator * is the main operator.

   • The expression can be split into two sub-expressions: (A + B) and (C - D).

   • Convert these sub-expressions:

     • (A + B) becomes + A B

     • (C - D) becomes - C D

   • Finally, place the * operator before these sub-expressions.

   • Prefix: * + A B - C D

2. Infix to Postfix:

   • Start from the innermost expressions and move outward.

   • Convert (A + B) to A B +

   • Convert (C - D) to C D -

   • Finally, place the multiplication operator after these results.

   • Postfix: A B + C D - *

Summary for Example 1:

• Infix: (A + B) * (C - D)

• Prefix: * + A B - C D

• Postfix: A B + C D - *

Example 2: Infix to Prefix and Postfix

Infix Expression:
A * (B + C) / D - E

Step-by-Step Conversion:

1. Infix to Prefix:

   • Identify the main operator with the lowest precedence. Here, the subtraction - is the main operator.

   • The expression is split into two parts: A * (B + C) / D and E.

   • Convert A * (B + C) / D:

     • * takes precedence over /, so it becomes * A + B C

     • This then combines with / D to become / * A + B C D

   • Place the - operator before these results.

   • Prefix: - / * A + B C D E

2. Infix to Postfix:

   • Begin with the innermost expressions and convert them.

   • Convert (B + C) to B C +

   • Combine with A * (B + C) to get A B C + *

   • Combine with / D to get A B C + * D /

   • Finally, subtract E:

   • Postfix: A B C + * D / E -

Summary for Example 2:

• Infix: A * (B + C) / D - E

• Prefix: - / * A + B C D E

• Postfix: A B C + * D / E -

Evaluating Arithmetic Expressions Using Stacks

Evaluating arithmetic expressions is one of the classic applications of stacks in computer science. Let's focus on evaluating postfix expressions using stacks. This approach is straightforward because postfix expressions eliminate the need for parentheses, and the order of operations is implicitly handled by the position of the operators.

Steps to Evaluate a Postfix Expression

1. Initialize an empty stack.

2. Scan the postfix expression from left to right.

   • If the token is an operand (number), push it onto the stack.

   • If the token is an operator, pop the top two elements from the stack, apply the operator, and push the result back onto the stack.

3. At the end of the expression, the stack will contain the final result.

Example

For the postfix expression 2 3 1 * + 9 -:

• Push 2 (stack: 2)

• Push 3 (stack: 2, 3)

• Push 1 (stack: 2, 3, 1)

• Encounter *: Pop 1 and 3, compute 3 * 1 = 3, push 3 (stack: 2, 3)

• Encounter +: Pop 3 and 2, compute 2 + 3 = 5, push 5 (stack: 5)

• Push 9 (stack: 5, 9)

• Encounter -: Pop 9 and 5, compute 5 - 9 = -4, push -4 (stack: -4)

Final result is -4.

Below is a C program that evaluates a postfix expression:

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

// Define a stack structure
typedef struct Stack {
    int* arr;
    int top;
    int capacity;
} Stack;

// Function to create a stack
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->arr = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

// Function to push an element onto the stack
void push(Stack* stack, int value) {
    stack->arr[++stack->top] = value;
}

// Function to pop an element from the stack
int pop(Stack* stack) {
    return stack->arr[stack->top--];
}

// Function to evaluate a postfix expression
int evaluatePostfix(char* exp) {
    Stack* stack = createStack(100); // Assuming expression won't be longer than 100 characters
    int i;

    for (i = 0; exp[i]; i++) {
        // If the character is a digit, push it onto the stack
        if (isdigit(exp[i])) {
            push(stack, exp[i] - '0');
        }
        // If the character is an operator, pop two elements from the stack, apply the operator, and push the result back
        else {
            int val1 = pop(stack);
            int val2 = pop(stack);
            switch (exp[i]) {
                case '+': push(stack, val2 + val1); break;
                case '-': push(stack, val2 - val1); break;
                case '*': push(stack, val2 * val1); break;
                case '/': push(stack, val2 / val1); break;
            }
        }
    }
    // The result of the expression is the last remaining element in the stack
    return pop(stack);
}

// Main function to test the evaluation
int main() {
    char exp[] = "231*+9-";
    printf("Postfix Expression: %s\n", exp);
    printf("Result: %d\n", evaluatePostfix(exp));
    return 0;
}

Explanation of the Code

1. Stack Creation: The createStack function initializes a stack with a specified capacity.

2. Pushing and Popping: The push and pop functions handle pushing and popping elements from the stack.

3. Evaluating Postfix Expression: The evaluatePostfix function iterates through each character of the postfix expression. If it encounters a digit, it pushes it onto the stack. If it encounters an operator, it pops the top two elements, applies the operator, and pushes the result back onto the stack.

4. Result: After processing the entire expression, the final result will be at the top of the stack.

Examples

1. Expression: "231*+9-"

   • Postfix Evaluation Steps:

     • Stack after pushing 2: 2

     • Stack after pushing 3: 2, 3

     • Stack after pushing 1: 2, 3, 1

     • After *: 2, 3

     • After +: 5

     • Stack after pushing 9: 5, 9

     • After -: -4

   • Result: -4

2. Expression: "123+*8-"

   • Postfix Evaluation Steps:

     • Stack after pushing 1: 1

     • Stack after pushing 2: 1, 2

     • Stack after pushing 3: 1, 2, 3

     • After +: 1, 5

     • After *: 5

     • Stack after pushing 8: 5, 8

     • After -: -3

   • Result: -3

Problems:

• Check for Balanced Parentheses: Write a C program using a stack to check whether an input string of parentheses (including {}, [], and ()) is balanced. The program should return true if the parentheses are balanced, and false otherwise.

• Reverse a String Using a Stack: Implement a C function that uses a stack to reverse a given string. The program should take the string as input and print the reversed string as output.

• Evaluate a Postfix Expression: Write a C program to evaluate a given postfix expression using a stack. The program should support basic arithmetic operators (+, -, *, /).

• Convert Infix Expression to Postfix: Develop a C program to convert an infix expression to its postfix form using a stack. The program should handle operators with different precedence and associativity.

• Find the Next Greater Element Using a Stack: Write a C program to find the next greater element for each element in an array using a stack. The program should output the next greater element or -1 if there is none.

• Design a Special Stack that Supports getMin() in O(1) Time: Develop a C program to design a stack that, in addition to push and pop, supports a function getMin() that returns the minimum element in the stack in O(1) time. The program should not use any auxiliary data structures.

Solutions:

1. Check for Balanced Parentheses

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

// Structure for stack
struct Stack {
    int top;
    unsigned capacity;
    char* array;
};

// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (char*)malloc(stack->capacity * sizeof(char));
    return stack;
}

// Stack utility functions
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, char item) { if (!isFull(stack)) stack->array[++stack->top] = item; }
char pop(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top--]; return '\0'; }
char peek(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top]; return '\0'; }

// Function to check if the input character is a matching pair
int isMatchingPair(char char1, char char2) {
    return ((char1 == '(' && char2 == ')') ||
            (char1 == '{' && char2 == '}') ||
            (char1 == '[' && char2 == ']'));
}

// Function to check if the parentheses are balanced
int areParenthesesBalanced(char* expr) {
    int i = 0;
    struct Stack* stack = createStack(strlen(expr));

    while (expr[i]) {
        // Push opening brackets to stack
        if (expr[i] == '(' || expr[i] == '{' || expr[i] == '[')
            push(stack, expr[i]);

        // For closing brackets, check if top of stack matches
        if (expr[i] == ')' || expr[i] == '}' || expr[i] == ']') {
            if (isEmpty(stack) || !isMatchingPair(pop(stack), expr[i]))
                return 0;
        }
        i++;
    }

    return isEmpty(stack);
}

int main() {
    char expr[] = "{()}[]";

    if (areParenthesesBalanced(expr))
        printf("Balanced\n");
    else
        printf("Not Balanced\n");

    return 0;
}

2. Reverse a String Using a Stack

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

// Structure for stack
struct Stack {
    int top;
    unsigned capacity;
    char* array;
};

// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (char*)malloc(stack->capacity * sizeof(char));
    return stack;
}

// Stack utility functions
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, char item) { if (!isFull(stack)) stack->array[++stack->top] = item; }
char pop(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top--]; return '\0'; }

// Function to reverse a string using a stack
void reverseString(char* str) {
    int n = strlen(str);
    struct Stack* stack = createStack(n);

    // Push all characters of the string to the stack
    for (int i = 0; i < n; i++) push(stack, str[i]);

    // Pop characters from stack and put them back into the string
    for (int i = 0; i < n; i++) str[i] = pop(stack);
}

int main() {
    char str[] = "HelloWorld";

    printf("Original String: %s\n", str);

    reverseString(str);

    printf("Reversed String: %s\n", str);

    return 0;
}

3. Evaluate a Postfix Expression

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

// Structure for stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

// Stack utility functions
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, int item) { if (!isFull(stack)) stack->array[++stack->top] = item; }
int pop(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top--]; return -1; }

// Function to evaluate a postfix expression
int evaluatePostfix(char* expr) {
    struct Stack* stack = createStack(strlen(expr));

    for (int i = 0; expr[i]; i++) {
        if (isdigit(expr[i])) {
            push(stack, expr[i] - '0'); // Push operand to stack
        } else {
            int val1 = pop(stack);
            int val2 = pop(stack);
            switch (expr[i]) {
                case '+': push(stack, val2 + val1); break;
                case '-': push(stack, val2 - val1); break;
                case '*': push(stack, val2 * val1); break;
                case '/': push(stack, val2 / val1); break;
            }
        }
    }
    return pop(stack); // The final result is on top of the stack
}

int main() {
    char expr[] = "231*+9-";
    printf("Postfix Expression: %s\n", expr);
    printf("Evaluated Result: %d\n", evaluatePostfix(expr));
    return 0;
}

4. Convert Infix Expression to Postfix

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

// Structure for stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

// Stack utility functions
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, char op) { if (!isFull(stack)) stack->array[++stack->top] = op; }
char pop(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top--]; return -1; }
char peek(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top]; return -1; }

// Function to check if character is an operand
int isOperand(char ch) { return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z'); }

// Function to get the precedence of operators
int precedence(char ch) {
    switch (ch) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
    }
    return -1;
}

// Function to convert infix expression to postfix
int infixToPostfix(char* exp) {
    int i, k;
    struct Stack* stack = createStack(strlen(exp));
    if (!stack) return -1;

    for (i = 0, k = -1; exp[i]; ++i) {
        // If the character is an operand, add it to output
        if (isOperand(exp[i])) exp[++k] = exp[i];

        // If the character is '(', push it to stack
        else if (exp[i] == '(') push(stack, exp[i]);

        // If the character is ')', pop and output from the stack until '(' is found
        else if (exp[i] == ')') {
            while (!isEmpty(stack) && peek(stack) != '(')
                exp[++k] = pop(stack);
            pop(stack); // Discard '('
        }

        // If an operator is encountered
        else {
            while (!isEmpty(stack) && precedence(exp[i]) <= precedence(peek(stack)))
                exp[++k] = pop(stack);
            push(stack, exp[i]);
        }
    }

    // Pop all the operators from the stack
    while (!isEmpty(stack)) exp[++k] = pop(stack);

    exp[++k] = '\0'; // Null-terminate the postfix expression
    return k;
}

int main() {
    char exp[] = "A+B*(C^D-E)";

    printf("Infix Expression: %s\n", exp);
    infixToPostfix(exp);
    printf("Post

fix Expression: %s\n", exp);

    return 0;
}

5. Find the Next Greater Element Using a Stack

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

// Structure for stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

// Stack utility functions
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, int item) { if (!isFull(stack)) stack->array[++stack->top] = item; }
int pop(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top--]; return -1; }
int peek(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top]; return -1; }

// Function to print the next greater element for each element in the array
void printNGE(int arr[], int n) {
    int i = 0;
    struct Stack* stack = createStack(n);

    push(stack, arr[0]);

    for (i = 1; i < n; i++) {
        if (isEmpty(stack)) {
            push(stack, arr[i]);
            continue;
        }

        while (!isEmpty(stack) && peek(stack) < arr[i]) {
            printf("%d -> %d\n", pop(stack), arr[i]);
        }

        push(stack, arr[i]);
    }

    while (!isEmpty(stack)) {
        printf("%d -> %d\n", pop(stack), -1);
    }
}

int main() {
    int arr[] = {11, 13, 21, 3};
    int n = sizeof(arr)/sizeof(arr[0]);

    printNGE(arr, n);

    return 0;
}

6. Design a Special Stack that Supports getMin() in O(1) Time

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

// Structure for the special stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
    int* minArray; // Additional array to keep track of minimum elements
};

// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    stack->minArray = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

// Stack utility functions
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, int item) {
    if (!isFull(stack)) {
        stack->array[++stack->top] = item;
        if (stack->top == 0)
            stack->minArray[stack->top] = item;
        else
            stack->minArray[stack->top] = (item < stack->minArray[stack->top - 1]) ? item : stack->minArray[stack->top - 1];
    }
}
int pop(struct Stack* stack) { if (!isEmpty(stack)) return stack->array[stack->top--]; return INT_MAX; }
int getMin(struct Stack* stack) { if (!isEmpty(stack)) return stack->minArray[stack->top]; return INT_MAX; }

// Function to return the minimum element in O(1) time
int getMinimum(struct Stack* stack) {
    return getMin(stack);
}

int main() {
    struct Stack* stack = createStack(100);

    push(stack, 10);
    push(stack, 20);
    printf("Minimum element is %d\n", getMinimum(stack));

    push(stack, 5);
    printf("Minimum element is %d\n", getMinimum(stack));

    pop(stack);
    printf("Minimum element is %d\n", getMinimum(stack));

    return 0;
}