Algorithm
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. Think of it like a stack of plates – you add a plate to the top, and you take a plate from the top.
Key operations associated with a stack are:
-
Push Operation:
- Adding an element to the stack is known as the "push" operation. The new element is added to the top of the stack.
- The stack grows in the upward direction, and the index of the top element is incremented.
-
Pop Operation:
- Removing an element from the stack is known as the "pop" operation. The top element is removed.
- The stack shrinks, and the index of the top element is decremented.
-
Peek/Top Operation:
- The "peek" or "top" operation retrieves the value of the top element without removing it. It simply looks at the value of the element at the top of the stack.
-
Empty Stack:
- A stack is considered empty when it contains no elements. This condition is usually checked before performing a pop or peek operation to avoid errors.
-
Full Stack (in fixed-size implementations):
- In some implementations with a fixed-size array, a stack may become full when it reaches its maximum capacity. Attempting to push an element onto a full stack may result in an overflow condition.
The operations on a stack are typically very fast with a time complexity of O(1) because the addition and removal of elements always happen at the top, and there is no need to traverse the entire data structure.
Code Examples
#1 Simple implementation of a stack in Python
Code -
Python Programming
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
else:
raise IndexError("pop from an empty stack")
def peek(self):
if not self.is_empty():
return self.items[-1]
else:
raise IndexError("peek from an empty stack")
def size(self):
return len(self.items)
# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Stack:", stack.items) # Output: Stack: [1, 2, 3]
print("Pop:", stack.pop()) # Output: Pop: 3
print("Peek:", stack.peek()) # Output: Peek: 2
print("Size:", stack.size()) # Output: Size: 2
#2 Simple implementation of a stack in Java
Code -
Java Programming
public class Stack {
private static final int MAX_SIZE = 1000; // Maximum size of the stack
private int top; // Index of the top element
private int[] array; // Array to store stack elements
public Stack() {
this.top = -1;
this.array = new int[MAX_SIZE];
}
// Push operation to add an element to the stack
public void push(int value) {
if (top >= MAX_SIZE - 1) {
System.out.println("Stack Overflow - Cannot push more elements.");
return;
}
array[++top] = value;
System.out.println(value + " pushed to the stack");
}
// Pop operation to remove the top element from the stack
public int pop() {
if (top < 0) {
System.out.println("Stack Underflow - Cannot pop from an empty stack.");
return -1; // indicating stack underflow
}
int value = array[top--];
System.out.println(value + " popped from the stack");
return value;
}
// Peek operation to get the top element without removing it
public int peek() {
if (top < 0) {
System.out.println("Stack is empty");
return -1; // indicating an empty stack
}
return array[top];
}
// Check if the stack is empty
public boolean isEmpty() {
return top < 0;
}
// Display the stack elements
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty");
return;
}
System.out.print("Stack: ");
for (int i = 0; i < = top; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.display();
System.out.println("Top element: " + stack.peek());
stack.pop();
stack.display();
System.out.println("Is the stack empty? " + stack.isEmpty());
}
}
#3 Stack using Arrays:
Code -
C Programming
#include <stdio.h>
#define MAX_SIZE 100
// Structure to represent a stack
struct Stack {
int arr[MAX_SIZE];
int top;
};
// Function to initialize the stack
void initialize(struct Stack *stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack *stack) {
return stack->top == -1;
}
// Function to check if the stack is full
int isFull(struct Stack *stack) {
return stack->top == MAX_SIZE - 1;
}
// Function to push an element onto the stack
void push(struct Stack *stack, int value) {
if (isFull(stack)) {
printf("Stack overflow\n");
return;
}
stack->arr[++stack->top] = value;
}
// Function to pop an element from the stack
int pop(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return -1; // Assuming -1 represents an invalid value
}
return stack->arr[stack->top--];
}
// Function to get the top element of the stack without popping it
int peek(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1; // Assuming -1 represents an invalid value
}
return stack->arr[stack->top];
}
int main() {
struct 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("Is the stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");
return 0;
}
#4 Stack using Linked List:
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a node in the stack
struct Node {
int data;
struct Node* next;
};
// Structure to represent a stack
struct Stack {
struct Node* top;
};
// Function to initialize the stack
void initialize(struct Stack *stack) {
stack->top = NULL;
}
// Function to check if the stack is empty
int isEmpty(struct Stack *stack) {
return stack->top == NULL;
}
// Function to push an element onto the stack
void push(struct Stack *stack, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}
newNode->data = value;
newNode->next = stack->top;
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; // Assuming -1 represents an invalid value
}
struct Node* temp = stack->top;
int poppedValue = temp->data;
stack->top = temp->next;
free(temp);
return poppedValue;
}
// Function to get the top element of the stack without popping it
int peek(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1; // Assuming -1 represents an invalid value
}
return stack->top->data;
}
int main() {
struct 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("Is the stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");
return 0;
}
#5 Stack using Array:
Code -
C++ Programming
#include <iostream>
#include <stdexcept>
const int MAX_SIZE = 100; // Maximum size of the stack
class Stack {
private:
int arr[MAX_SIZE];
int top;
public:
Stack() : top(-1) {}
void push(int value) {
if (top >= MAX_SIZE - 1) {
throw std::overflow_error("Stack overflow");
}
arr[++top] = value;
}
void pop() {
if (top < 0) {
throw std::underflow_error("Stack underflow");
}
--top;
}
int peek() const {
if (top < 0) {
throw std::underflow_error("Stack is empty");
}
return arr[top];
}
bool isEmpty() const {
return top < 0;
}
};
int main() {
Stack myStack;
myStack.push(1);
myStack.push(2);
myStack.push(3);
std::cout << "Top element: " << myStack.peek() << std::endl;
myStack.pop();
std::cout << "Top element after pop: " << myStack.peek() << std::endl;
return 0;
}
#6 Stack using Linked List:
Code -
C++ Programming
#include <iostream>
#include <stdexcept>
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class Stack {
private:
Node* top;
public:
Stack() : top(nullptr) {}
void push(int value) {
Node* newNode = new Node(value);
newNode->next = top;
top = newNode;
}
void pop() {
if (isEmpty()) {
throw std::underflow_error("Stack underflow");
}
Node* temp = top;
top = top->next;
delete temp;
}
int peek() const {
if (isEmpty()) {
throw std::underflow_error("Stack is empty");
}
return top->data;
}
bool isEmpty() const {
return top == nullptr;
}
};
int main() {
Stack myStack;
myStack.push(1);
myStack.push(2);
myStack.push(3);
std::cout << "Top element: " << myStack.peek() << std::endl;
myStack.pop();
std::cout << "Top element after pop: " << myStack.peek() << std::endl;
return 0;
}
Demonstration
Stack Data Structure- DevsEnv