Data Structure

DS Theory Assignment 02: 5 Scenario-Based Problems on Stack, Queue, Priority Queue, and Deque

By 5 Mins Read

Data Structures Assignment: 02

5 Scenario-Based Problems Using Linear Data Structures (Stack, Infix to Postfix, Circular Queue, Priority Queue, Deque)

Introduction to Linear Data Structures

Data structures are essential for organizing and managing data efficiently in computer programs. Among the different types of data structures, Linear Data Structures play a critical role in solving real-world computing problems.

Linear data structures store elements sequentially, meaning each element is connected to the previous and next element in a single line. Examples include:

  • Stack

  • Queue

  • Circular Queue

  • Priority Queue

  • Double Ended Queue (Deque)

In academic courses such as Data Structures, students are often evaluated using scenario-based problems to test their ability to apply theoretical concepts in real-world situations.

This blog presents a scenario-based assignment designed for CLO-01: Employ linear data structures to solve computing problems.

The assignment includes five practical scenarios covering important data structures used in software development, operating systems, and real-world applications.

CLO-01:

Employ Linear Data Structures to Solve Computing Problems

Course Learning Outcome (CLO-01) requires students to:

  • Understand linear data structures

  • Identify real-world problems where they can be applied

  • Design algorithms using these structures

  • Implement solutions using programming languages such as C++

The following assignment questions focus on practical scenarios that simulate real computing systems.

Question 01:

Stack (Undo Operation in Text Editor)

Real-World Scenario

Imagine a text editor application similar to Notepad or Microsoft Word. When a user writes text and performs operations like:

  • inserting text

  • deleting text

  • formatting text

the application allows the user to press an Undo button to revert the previous action.

This functionality is implemented using a Stack data structure.

Why Stack is Used?

Stack follows the Last In First Out (LIFO) principle.

This means the most recent action is reversed first, which perfectly matches how an Undo system works.

Example sequence:

Insert Text

Delete Word

Change Font

Undo

Undo

Operations performed by stack:

Action Stack Operation
Insert Text Push
Delete Word Push
Change Font Push
Undo Pop
Undo Pop

Student Tasks

Students must:

  1. Explain how stack supports undo operations

  2. Design an algorithm

  3. Write a C++ program implementing stack

  4. Demonstrate the program output

 

Question 02:

Infix to Postfix Expression Using Stack

Real-World Scenario

Many applications like scientific calculators, compilers, and expression evaluators process mathematical expressions entered by users.

Users write expressions in infix notation, for example:

A + B * C

However, computers process expressions more efficiently in postfix notation.

Example:

ABC*+

Why Postfix is Preferred?

Postfix expressions eliminate the need for:

  • parentheses

  • operator precedence rules during evaluation

This makes evaluation simpler using stack operations.

Example Conversion

Convert the following infix expression to postfix:

(A + B) * (C – D) / E

Expected postfix form:

AB+CD-*E/

Student Tasks

Students must:

  1. Explain the difference between infix and postfix expressions

  2. Show step-by-step stack operations

  3. Draw a diagram for the conversion process

  4. Write a C++ program for infix to postfix conversion

Question 03:

Circular Queue (Printer Job Scheduling)

Real-World Scenario

Consider a computer lab printer system in a university. Multiple students send print jobs to the printer. The printer processes requests one by one, forming a queue.

However, a normal queue wastes memory after several deletions. To solve this problem, systems use a Circular Queue.

What is a Circular Queue?

A circular queue connects the last position of the queue back to the first position, forming a circle.

This allows efficient memory usage.

Example queue size:

Size = 5

Operations:

Insert: P1, P2, P3, P4
Delete: 2 jobs
Insert: P5, P6

Students must track:

  • Front pointer

  • Rear pointer

Student Tasks

Students must:

  1. Explain why circular queue is better than linear queue

  2. Simulate operations step-by-step

  3. Show front and rear positions

  4. Write a C++ program implementing circular queue

Question 04:

Priority Queue (Hospital Emergency System)

Real-World Scenario

In a hospital emergency room, patients are not treated in arrival order. Instead, they are treated based on the severity of their condition.

Example patient list:

Patient Priority
John 2
Sara 5
Ahmed 1
Ali 4

A higher number indicates higher priority.

So the treatment order becomes:

Sara → Ali → John → Ahmed

What is a Priority Queue?

A Priority Queue is a special type of queue where elements are removed based on priority rather than arrival order.

Applications include:

  • Operating system scheduling

  • Emergency services

  • Network packet routing

  • CPU task management

Student Tasks

Students must:

  1. Explain how priority queues manage urgent tasks

  2. Insert patients into the queue

  3. Determine treatment order

  4. Write a C++ program implementing a priority queue

Question 05:

Double-Ended Queue (Deque) for Task Scheduling

Real-World Scenario

Modern web servers and operating systems manage tasks based on urgency.

Some tasks must be executed immediately, while others can wait.

For this purpose, systems use a Double-Ended Queue (Deque).

A deque allows insertion and deletion from both ends.

Example Operations

InsertFront(Task1)
InsertRear(Task2)
InsertFront(Task3)
DeleteRear()
InsertRear(Task4)

Deque state changes during execution.

Why Is Deque Useful?

Deque is widely used in:

  • CPU scheduling

  • Browser history

  • Sliding window algorithms

  • Job scheduling systems

Student Tasks

Students must:

  1. Explain the difference between queue and deque

  2. Perform given operations

  3. Show the state after each step

  4. Write a C++ program implementing deque

 

Submission Requirements for Students

Students must submit the following components:

1. Problem Analysis

Explain the scenario and identify the data structure used.

2. Algorithm

Provide a step-by-step algorithm.

3. Flowchart

Illustrate program logic visually.

4. C++ Implementation

Provide a working C++ program.

5. Output Screenshots

Attach program execution results.

Learning Outcomes of This Assignment

By completing this assignment, students will:

  • Understand real-world applications of linear data structures

  • Improve problem-solving skills

  • Learn how to implement stack and queue structures in C++

  • Understand how data structures are used in software systems

Conclusion

Linear data structures are fundamental building blocks in computer science and software engineering. Through real-world scenarios such as undo operations, calculator expression evaluation, printer scheduling, hospital management systems, and server task management, students gain practical experience applying these structures.

Assignments like this help bridge the gap between theoretical learning and real-world computing problems, preparing students for advanced programming and system design.

Author

Related Posts

Write A Comment