Introduction to Stack in Data Structures

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning
the last element added to the stack is the first one to be removed. It is widely used in
programming for tasks like managing function calls, evaluating expressions, and undoing
operations in applications.

Characteristics of a Stack

●​ LIFO Principle: The element inserted last is the first to be removed.

●​ One End Operations: Elements can be added (pushed) or removed (popped) only
from the top of the stack.

●​ Fixed Size or Dynamic: Depending on implementation, stacks can have a fixed size
(array-based) or be dynamic in size (linked list-based).

Basic Operations on a Stack

●​ Push: Add an element to the top of the stack.

●​ Pop: Remove the top element from the stack.
●​ Peek/Top: Retrieve the top element without removing it.
●​ isEmpty: Check if the stack is empty.
●​ isFull: Check if the stack is full (only for array-based implementations).

Representation of a Stack

Stacks can be implemented in two ways:

Array-Based Stack:
●​ Uses a fixed-size array.
●​ Simple to implement but has a limitation of a fixed size.

Linked List-Based Stack:

●​ Dynamic in size.
●​ Each element (node) has a value and a pointer to the next node.

Stack Operations in Detail

1. Push Operation

Adds an element to the top of the stack.

Steps:
Check if the stack is full (in array implementation).
Increment the top pointer.
Insert the element at the position pointed by top.
2. Pop Operation

Removes the top element of the stack.

Steps:
Check if the stack is empty.
Retrieve the element at the position pointed by top.
Decrement the top pointer.

3. Peek Operation

Retrieves the top element without removing it.

Steps:
Check if the stack is empty.
Return the value at the position pointed by top.

4. isEmpty Operation

Checks if the stack has no elements.

Steps:
Return true if top == -1; otherwise, return false.
Algorithmic Example

Push Operation

PUSH(stack, element, maxSize):

if TOP == maxSize – 1:

print “Stack Overflow”

else:

TOP = TOP + 1

stack[TOP] = element

Pop Operation

POP(stack):

if TOP == -1:

print “Stack Underflow”

else:

element = stack[TOP]
 TOP = TOP – 1

return element

Applications of Stacks

1.​ Function Call Management: Used in recursion and backtracking.

2.​ Expression Evaluation:
●​ Infix to Postfix/Prefix Conversion.
●​ Evaluating Postfix/Prefix expressions.
3.​ Undo/Redo Mechanism: Common in text editors and software.
4.​ Balancing Parentheses: Validating expressions with brackets.
5.​ Browser History Navigation: Managing forward and backward navigation.

Advantages of Stacks

●​ Simple to implement.
●​ Efficient for LIFO operations.
●​ Useful in solving problems like parsing, recursion, and backtracking.

Limitations of Stacks

●​ Limited size in array-based implementation.

●​ Access is restricted to the top element only.

Example

Stack Push and Pop Example

Suppose a stack has a capacity of 5 and is initially empty:

Push 10 → Stack: [10]

Push 20 → Stack: [10, 20]
Push 30 → Stack: [10, 20, 30]
Pop → Removed 30; Stack: [10, 20]
Peek → Top element is 20.

Visualization

A stack can be visualized as a stack of plates where:

●​ Adding a plate is analogous to the push operation.

●​ Removing the top plate is analogous to the pop operation.

Stack using Array

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It can be
implemented using an array by treating the end of the array as the top of the stack.
Declaration of Stack using Array

●​ A stack can be implemented using an array where we maintain:

●​ An integer array to store elements.
●​ A variable capacity to represent the maximum size of the stack.
●​ A variable top to track the index of the top element. Initially, top = -1 to indicate an
empty stack.

Full Implementation of Stack using Array

#include <iostream>
using namespace std;

class myStack {

// array to store elements

int *arr;

// maximum size of stack

int capacity;

// index of top element

int top;

public:

// constructor
myStack(int cap) {
capacity = cap;
arr = new int[capacity];
top = -1;
}

// push operation
void push(int x) {
if (top == capacity - 1) {
cout << "Stack Overflow\n";
return;
}
arr[++top] = x;
}

// pop operation
int pop() {
if (top == -1) {
cout << "Stack Underflow\n";
return -1;
 }
return arr[top--];
}

// peek (or top) operation

int peek() {
if (top == -1) {
cout << "Stack is Empty\n";
return -1;
}
return arr[top];
}

// check if stack is empty

bool isEmpty() {
return top == -1;
}

// check if stack is full

bool isFull() {
return top == capacity - 1;
}
};

int main() {
myStack st(4);

// pushing elements
[Link](1);
[Link](2);
[Link](3);
[Link](4);

// popping one element

cout << "Popped: " << [Link]() << "\n";

// checking top element

cout << "Top element: " << [Link]() << "\n";

// checking if stack is empty

cout << "Is stack empty: " << ([Link]() ? "Yes" : "No") << "\n";

// checking if stack is full

cout << "Is stack full: " << ([Link]() ? "Yes" : "No") << "\n";

return 0;
}
Output

Popped: 4
Top element: 3
Is stack empty: No
Is stack full: No

​Stack - Linked List Implementation

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It can be
implemented using a linked list, where each element of the stack is represented as a node.
The head of the linked list acts as the top of the stack.

Declaration of Stack using Linked List

A stack can be implemented using a linked list where we maintain:

●​ A Node structure/class that contains:

●​ data → to store the element.
●​ next → pointer/reference to the next node in the stack.
●​ A pointer/reference top that always points to the current top node of the stack.
●​ Initially, top = null to represent an empty stack.

Stack Implementation using Linked List

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
int data;
Node* next;

Node(int x) {
data = x;
next = NULL;
}
};

// Stack implementation using linked list

class myStack {
Node* top;

// To Store current size of stack

int count;
public:
myStack() {

// initially stack is empty

top = NULL;
count = 0;
}

// push operation
void push(int x) {
Node* temp = new Node(x);
temp->next = top;
top = temp;

count++;
}

// pop operation
int pop() {
if (top == NULL) {
cout << "Stack Underflow" << endl;
return -1;
}
Node* temp = top;
top = top->next;
int val = temp->data;

count--;
delete temp;
return val;
}

// peek operation
int peek() {
if (top == NULL) {
cout << "Stack is Empty" << endl;
return -1;
}
return top->data;
}

// check if stack is empty

bool isEmpty() {
return top == NULL;
}

// size of stack
int size() {
 return count;
}
8};

int main() {
myStack st;

// pushing elements
[Link](1);
[Link](2);
[Link](3);
[Link](4);

// popping one element

cout << "Popped: " << [Link]() << endl;

// checking top element

cout << "Top element: " << [Link]() << endl;

// checking if stack is empty

cout << "Is stack empty: " << ([Link]() ? "Yes" : "No") << endl;

// checking current size

cout << "Current size: " << [Link]() << endl;

return 0;
}

Output
Popped: 4
Top element: 3
Is stack empty: No
Current size: 3

Applications of Stack

Stacks are versatile and used in many areas of computer science and real-world
applications. Here are some common applications:

1. Expression Evaluation and Conversion

Infix to Postfix/Prefix Conversion: Stacks are used to convert infix expressions (e.g., A + B *
C) to postfix (e.g., ABC*+) or prefix (e.g., +A*BC).
Expression Evaluation: Postfix or prefix expressions are evaluated using stacks.

2. Function Call Management (Recursion)

The call stack in programming languages stores information about function calls.
It tracks return addresses, local variables, and parameters for recursive or nested function
calls.

3. Undo and Redo Operations

Text editors and applications use stacks to manage undo (reverting to the previous state)
and redo (reapplying an undone action) operations.

4. Browser History

A browser’s back and forward navigation system uses two stacks:

One stack for back history.
Another stack for forward history.

5. Parsing

Stacks are used in parsing operations, such as:

Syntax parsing in compilers to check matching parentheses or braces.
Processing XML or HTML tags to ensure proper nesting.

6. Tower of Hanoi

Stacks are used to simulate or solve the Tower of Hanoi puzzle efficiently.

7. Balancing Symbols

Stacks are employed to check if symbols in a string (e.g., {}, [], ()) are balanced correctly, like
in mathematical expressions or code.

8. Depth-First Search (DFS)

DFS in graph traversal uses stacks to explore nodes and backtrack when needed.
9. Memory Management

Operating systems use stacks for memory allocation in processes, particularly in managing
stack frames for functions.

10. Backtracking Algorithms

Stacks are used in backtracking problems, such as:

Solving mazes.
N-Queens problem.
Sudoku solving.

Multiple Stacks
Sometimes, applications require maintaining multiple stacks within the same memory space,
such as for managing multiple processes or tasks. Instead of creating separate arrays for
each stack, a single array can be divided dynamically or statically to store multiple stacks.

Approaches for Multiple Stacks

1.​ Fixed Partitioning:

●​ Divide the array into fixed sections, one for each stack.
●​ Requires prior knowledge of the maximum size each stack might need.
●​ Risk: Some stacks may overflow while others remain underutilized.

2.​ Dynamic Partitioning:

●​ Allow stacks to grow dynamically by overlapping their boundaries.
●​ Use additional metadata to manage free space and stack boundaries.

Implementation of Multiple Stacks as Queues

When multiple stacks need to function as separate queues within a single memory array, a
strategic implementation is required. This can be done using fixed partitioning or dynamic
partitioning methods.

Here’s a detailed explanation and implementation:

1. Concept of Multiple Stacks as Queues

To implement multiple queues using stacks:

●​ Each queue uses two stacks.

Stack 1 (Input Stack): Used for enqueue operations (pushing elements).
Stack 2 (Output Stack): Used for dequeue operations (retrieving elements).
●​ Queues are managed independently.

2. Operations in Each Queue

●​ Enqueue:
Push the element into Stack 1.
●​ Dequeue:
If Stack 2 is empty, transfer all elements from Stack 1 to Stack 2.
Pop the top element from Stack 2.

Applications of Multiple Stacks as Queues

●​ Process Scheduling: Managing independent task queues.

●​ Simulation: Modeling scenarios requiring FIFO behavior.
●​ Communication Systems: Handling multiple message queues in parallel.