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:
Push: Add an item to the top of the stack.
Pop: Remove the item from the top of the stack.
Peek (or Top): Get the value of the top item without removing it.
IsEmpty: Check whether the stack is empty.
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:
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.
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
typedef struct Stack {
int items[MAX];
int top;
} 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 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 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
The push operation adds elements 10, 20, and 30 to the stack.
The pop operation removes the top element (30) from the stack.
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>
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;
} 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:
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).
No Wasted Space: Memory is allocated as needed, so there’s no need to allocate a fixed-size block of memory upfront.
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:
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.
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.
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:
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.
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.
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.
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.
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.
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:
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:
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
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:
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
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
Initialize an empty stack.
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.
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>
typedef struct Stack {
int* arr;
int top;
int capacity;
} 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;
}
void push(Stack* stack, int value) {
stack->arr[++stack->top] = value;
}
int pop(Stack* stack) {
return stack->arr[stack->top--];
}
int evaluatePostfix(char* exp) {
Stack* stack = createStack(100);
int i;
for (i = 0; exp[i]; i++) {
if (isdigit(exp[i])) {
push(stack, exp[i] - '0');
}
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;
}
}
}
return pop(stack);
}
int main() {
char exp[] = "231*+9-";
printf("Postfix Expression: %s\n", exp);
printf("Result: %d\n", evaluatePostfix(exp));
return 0;
}
Explanation of the Code
Stack Creation: The createStack function initializes a stack with a specified capacity.
Pushing and Popping: The push and pop functions handle pushing and popping elements from the stack.
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.
Result: After processing the entire expression, the final result will be at the top of the stack.
Examples
Expression: "231*+9-"
Expression: "123+*8-"
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>
struct Stack {
int top;
unsigned capacity;
char* array;
};
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;
}
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'; }
int isMatchingPair(char char1, char char2) {
return ((char1 == '(' && char2 == ')') ||
(char1 == '{' && char2 == '}') ||
(char1 == '[' && char2 == ']'));
}
int areParenthesesBalanced(char* expr) {
int i = 0;
struct Stack* stack = createStack(strlen(expr));
while (expr[i]) {
if (expr[i] == '(' || expr[i] == '{' || expr[i] == '[')
push(stack, expr[i]);
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>
struct Stack {
int top;
unsigned capacity;
char* array;
};
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;
}
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'; }
void reverseString(char* str) {
int n = strlen(str);
struct Stack* stack = createStack(n);
for (int i = 0; i < n; i++) push(stack, str[i]);
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>
struct Stack {
int top;
unsigned capacity;
int* array;
};
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;
}
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 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');
} 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);
}
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>
struct Stack {
int top;
unsigned capacity;
int* array;
};
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;
}
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; }
int isOperand(char ch) { return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z'); }
int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
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 (isOperand(exp[i])) exp[++k] = exp[i];
else if (exp[i] == '(') push(stack, exp[i]);
else if (exp[i] == ')') {
while (!isEmpty(stack) && peek(stack) != '(')
exp[++k] = pop(stack);
pop(stack);
}
else {
while (!isEmpty(stack) && precedence(exp[i]) <= precedence(peek(stack)))
exp[++k] = pop(stack);
push(stack, exp[i]);
}
}
while (!isEmpty(stack)) exp[++k] = pop(stack);
exp[++k] = '\0';
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>
struct Stack {
int top;
unsigned capacity;
int* array;
};
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;
}
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; }
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>
struct Stack {
int top;
unsigned capacity;
int* array;
int* minArray;
};
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;
}
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; }
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;
}