Stack-Queue

CSD202
FTP University

11/06/2025 Data Structures and Algorithms in C++ 1

 Introduction to Stack

 Stack is a linear data structure that follows the LIFO (Last

In, First Out) principle.

The last element added is the first one to be removed.

 Example: A stack of plates - last placed plate is the first

one taken out.

11/06/2025 Data Structures and Algorithms in C++ 2

 Stack Structure
 Two Main Operations:
– push(x): Insert an element at the top.
– pop(): Remove the top element.
 Additional Operations:
– peek() / top(): Get the top element without removing it.
– isEmpty(): Check if the stack is empty.
– isFull(): Check if the stack is full (in case of a fixed-size
stack).

11/06/2025 Data Structures and Algorithms in C++ 3

 Stack Representation
 Stack using an Array

#define MAX 100

int stack[MAX], top = -1;
void push(int x) {
if (top == MAX - 1) return; // Stack Overflow
stack[++top] = x;
}
void pop() {
if (top == -1) return; // Stack Underflow
top--;
}

11/06/2025 Data Structures and Algorithms in C++ 4

 Stack Representation
 Stack using Linked List

11/06/2025 Data Structures and Algorithms in C++ 5

 Advantages & Disadvantages of
Stack
Advantages:

– Simple and efficient for managing function calls, parsing, and

backtracking.
– Requires constant time for push and pop operations (O(1)).

 Disadvantages:
– Fixed size (in array implementation) can lead to stack overflow.
– Limited access (only the top element can be accessed).

11/06/2025 Data Structures and Algorithms in C++ 6

 Applications of Stack
 Function Call Management (Recursion, system calls).
 Expression Evaluation (Postfix/Infix conversion).
 Undo/Redo in text editors.
 Backtracking (Maze solving, puzzles).
 Browser History Management.

11/06/2025 Data Structures and Algorithms in C++ 7

 Stack in Real-Life Applications

 Web Browsing: Back/Forward button navigation.

 Text Editors: Ctrl+Z (Undo) uses a stack.
 Programming Languages: Function calls are stored in a
stack.
 Game Development: State management (e.g.,
Pause/Resume).

11/06/2025 Data Structures and Algorithms in C++ 8

 Stack vs. Queue

Feature Stack (LIFO) Queue (FIFO)

Order Last In, First Out
First In, First Out
Access Only Top Element Only
Element
Front

Enqueue,
Operations Push, Pop, Peek Dequeue
Example Undo Feature Task Scheduling

11/06/2025 Data Structures and Algorithms in C++ 9

 Introduction to Queue

 Queue is a linear data structure that follows the FIFO

(First In, First Out) principle.

 The first element added is the first one to be removed.

 Example: A queue of people waiting in line - first

person in line is served first.

11/06/2025 Data Structures and Algorithms in C++ 10

 Queue Structure
 Two Main Operations:

– Enqueue(x): Insert an element at the rear.

– Dequeue(): Remove the element from the front.

 Additional Operations:

– front(): Get the front element without removing it.

– rear(): Get the last element in the queue.

– isEmpty(): Check if the queue is empty.

– isFull(): Check if the queue is full (for a fixed-size

11/06/2025 queue). Data Structures and Algorithms in C++ 11

 Queue Representation
 Queue using an Array

#define MAX 100

int queue[MAX], front = -1, rear = -1;
void enqueue(int x) {
if (rear == MAX - 1) return; // Queue Overflow
if (front == -1) front = 0;
queue[++rear] = x;
}
void dequeue() {
if (front == -1 || front > rear) return; // Queue Underflow
front++;
}

11/06/2025 Data Structures and Algorithms in C++ 12

 Queue Representation
 Queue using Linked List

11/06/2025 Data Structures and Algorithms in C++ 13

 Types of Queues
 Simple Queue - Follows FIFO, elements are added at the
rear and removed from the front.
 Circular Queue - The last position is connected to the first
position to form a circle.
 Deque (Double-ended Queue) - Elements can be inserted
and deleted from both ends.
 Priority Queue - Elements are dequeued based on priority
instead of order.

11/06/2025 Data Structures and Algorithms in C++ 14

 Advantages & Disadvantages of
Queue
 Advantages:
– Efficient O(1) time complexity for enqueue and dequeue.

– Used in scheduling and real-time processing.

 Disadvantages:
– Fixed size in array implementation can cause overflow.

– Requires more memory in linked list implementation.

11/06/2025 Data Structures and Algorithms in C++ 15

 Applications of Queue
 CPU Scheduling (Process scheduling in operating systems)

 Task Scheduling (Printing jobs, network packets).

 Handling Requests (Customer service call handling).

 Breadth-First Search (BFS) in Graphs.

 Data Buffering (Streaming, keyboard buffering).

11/06/2025 Data Structures and Algorithms in C++ 16

 Queue in Real-Life Applications

 Operating Systems: CPU job scheduling uses a queue.

 Printers: Print jobs are handled in order.

 Call Centers: First caller is served first.

 Data Streaming: Video buffering uses a queue.

11/06/2025 Data Structures and Algorithms in C++ 17

 Summary
Stack Queue
Principle LIFO FIFO
Primary Push & Pop Enqueue & Dequeue.
operations
Used in Recursion, undo Scheduling, networking,
operations, function buffering, and graph
calls. traversal
Implementatio Array & Linked List. Array & Linked List.
ns
Types Simple Queue, Circular
Queue, Deque, Priority
Queue

11/06/2025 Data Structures and Algorithms in C++ 18

 Introduction to STL Stack
 STL stand for Standard Template Library
 Stack is a LIFO (Last In, First Out) data structure.
 STL provides a ready-to-use stack container in <stack>
header.
 Supports constant time (O(1)) push and pop operations.

11/06/2025 Data Structures and Algorithms in C++ 19

 Stack Declaration & Initialization
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> myStack; // Declaring a stack of integers
return 0;
}

 stack<int> → Declares a stack of integers.

 Uses deque (default), vector, or list as an underlying
container.

11/06/2025 Data Structures and Algorithms in C++ 20

 Common Stack Operations

Operation Function
Push (Insert) push(value)
Pop (Remove) pop()
Top Element top()
Check if Empty empty()
Stack Size size()

11/06/2025 Data Structures and Algorithms in C++ 21

 Pushing and Popping
stack<int> myStack;
[Link](10); // Push 10 onto the stack
[Link](20); // Push 20
[Link](); // Remove the top element (20)

11/06/2025 Data Structures and Algorithms in C++ 22

 Accessing the Top Element
if (![Link]())
cout << "Top element: " << [Link]();
//Traversing a Stack

while (![Link]()) {
cout << [Link]() << " ";
[Link]();
}

11/06/2025 Data Structures and Algorithms in C++ 23

 Advantages & Disadvantages of STL
Stack

 Advantages:

– Simple and efficient O(1) insertion & deletion.

– No manual memory management required.

 Disadvantages:

– No random access (Only top element can be accessed).

– Limited operations compared to other containers.

11/06/2025 Data Structures and Algorithms in C++ 24

 Introduction to STL Queue
 Queue is a FIFO (First In, First Out) data structure.
 STL provides a built-in queue container in the
<queue> header.
 Insertion (push()) happens at the rear and
deletion (pop()) occurs at the front.
 Used in task scheduling, buffering, and real-time
processing.

11/06/2025 Data Structures and Algorithms in C++ 25

 Declaring a Queue in C++ STL
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> myQueue; // Declaring a queue of integers
return 0;
}
 queue<int> → Creates an integer queue.
 Other data types can be used (queue<string>, queue<float>,
etc.).

11/06/2025 Data Structures and Algorithms in C++ 26

 Common Queue Operations

Operation Function
Insert (Enqueue) push(value)
Remove (Dequeue) pop()
Get Front Element front()
Get Rear Element back()
Check if Empty empty()
Get Queue Size size()

11/06/2025 Data Structures and Algorithms in C++ 27

 Enqueue and Dequeue Operations
 queue<int> myQueue;
 [Link](10); // Queue: [10]
 [Link](20); // Queue: [10, 20]
 [Link](30); // Queue: [10, 20, 30]
 [Link](); // Removes 10 → Queue: [20, 30]

11/06/2025 Data Structures and Algorithms in C++ 28

 Accessing Front and Rear Elements
 cout << "Front: " << [Link](); // 20
 cout << "Rear: " << [Link](); // 30

 front() → Returns the first element in the

 [Link]() → Returns the last element in the queue.

11/06/2025 Data Structures and Algorithms in C++ 29

 Traversing a Queue
while (![Link]()) {
cout << [Link]() << " ";
[Link]();
}

 Note: pop() removes elements, so the queue becomes

empty after traversal.

11/06/2025 Data Structures and Algorithms in C++ 30

 Advantages & Disadvantages of STL
Queue
 Advantages:

– Simple and efficient O(1) enqueue and dequeue operations.

– No manual memory management.

 Disadvantages:

– No random access (Only front and back elements can be accessed).

– Limited operations compared to other containers like vector or list.

11/06/2025 Data Structures and Algorithms in C++ 31

 Queue vs. Stack in STL

Feature queue (FIFO) stack (LIFO)

Order First In, First Out Last In, First Out
Access Only Front & Rear Only Top Element
Operations Enqueue, Dequeue Push, Pop, Top
Example Task Scheduling Undo Feature

11/06/2025 Data Structures and Algorithms in C++ 32

 Summary
 Stack
 Queue
 STL in stack
 STL in Queue

11/06/2025 Data Structures and Algorithms in C++ 33