STACK & QUEUE

Stack
A stack is a linear data structure that operates on the LIFO (Last In, First Out)
principle, meaning the last element added to the stack is the first one to be
removed.

Basic Operations of a Stack:

1. Push(x): Adds an element x to the top of the stack.

2. Pop(): Removes and returns the top element of the stack.

3. Peek()/Top(): Returns the top element without removing it.

4. isEmpty(): Checks if the stack is empty.

Applications of Stacks
1. Expression Conversion (Infix to Postfix/Prefix)

Stacks are widely used for converting expressions between infix, prefix, and
postfix notations.

Algorithm for Infix to Postfix Conversion

1. Initialize an empty stack and an empty string for the result.

2. Read the infix expression from left to right:

If the character is an operand, append it to the result string.

If the character is an operator:

Pop and append all operators from the stack that have higher or
equal precedence.

Push the current operator onto the stack.

If the character is an opening parenthesis, push it onto the stack.

If the character is a closing parenthesis:

Pop and append all operators from the stack until an opening
parenthesis is encountered.

Remove the opening parenthesis.

 3. Pop all remaining operators from the stack and append them to the result
string.

Time Complexity:

Traversal: O(n), where n is the length of the expression.

Stack Operations: Each element is pushed and popped once, so O(n).

Overall Complexity: O(n).

2. Expression Evaluation (Postfix/Prefix)

Once an expression is in postfix or prefix form, it can be evaluated using a

stack.

Algorithm for Postfix Evaluation

1. Initialize an empty stack.

2. Read the postfix expression from left to right:

If the character is an operand, push it onto the stack.

If the character is an operator:

Pop the top two elements from the stack.

Apply the operator to these elements.

Push the result back onto the stack.

3. The final value in the stack is the result of the expression.

Time Complexity:

Traversal: O(n), where n is the length of the expression.

Stack Operations: O(n).

Overall Complexity: O(n).

Abstract Data Type (ADT) for Stack

An ADT (Abstract Data Type) for a stack specifies its behavior and operations,
irrespective of how it is implemented (array or linked list).
Stack ADT Operations

1. CreateStack(maxSize): Initializes an empty stack with a maximum size.

2. Push(stack, x): Adds element x to the stack if it’s not full.

3. Pop(stack): Removes and returns the top element of the stack if it’s not
empty.

4. Peek(stack): Returns the top element without removing it.

5. isEmpty(stack): Returns true if the stack is empty.

6. isFull(stack): Returns true if the stack is full.

Implementation Using Array

Algorithm for Stack Operations

1. Push(x):

1 Algorithm Push(stack, x):

2
3 1. If stack.top == stack.maxSize - 1:
4 Print "Stack Overflow".
5 Return.
6 2. Increment stack.top by 1.
7 3. Set stack[stack.top] = x.

Time Complexity: O(1).

2. Pop():

1 Algorithm Pop(stack):
2
3 1. If stack.top == -1:
4 Print "Stack Underflow".
5 Return.
6 2. Set x = stack[stack.top].
7 3. Decrement stack.top by 1.
8 4. Return x.

Time Complexity: O(1).

3. Peek():
 1 Algorithm Peek(stack):
2
3 1. If stack.top == -1:
4 Print "Stack is Empty".
5 Return.
6 2. Return stack[stack.top].

Time Complexity: O(1).

Implementation Using Linked List

1. Push(x):

1 Algorithm Push(stack, x):

2
3 1. Create a new node with value x.
4 2. Set newNode.next = stack.top.
5 3. Set stack.top = newNode.

Time Complexity: O(1).

2. Pop():

1 Algorithm Pop(stack):
2
3 1. If stack.top == NULL:
4 Print "Stack Underflow".
5 Return.
6 2. Set x = stack.top.value.
7 3. Set stack.top = stack.top.next.
8 4. Free the memory of the popped node.
9 5. Return x.

Time Complexity: O(1).

Complexity Analysis

Linked List
Operation Array Implementation
Implementation

Push(x) O(1) O(1)

Pop() O(1) O(1)

 Linked List
Operation Array Implementation
Implementation

Peek() O(1) O(1)

Space Requires predefined size Dynamic allocation

Complexity (O(n)). (O(n)).

Queue: Abstract Data Type (ADT)

A queue is a linear data structure that operates on the FIFO (First In, First Out)
principle, where the first element added to the queue is the first one to be
removed.

Queue ADT Operations

1. CreateQueue(maxSize): Initializes an empty queue with a maximum size.

2. Enqueue(queue, x): Adds an element x to the rear of the queue.

3. Dequeue(queue): Removes and returns the front element of the queue.

4. Peek(queue): Returns the front element without removing it.

5. isEmpty(queue): Returns true if the queue is empty.

6. isFull(queue): Returns true if the queue is full.

Types of Queues
1. Simple Queue

A basic queue that follows the FIFO principle.

Insertions occur at the rear and deletions occur at the front.

Operations

1. Enqueue(x): Adds an element x to the rear.

Algorithm:
 1 Algorithm Enqueue(queue, x):
2
3 1. If (rear == maxSize - 1):
4 Print "Queue Overflow".
5 Return.
6 2. Increment rear by 1.
7 3. Set queue[rear] = x.

Time Complexity: O(1).

2. Dequeue(): Removes the front element.

Algorithm:

1 Algorithm Dequeue(queue):
2
3 1. If (front > rear):
4 Print "Queue Underflow".
5 Return.
6 2. Set x = queue[front].
7 3. Increment front by 1.
8 4. Return x.

Time Complexity: O(1).

Drawback:

Wasted Space: Once elements are dequeued, those spaces cannot be

reused.

2. Circular Queue

Overcomes the limitation of wasted space in simple queues by connecting

the last position back to the first, forming a circular structure.

The rear and front pointers wrap around to the beginning of the array when
they reach the end.

Operations

1. Enqueue(x): Adds an element x to the rear.

Algorithm:
 1 Algorithm Enqueue(queue, x):
2
3 1. If ((rear + 1) % maxSize == front):
4 Print "Queue Overflow".
5 Return.
6 2. If (front == -1):
7 Set front = 0.
8 3. Set rear = (rear + 1) % maxSize.
9 4. Set queue[rear] = x.

Time Complexity: O(1).

2. Dequeue(): Removes the front element.

Algorithm:

1 Algorithm Dequeue(queue):
2
3 1. If (front == -1):
4 Print "Queue Underflow".
5 Return.
6 2. Set x = queue[front].
7 3. If (front == rear):
8 Set front = rear = -1. // Reset queue.
9 Else:
10 Set front = (front + 1) % maxSize.
11 4. Return x.

Time Complexity: O(1).

Advantages:

Efficient space utilization.

Can handle wrap-around situations.

3. Priority Queue

A queue in which each element is associated with a priority.

Elements with higher priority are dequeued before elements with lower
priority.

If two elements have the same priority, they are dequeued in FIFO order.
Operations

1. Enqueue(x, priority): Adds an element x with its priority.

Algorithm

(for an unsorted array implementation):

1 Algorithm Enqueue(queue, x, priority):

2
3 1. Add the element `x` with its priority to the end of
the array.

Time Complexity: O(1).

2. Dequeue(): Removes the element with the highest priority.

Algorithm (for an unsorted array implementation):

1 Algorithm Dequeue(queue):
2
3 1. If (queue is empty):
4 Print "Queue Underflow".
5 Return.
6 2. Find the element with the highest priority.
7 3. Remove that element from the array.
8 4. Return the element.

Time Complexity: O(n), where n is the number of elements in the

queue.

Advantages:

Handles priority-based processing effectively.

Drawback:

Complexity for finding the highest priority element depends on the

implementation (e.g., O(n) for an unsorted array).
Comparison of Simple Queue, Circular Queue,
and Priority Queue

Aspect Simple Queue Circular Queue Priority Queue

Linear with
Structure Linear Circular
priority

At the rear Based on

Insertion At the rear (wrap-around priority or at
allowed) rear

Highest priority
Deletion From the front From the front
element

Efficient for
Wastes space Efficient space
Efficiency priority-based
after dequeue utilization
tasks

O(1) (unsorted),
Complexity
O(1) O(1) O(log n
⁡ ) (sorted
(Enqueue)
heap)

O(n) (unsorted),
Complexity
O(1) O(1) O(log⁡n) (sorted
(Dequeue)
heap)

Scheduling, CPU
Buffer
Applications resource scheduling,
management
management event handling

Difference between Stack and

Queue
Aspect Stack Queue

A linear data structure A linear data structure

that follows the LIFO that follows the FIFO
Definition
(Last In, First Out) (First In, First Out)
principle. principle.
Aspect Stack Queue

Principle Last In, First Out (LIFO). First In, First Out (FIFO).

Elements are added Elements are added

Insertion Point
(pushed) at the top. (enqueued) at the rear.

Elements are removed

Elements are removed
Deletion Point (dequeued) from the
(popped) from the top.
front.

Only the top element Only the front element

Access
can be accessed. can be accessed.

Push (insertion), Pop Enqueue (insertion),

Operations (deletion), Peek (view top Dequeue (deletion), Peek
element). (view front element).

Works like a vertical Works like a horizontal

Structure stack (e.g., a pile of queue (e.g., a line at a
plates). ticket counter).

Implemented using
Implemented using
Implementation arrays, linked lists, or
arrays or linked lists.
circular queues.

Function call Process scheduling,

management, recursion, breadth-first search (BFS),
Applications
undo/redo operations, customer service
backtracking. management.

Requires memory for

Requires memory for a
Memory Usage front and rear pointers
top pointer (or index).
(or indices).

Simple Queue, Circular

Simple Stack, Double
Variants Queue, Priority Queue,
Stack.
Deque.

Enqueue(10),
Push(10), Push(20), Pop()
Example Enqueue(20), Dequeue()
→ Stack: [10].
→ Queue: [20].