In C programming, a stack can be implemented using either an array or a linked list. For the sake of simplicity and popularity, this article will focus on the array-based approach.
Definition of a stack structure in C:
#define MAX_SIZE 100
typedef struct {
int arr[MAX_SIZE];
int top;
} Stack;
Here, a construct named Stack is outlined, comprising an array of integers called arr and an integer top that signifies the current top element. The MAX_SIZE constant specifies the maximum capacity of the stack.
We need to set up a stack by assigning the top variable to -1 to indicate that the stack is empty. The initialization function can be observed below:
void initialize (Stack *stack) {
stack->top = -1;
}
When executing a push operation, a new item is inserted at the top of the stack. This action results in an increment of the top variable, and the new element is placed at the appropriate index position. Let's demonstrate the push operation:
void push (Stack *stack, int element) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow! Cannot push element %d\n", element);
return;
}
stack->arr[++stack->top] = element;
}
In the provided code snippet, we ascertain if the stack is already full (top == MAX_SIZE - 1). If this condition is met, we exit the function without pushing the element and display an error message signaling a stack overflow.
The uppermost item in the stack gets eliminated when performing the pop operation. The top variable is decremented to reflect this elimination. Now, let's proceed with executing the pop action:
int pop (Stack *stack) {
if (stack->top == -1) {
printf("Stack Underflow! Cannot pop element.\n");
return -1; // Return an invalid value to indicate underflow
}
return stack->arr[stack->top--];
}
The provided code snippet verifies if the stack is empty by checking if the top value equals -1. When this condition is met, it signifies an underflow scenario, prompting the return of an inaccurate value (-1) and the display of an error message signaling a stack underflow.
We have the option to examine the uppermost item by utilizing the peek function, which allows us to view it without eliminating it. The following steps illustrate how this can be achieved:
int peek (Stack *stack) {
if (stack->top == -1) {
printf("Stack is empty!\n");
return -1; // Return an invalid value to indicate an empty stack
}
return stack->arr[stack->top];
}
The code snippet above inspects the stack to determine if it is empty (top == -1). When an empty stack is encountered, an error message is displayed, and an invalid value (-1) is returned.
Example:
Let's proceed with creating a simple program to demonstrate the functionality of stack operations. We will push several elements onto the stack, pop one element off, and finally inspect the top element.
#include <stdio.h>
int main () {
Stack stack;
initialize(&stack);
push (&stack, 10);
push (&stack, 20);
push (&stack, 30);
printf("Top element: %d\n", peek(&stack));
printf("Popped element: %d\n", pop(&stack));
printf("Top element after popping: %d\n", peek(&stack));
return 0;
}
Output:
Top element: 30
Popped element: 30
Top element after popping: 20
Here are applications of stack data structure
1. Parentheses Matching:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool parenthesesMatching(char* expression) {
Stack stack;
initialize(&stack);
int length = strlen(expression);
for (int i = 0; i< length; i++) {
if (expression[i] == '(') {
push(&stack, '(');
} else if (expression[i] == ')') {
if (pop(&stack) == -1) {
return false;
}
}
}
return stack.top == -1; // If stack is empty, all parentheses are matched
}
int main() {
char expression[100];
printf("Enter an expression: ");
scanf("%s", expression);
if (parenthesesMatching(expression)) {
printf("Parentheses are balanced.\n");
} else {
printf("Parentheses are not balanced.\n");
}
return 0;
}
Output:
Enter an expression: (a + b) * (c - d)
Parentheses are balanced.
Explanation:
This software utilizes a stack data structure to verify the balance of brackets within an expression. With each iteration, it scans every character in the expression, pushing an opening parenthesis onto the stack. Whenever a closing parenthesis is encountered, an element is popped from the stack. The expression is considered balanced, with all brackets matched, if the stack is empty by the completion of the iteration.
2. Infix to Postfix Conversion:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int precedence(char operator) {
if (operator == '+' || operator == '-')
return 1;
else if (operator == '*' || operator == '/')
return 2;
else if (operator == '^')
return 3;
else
return 0;
}
void infixToPostfix(char* infix, char* postfix) {
Stack stack;
initialize(&stack);
int length = strlen(infix);
int j = 0;
for (int i = 0; i< length; i++) {
char currentChar = infix[i];
if (isalnum(currentChar)) {
postfix[j++] = currentChar;
} else if (currentChar == '(') {
push(&stack, '(');
} else if (currentChar == ')') {
while (peek(&stack) != '(') {
postfix[j++] = pop(&stack);
}
pop(&stack); // Pop the '(' from the stack
} else {
while (precedence(currentChar) <= precedence(peek(&stack))) {
postfix[j++] = pop(&stack);
}
push(&stack, currentChar);
}
}
while (stack.top != -1) {
postfix[j++] = pop(&stack);
}
postfix[j] = '\0'; // Append null character to indicate end of postfix expression
}
int main() {
char infix[100];
printf("Enter an infix expression: ");
scanf("%s", infix);
char postfix[100];
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}
Output:
Enter an infix expression: (a + b) * c - d
Postfix expression: ab+c*d-
Explanation:
By leveraging the stack data structure, this software converts an infix mathematical expression into postfix format. It sequentially processes each character in the infix expression considering the operator precedence and bracket placement. The postfix notation is generated by popping operators from the stack and appending them to the resulting string.
3. Undo/Redo Functionality:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char operation[100];
} Edit;
void performOperation(Stack* undoStack, Stack* redoStack, char* operation) {
Edit edit;
strcpy(edit.operation, operation);
push(undoStack, edit);
// Clear redo stack since a new operation has been performed
while (stack->top != -1) {
pop(redoStack);
}
}
bool undo(Stack* undoStack, Stack* redoStack) {
if (undoStack->top == -1) {
return false;
}
Edit edit = pop(undoStack);
push(redoStack, edit);
printf("Undo operation: %s\n", edit.operation);
return true;
}
bool redo(Stack* undoStack, Stack* redoStack) {
if (redoStack->top == -1) {
return false;
}
Edit edit = pop(redoStack);
push(undoStack, edit);
printf("Redo operation: %s\n", edit.operation);
return true;
}
int main() {
Stack undoStack;
initialize(&undoStack);
Stack redoStack;
initialize(&redoStack);
performOperation(&undoStack, &redoStack, "Insert text");
performOperation(&undoStack, &redoStack, "Delete text");
performOperation(&undoStack, &redoStack, "Replace text");
undo (&undoStack, &redoStack);
redo(&undoStack, &redoStack);
return 0;
}
Output:
Undo operation: Replace text
Redo operation: Replace text
Explanation:
This software employs a pair of stacks to showcase the functionality of undoing and redoing actions. The performOperation function simulates an operation, with the outcome stored in the undo stack. Upon invoking the undo function, an operation is taken off the undo stack and added to the redo stack. Subsequently, the redo function reverses this process by extracting an operation from the redo stack and inserting it back into the undo stack.
Conclusion:
In summary, proficient programming necessitates understanding the stack data structure and its implementation in the C language. The Last-In-First-Out (LIFO) concept enables manipulation of stack elements through actions like push, pop, and peek. This article's array-based approach presents a common and easily understood technique. Ensuring proper stack functionality involves addressing issues such as stack overflow and underflow. Mastering the stack data structure empowers programmers to address diverse programming challenges and enhance code efficiency.