PPT: Stacks & Queues | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

 Page 1


Stacks and 
Queues
Page 2


Stacks and 
Queues
Introduction to Stacks and Queues
Stack (LIFO)
A linear data structure 
following the Last In, First 
Out principle, where 
elements are added and 
removed from the same 
end.
Queue (FIFO)
A linear data structure 
following the First In, First 
Out principle, where 
elements are added at one 
end and removed from the 
other.
Key Characteristics
Both store elements in a 
specific order with 
operations restricted to 
specific ends of the 
structure.
Stacks are essential for function call management and expression evaluation, while queues 
excel in task scheduling and resource sharing cases.
Page 3


Stacks and 
Queues
Introduction to Stacks and Queues
Stack (LIFO)
A linear data structure 
following the Last In, First 
Out principle, where 
elements are added and 
removed from the same 
end.
Queue (FIFO)
A linear data structure 
following the First In, First 
Out principle, where 
elements are added at one 
end and removed from the 
other.
Key Characteristics
Both store elements in a 
specific order with 
operations restricted to 
specific ends of the 
structure.
Stacks are essential for function call management and expression evaluation, while queues 
excel in task scheduling and resource sharing cases.
Stack - Concept and 
Operations
Push
Adds an element to the 
top of the stack
Pop
Removes and returns the 
top element
Peek/Top
Returns the top element 
without removing it
IsEmpty/IsFull
Checks if the stack is 
empty or full
The defining property of a stack is its LIFO (Last In, First Out) 
behavior - the last element added is always the first to be removed. 
All primary stack operations have a time complexity of O(1).
For example, if we Push(3), Push(5), and then Pop(), we'll get 5 back 
and our stack will contain only [3].
Page 4


Stacks and 
Queues
Introduction to Stacks and Queues
Stack (LIFO)
A linear data structure 
following the Last In, First 
Out principle, where 
elements are added and 
removed from the same 
end.
Queue (FIFO)
A linear data structure 
following the First In, First 
Out principle, where 
elements are added at one 
end and removed from the 
other.
Key Characteristics
Both store elements in a 
specific order with 
operations restricted to 
specific ends of the 
structure.
Stacks are essential for function call management and expression evaluation, while queues 
excel in task scheduling and resource sharing cases.
Stack - Concept and 
Operations
Push
Adds an element to the 
top of the stack
Pop
Removes and returns the 
top element
Peek/Top
Returns the top element 
without removing it
IsEmpty/IsFull
Checks if the stack is 
empty or full
The defining property of a stack is its LIFO (Last In, First Out) 
behavior - the last element added is always the first to be removed. 
All primary stack operations have a time complexity of O(1).
For example, if we Push(3), Push(5), and then Pop(), we'll get 5 back 
and our stack will contain only [3].
Stack Implementation
Array-Based Implementation
Uses an array with a fixed or dynamic size and 
maintains a t o p pointer to track the top 
element. Push operation increments top and 
adds the element, while Pop returns the 
element at top and decrements the pointer.
A d v a n t a g e s : Simple and memory-efficient
D i s a d v a n t a g e s : Fixed size with risk of 
overflow
Linked List Implementation
Uses a singly linked list where the top is the 
head. Push operation adds a node at the head 
(O(1)), and Pop removes the head node (O(1)).
A d v a n t a g e s : Dynamic size with no overflow 
risk
D i s a d v a n t a g e s : Extra memory required for 
pointers
Page 5


Stacks and 
Queues
Introduction to Stacks and Queues
Stack (LIFO)
A linear data structure 
following the Last In, First 
Out principle, where 
elements are added and 
removed from the same 
end.
Queue (FIFO)
A linear data structure 
following the First In, First 
Out principle, where 
elements are added at one 
end and removed from the 
other.
Key Characteristics
Both store elements in a 
specific order with 
operations restricted to 
specific ends of the 
structure.
Stacks are essential for function call management and expression evaluation, while queues 
excel in task scheduling and resource sharing cases.
Stack - Concept and 
Operations
Push
Adds an element to the 
top of the stack
Pop
Removes and returns the 
top element
Peek/Top
Returns the top element 
without removing it
IsEmpty/IsFull
Checks if the stack is 
empty or full
The defining property of a stack is its LIFO (Last In, First Out) 
behavior - the last element added is always the first to be removed. 
All primary stack operations have a time complexity of O(1).
For example, if we Push(3), Push(5), and then Pop(), we'll get 5 back 
and our stack will contain only [3].
Stack Implementation
Array-Based Implementation
Uses an array with a fixed or dynamic size and 
maintains a t o p pointer to track the top 
element. Push operation increments top and 
adds the element, while Pop returns the 
element at top and decrements the pointer.
A d v a n t a g e s : Simple and memory-efficient
D i s a d v a n t a g e s : Fixed size with risk of 
overflow
Linked List Implementation
Uses a singly linked list where the top is the 
head. Push operation adds a node at the head 
(O(1)), and Pop removes the head node (O(1)).
A d v a n t a g e s : Dynamic size with no overflow 
risk
D i s a d v a n t a g e s : Extra memory required for 
pointers
Applications of Stacks
Function Call 
Management
Stores function call details 
including return addresses 
and local variables, 
managed by the system 
call stack
Expression Evaluation
Converts infix to postfix 
expressions (e.g., A+B*C ³ 
ABC*+) and evaluates 
postfix expressions (e.g., 
23*4+ ³ 10)
Backtracking
Used in algorithms like 
depth-first search (DFS) 
and maze solving
Undo Operations
Stores states for reverting actions in applications like text editors