Table of Contents
Introduction to Stacks in C
A stack is a fundamental data structure in computer science that follows the Last-In-First-Out (LIFO) principle. In C, a stack can be implemented using either an array or a linked list. It is primarily used for managing function calls, expression evaluation, and undo/redo operations.
To understand the concept of a stack, let's consider an example of stacking plates. When you add a plate to the stack, it goes on top of the existing plates, and when you remove a plate, you take it from the top. Similarly, in C, a stack is an abstract data type that allows you to push (add) and pop (remove) elements only at one end, called the top of the stack.
Related Article: Combining Match and Range Queries in Elasticsearch
Stack Program in C: Implementation and Operations
To implement a stack in C, you can use an array or a linked list. Let's start with implementing a stack using an array. Here's a basic implementation of a stack structure in C:
#define MAX_SIZE 100
typedef struct {
int arr[MAX_SIZE];
int top;
} Stack;
void initialize(Stack* stack) {
stack->top = -1;
}
int isEmpty(Stack* stack) {
return stack->top == -1;
}
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
void push(Stack* stack, int data) {
if (isFull(stack)) {
printf("Stack overflow\n");
return;
}
stack->arr[++stack->top] = data;
}
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return -1;
}
return stack->arr[stack->top--];
}
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->arr[stack->top];
}
In this implementation, we define a stack structure with an array to hold the elements and a top variable to keep track of the top position. The initialize function initializes the stack, isEmpty checks if the stack is empty, isFull checks if the stack is full, push adds an element to the top of the stack, pop removes and returns the top element, and peek returns the top element without removing it.
Complexity of Using Stacks in C
The complexity of stack operations in C depends on the underlying data structure used for implementation. When implemented using an array, the time complexity of push and pop operations is O(1) since accessing elements in an array has constant time complexity. However, if the stack is implemented using a linked list, the time complexity of push and pop operations is still O(1) since inserting and deleting nodes at the head of a linked list also has constant time complexity.
The space complexity of a stack is determined by the number of elements it contains. In both array-based and linked list-based implementations, the space complexity is O(n), where n is the number of elements in the stack.
Error Handling in Stack Programs
Error handling is an important aspect of programming, including stack programs. One common error in stack programs is stack overflow, which occurs when trying to push an element onto a full stack. Another error is stack underflow, which happens when trying to pop an element from an empty stack.
To handle these errors, we added error messages to the push and pop functions in the previous stack implementation. When a stack overflow or underflow occurs, an error message is printed, and the function returns an appropriate value (-1 in this case) to indicate the error.
Related Article: The very best software testing tools
Code Snippet Ideas: Stack Operations in C
Here are a few code snippets that demonstrate various stack operations in C:
1. Pushing elements onto a stack:
Stack stack; initialize(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30);
2. Popping elements from a stack:
int item1 = pop(&stack); // Pops and returns 30 int item2 = pop(&stack); // Pops and returns 20
Code Snippet Ideas: Advanced Stack Techniques
Stacks can be used for more advanced techniques and algorithms. Here are a few code snippets that demonstrate advanced stack techniques in C:
1. Checking balanced parentheses using a stack:
int checkBalancedParentheses(const char* expression) {
Stack stack;
initialize(&stack);
for (int i = 0; expression[i] != '\0'; i++) {
if (expression[i] == '(') {
push(&stack, '(');
} else if (expression[i] == ')') {
if (isEmpty(&stack)) {
return 0; // Unbalanced parentheses
}
pop(&stack);
}
}
return isEmpty(&stack); // Returns 1 if parentheses are balanced, 0 otherwise
}
2. Evaluating postfix expressions using a stack:
int evaluatePostfixExpression(const char* postfix) {
Stack stack;
initialize(&stack);
for (int i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
int operand = postfix[i] - '0';
push(&stack, operand);
} else {
int operand2 = pop(&stack);
int operand1 = pop(&stack);
int result;
switch (postfix[i]) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
push(&stack, result);
}
}
return pop(&stack);
}
Code Snippet Ideas: Real World Examples of Stack Usage in C
Stacks have numerous real-world applications in C. Here are a few code snippets that demonstrate the usage of stacks in practical scenarios:
1. Undo/redo functionality in a text editor:
Stack undoStack;
Stack redoStack;
initialize(&undoStack);
initialize(&redoStack);
void performEditAction(const char* action) {
// Perform the edit action
// ...
// Push the action onto the undo stack
push(&undoStack, action);
// Clear the redo stack
while (!isEmpty(&redoStack)) {
pop(&redoStack);
}
}
void undo() {
if (!isEmpty(&undoStack)) {
const char* action = pop(&undoStack);
// Undo the action
// ...
// Push the action onto the redo stack
push(&redoStack, action);
}
}
void redo() {
if (!isEmpty(&redoStack)) {
const char* action = pop(&redoStack);
// Redo the action
// ...
// Push the action onto the undo stack
push(&undoStack, action);
}
}
2. Backtracking in maze solving algorithms:
typedef struct {
int row;
int col;
} Position;
int solveMaze(char maze[][MAX_SIZE], int numRows, int numCols) {
Stack stack;
initialize(&stack);
Position start = {0, 0};
push(&stack, start);
while (!isEmpty(&stack)) {
Position current = pop(&stack);
int row = current.row;
int col = current.col;
if (row == numRows - 1 && col == numCols - 1) {
return 1; // Maze solved
}
if (maze[row][col] == ' ') {
maze[row][col] = '.'; // Mark current position as visited
// Push neighboring positions onto the stack
if (row > 0 && maze[row - 1][col] != '#') {
Position neighbor = {row - 1, col};
push(&stack, neighbor);
}
if (row < numRows - 1 && maze[row + 1][col] != '#') {
Position neighbor = {row + 1, col};
push(&stack, neighbor);
}
if (col > 0 && maze[row][col - 1] != '#') {
Position neighbor = {row, col - 1};
push(&stack, neighbor);
}
if (col < numCols - 1 && maze[row][col + 1] != '#') {
Position neighbor = {row, col + 1};
push(&stack, neighbor);
}
}
}
return 0; // Maze unsolvable
}
Code Snippet Ideas: Best Practices for Working with Stacks in C
When working with stacks in C, there are some best practices to consider. Here are a few code snippets that demonstrate these best practices:
1. Use a macro to define the maximum size of the stack:
#define MAX_SIZE 100
2. Encapsulate the stack implementation in a separate module:
// stack.h
typedef struct {
int arr[MAX_SIZE];
int top;
} Stack;
void initialize(Stack* stack);
int isEmpty(Stack* stack);
int isFull(Stack* stack);
void push(Stack* stack, int data);
int pop(Stack* stack);
int peek(Stack* stack);
// stack.c
#include "stack.h"
void initialize(Stack* stack) {
stack->top = -1;
}
int isEmpty(Stack* stack) {
return stack->top == -1;
}
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
void push(Stack* stack, int data) {
if (isFull(stack)) {
printf("Stack overflow\n");
return;
}
stack->arr[++stack->top] = data;
}
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return -1;
}
return stack->arr[stack->top--];
}
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->arr[stack->top];
}
Related Article: Altering Response Fields in an Elasticsearch Query
Code Snippet Ideas: Performance Considerations for Stack Programs
When designing and implementing stack programs in C, there are certain performance considerations to keep in mind. Here are a few code snippets that demonstrate these performance considerations:
1. Use a fixed-size stack if the maximum number of elements is known in advance:
#define MAX_SIZE 100 int arr[MAX_SIZE]; int top = -1;
2. Avoid unnecessary stack operations by checking for stack overflow and underflow conditions:
void push(int data) {
if (top == MAX_SIZE - 1) {
printf("Stack overflow\n");
return;
}
arr[++top] = data;
}
int pop() {
if (top == -1) {
printf("Stack underflow\n");
return -1;
}
return arr[top--];
}
Stack Program Using an Array in C
Here's an example of a stack program using an array in C:
#include <stdio.h>
#define MAX_SIZE 100
typedef struct {
int arr[MAX_SIZE];
int top;
} Stack;
void initialize(Stack* stack) {
stack->top = -1;
}
int isEmpty(Stack* stack) {
return stack->top == -1;
}
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
void push(Stack* stack, int data) {
if (isFull(stack)) {
printf("Stack overflow\n");
return;
}
stack->arr[++stack->top] = data;
}
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return -1;
}
return stack->arr[stack->top--];
}
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->arr[stack->top];
}
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("Popped element: %d\n", pop(&stack));
printf("Top element: %d\n", peek(&stack));
return 0;
}
This program initializes a stack, pushes three elements onto the stack, prints the top element, pops two elements from the stack, and prints the top element again.
Linked Lists in C: An Alternative to Array-based Stacks
In addition to array-based stacks, linked lists can also be used to implement stacks in C. Linked lists provide dynamic memory allocation, allowing the stack size to be flexible. Here's an example of a stack implementation using linked lists:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct {
Node* top;
} Stack;
void initialize(Stack* stack) {
stack->top = NULL;
}
int isEmpty(Stack* stack) {
return stack->top == NULL;
}
void push(Stack* stack, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = stack->top;
stack->top = newNode;
}
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return -1;
}
Node* temp = stack->top;
int data = temp->data;
stack->top = temp->next;
free(temp);
return data;
}
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->top->data;
}
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("Popped element: %d\n", pop(&stack));
printf("Top element: %d\n", peek(&stack));
return 0;
}
This program demonstrates a stack implementation using linked lists. It initializes a stack, pushes three elements onto the stack, prints the top element, pops two elements from the stack, and prints the top element again.
Use Cases with Code Examples: Stack Implementation in C
Stacks have a wide range of use cases in C. Here are a few examples:
1. Evaluating infix expressions:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
typedef struct {
char arr[MAX_SIZE];
int top;
} Stack;
void initialize(Stack* stack) {
stack->top = -1;
}
int isEmpty(Stack* stack) {
return stack->top == -1;
}
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
void push(Stack* stack, char data) {
if (isFull(stack)) {
printf("Stack overflow\n");
return;
}
stack->arr[++stack->top] = data;
}
char pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return '\0';
}
return stack->arr[stack->top--];
}
char peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return '\0';
}
return stack->arr[stack->top];
}
int isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
int getPrecedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return -1;
}
void infixToPostfix(const char* infix, char* postfix) {
Stack stack;
initialize(&stack);
int j = 0;
for (int i = 0; infix[i] != '\0'; i++) {
char ch = infix[i];
if (isdigit(ch)) {
postfix[j++] = ch;
} else if (isOperator(ch)) {
while (!isEmpty(&stack) && getPrecedence(ch) <= getPrecedence(peek(&stack))) {
postfix[j++] = pop(&stack);
}
push(&stack, ch);
} else if (ch == '(') {
push(&stack, ch);
} else if (ch == ')') {
while (!isEmpty(&stack) && peek(&stack) != '(') {
postfix[j++] = pop(&stack);
}
if (!isEmpty(&stack) && peek(&stack) == '(') {
pop(&stack);
}
}
}
while (!isEmpty(&stack)) {
postfix[j++] = pop(&stack);
}
postfix[j] = '\0';
}
int evaluatePostfix(const char* postfix) {
Stack stack;
initialize(&stack);
for (int i = 0; postfix[i] != '\0'; i++) {
char ch = postfix[i];
if (isdigit(ch)) {
push(&stack, ch - '0');
} else if (isOperator(ch)) {
int operand2 = pop(&stack);
int operand1 = pop(&stack);
int result;
switch (ch) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
push(&stack, result);
}
}
return pop(&stack);
}
int main() {
char infix[100];
char postfix[100];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
int result = evaluatePostfix(postfix);
printf("Result: %d\n", result);
return 0;
}
This program converts an infix expression to postfix notation and evaluates the postfix expression. It uses a stack to perform the conversion and evaluation.
2. Checking for balanced parentheses in an expression:
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct {
char arr[MAX_SIZE];
int top;
} Stack;
void initialize(Stack* stack) {
stack->top = -1;
}
int isEmpty(Stack* stack) {
return stack->top == -1;
}
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
void push(Stack* stack, char data) {
if (isFull(stack)) {
printf("Stack overflow\n");
return;
}
stack->arr[++stack->top] = data;
}
char pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return '\0';
}
return stack->arr[stack->top--];
}
char peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return '\0';
}
return stack->arr[stack->top];
}
int isBalanced(const char* expression) {
Stack stack;
initialize(&stack);
for (int i = 0; expression[i] != '\0'; i++) {
char ch = expression[i];
if (ch == '(' || ch == '[' || ch == '{') {
push(&stack, ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
if (isEmpty(&stack)) {
return 0; // Unbalanced parentheses
}
char top = pop(&stack);
if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) {
return 0; // Unbalanced parentheses
}
}
}
return isEmpty(&stack); // Returns 1 if parentheses are balanced, 0 otherwise
}
int main() {
char expression[100];
printf("Enter an expression: ");
scanf("%s", expression);
if (isBalanced(expression)) {
printf("Parentheses are balanced\n");
} else {
printf("Parentheses are unbalanced\n");
}
return 0;
}
This program checks whether the parentheses in an expression are balanced or not using a stack.
These code examples demonstrate various use cases of stack implementation in C. Stacks are versatile data structures that can be applied to solve a wide range of problems efficiently and effectively.