Index
Stack
A stack is a fundamental data structure that follows the Last-In, First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. It operates on two main operations: push and pop.
Here’s an overview of stack operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes the element from the top of the stack.
- Peek (or Top): Returns the element at the top of the stack without removing it.
- isEmpty: Checks if the stack is empty.
- isFull: Checks if the stack is full (for fixed-size stacks).
Stacks are commonly used in various computer science applications, including:
- Function call management: Storing return addresses during function calls.
- Expression evaluation and parsing: Evaluating expressions and parsing syntax.
- Undo functionality in text editors and software: Storing previous states to enable undo operations.
- Backtracking algorithms: Storing states to backtrack to previous decisions.
- Memory management: Storing variables and function call information during program execution.
Stacks can be implemented using various underlying data structures, including arrays and linked lists. The choice of implementation depends on factors like memory constraints, performance requirements, and the specific application context.
Stack Implementation using Arrays
Reasons to implement stacks using arrays:
- Memory Efficient: Array elements do not hold the next elements address like linked list nodes do.
- Easier to implement and understand: Using arrays to implement stacks require less code than using linked lists, and for this reason it is typically easier to understand as well.
A reason for not using arrays to implement stacks:
- Fixed size: An array occupies a fixed part of the memory. This means that it could take up more memory than needed, or if the array fills up, it cannot hold more elements.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *stack;
int top;
int capacity;
} Stack;
Stack* createStack(int capacity) {
Stack *newStack = (Stack*)malloc(sizeof(Stack));
newStack->stack = (int*)malloc(capacity * sizeof(int));
newStack->top = -1;
newStack->capacity = capacity;
return newStack;
}
void push(Stack *s, int element) {
if (s->top == s->capacity - 1) {
printf("Stack is full\n");
return;
}
s->stack[++s->top] = element;
}
int pop(Stack *s) {
if (s->top == -1) {
printf("Stack is empty\n");
return -1;
}
return s->stack[s->top--];
}
int peek(Stack *s) {
if (s->top == -1) {
printf("Stack is empty\n");
return -1;
}
return s->stack[s->top];
}
int isEmpty(Stack *s) {
return s->top == -1;
}
int size(Stack *s) {
return s->top + 1;
}
void printStack(Stack *s) {
printf("Stack: ");
for (int i = 0; i <= s->top; ++i) {
printf("%c ", s->stack[i]);
}
printf("\n");
}
int main() {
Stack *myStack = createStack(100);
push(myStack, 'A');
push(myStack, 'B');
push(myStack, 'C');
push(myStack, 'D');
// Print initial stack
printStack(myStack);
printf("Pop: %c\n", pop(myStack));
printf("Peek: %c\n", peek(myStack));
printf("isEmpty: %d\n", isEmpty(myStack));
printf("Size: %d\n", size(myStack));
return 0;
}
Output:
Stack: A B C
Pop: D
Peek: C
isEmpty: 0
Size: 3
Stack Implementation using Linked List
A reason for using linked lists to implement stacks:
- Dynamic size: The stack can grow and shrink dynamically, unlike with arrays.
Reasons for not using linked lists to implement stacks:
- Extra memory: Each stack element must contain the address to the next element (the next linked list node).
- Readability: The code might be harder to read and write for some because it is longer and more complex.
#include <stdio.h>
#include <stdlib.h>
// Define a structure for the node
struct Node {
int data;
struct Node* next;
};
// Define a structure for the stack
struct Stack {
struct Node* top;
};
// Function to initialize the stack
void initialize(struct Stack *stack) {
stack->top = NULL; // Initialize top to NULL to indicate an empty stack
}
// Function to check if the stack is empty
int isEmpty(struct Stack *stack) {
return (stack->top == NULL); // If top is NULL, stack is empty
}
// Function to push an element onto the stack
void push(struct Stack *stack, int item) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}
// Assign data to the new node
newNode->data = item;
// Set the next of the new node to the current top
newNode->next = stack->top;
// Move the top to point to the new node
stack->top = newNode;
}
// Function to pop an element from the stack
int pop(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack Underflow\n");
return -1; // Return an error value
}
// Retrieve the item at the top of the stack
int item = stack->top->data;
// Store the current top node
struct Node* temp = stack->top;
// Move the top to the next node
stack->top = stack->top->next;
// Free the memory of the popped node
free(temp);
return item; // Return the popped item
}
// Function to peek at the top element of the stack
int peek(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1; // Return an error value
}
return stack->top->data; // Return the item at the top of the stack
}
int main() {
struct Stack stack;
initialize(&stack);
// Push elements onto the stack
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
// Print the top element of the stack
printf("Top element of stack: %d\n", peek(&stack));
// Pop elements from the stack and print them
printf("Elements popped from stack:\n");
while (!isEmpty(&stack)) {
printf("%d\n", pop(&stack));
}
return 0;
}
Output:
Top element of stack: 30
Elements popped from stack:
30
20
10
