Data Structures &
Algorithms
Lecture – 10
Applications of Stack and Queue
M Abrar Saddique
Applications of STACK
Stacks have a wide range of applications in computer
science and programming. Here are some common uses:
Function Call Management: Stacks manage function calls
in programming languages. When a function is called, its
context (like local variables and return address) is pushed
onto the stack. When the function completes, this
context is popped off the stack.
Example: When a program calls a function, the
current state (including local variables and the return
address) is pushed onto the call stack. When the function
returns, the state is popped, allowing the program to
continue from where it left off.
Expression Evaluation: Stacks are used to evaluate
expressions, especially in converting between different
notations (infix, postfix, and prefix).
Example: Converting an infix expression (like 3 + 5) to postfix
expression (like 3 5 +) can be done using a stack. The algorithm uses
the stack to temporarily hold operators until they are needed, ensuring
the correct order of operations.
Backtracking Algorithms: Many algorithms, such as
depth-first search (DFS), use stacks to remember
previous states or decisions, allowing the algorithm
to backtrack when necessary.
Example: In solving a maze, a depth-first search (DFS)
algorithm can use a stack to remember the current path. If
the algorithm hits a dead end, it pops from the stack to
backtrack to the last decision point and explore alternative
paths.
Undo Mechanisms: In applications like text editors,
stacks can store the history of actions. When the user
wants to undo an action, the last action is popped
from the stack and reversed.
Example: In a text editor, each change (like adding or
deleting text) can be pushed onto a stack. When the user
selects "undo," the last change is popped from the stack and
reversed.
Memory Management: Stacks can help manage
memory in certain contexts, especially with variable
allocation and deallocation during function calls.
Browser Navigation: Browsers use stacks to manage
the history of visited pages, allowing users to
navigate back to previously viewed pages.
Example: When you navigate to a new web page, the
URL is pushed onto a stack. Pressing the "back" button pops
the last URL off the stack, allowing you to return to the
previous page.
Syntax Checking: Stacks are used in parsing
expressions to ensure that parentheses and other
delimiters are properly nested and matched.
Example: A compiler can use a stack to check for
balanced parentheses in an expression. Each opening
parenthesis is pushed onto the stack, and each closing
parenthesis pops an opening one. If the stack is empty at the
end, the parentheses are balanced.
Game Development: In game programming, stacks
can be used to manage states, such as keeping track
of levels or player moves.
Example: In a turn-based strategy game, a stack can be
used to manage the history of player moves. If a player wants
to undo their last move, the game can pop the last action
from the stack and revert the game state.
Data Serialization: Stacks can help with converting
complex data structures into a serialized format for
storage or transmission.
Example: When serializing a tree structure (like a file
directory), a stack can help traverse the tree in a depth-first
manner, ensuring that all nodes are visited and stored in the
correct order.
Applications of Queue
Print Queue: In a printer system, print jobs are
managed in a queue. The first job sent to the printer
is the first one printed, ensuring a fair and orderly
processing of requests.
Task Scheduling: Operating systems use
queues to manage processes and tasks. Jobs
waiting to be processed can be placed in a
queue, and the scheduler can handle them in
the order they arrive.
Customer Service Systems: Queues are often
used in customer service applications, such as
call centers or help desks, where customers
are served in the order they arrive.
Breadth-First Search (BFS): In graph traversal,
BFS uses a queue to explore nodes level by
level. Nodes are enqueued as they are
discovered and dequeued as they are
explored.
Buffering: Queues are used in buffering
scenarios, such as in streaming applications or
network communication, where data packets
are queued for processing or transmission.
Order Processing: In e-commerce systems,
orders can be managed in a queue to ensure
they are processed in the order they are
received.
Event Handling: GUI applications often use
event queues to manage user inputs and
system events. Events are processed in the
order they occur.
Simulation: Queues are used in simulations to
model systems where entities wait in line for
resources, such as customers at a bank or cars
at a toll booth.
