Data Structures Unit 2 Notes

Unit 2 Syllabus Topics

• Stack as ADT
• Different implementation of Stack
• Multiple Stack
• Infix to Postfix Conversion using Stack
• Evaluation of Postfix Expression
• Recursion
• Queue as ADT
• Different implementation of Queue
• Circular Queue
• DQueue or Double Ended Queue
• Priority Queue
• Queue Simulation
• Applications of Queue

Introduction to Unit 2

Data Structures Unit 2 mainly focuses on two very important linear data structures: Stack and Queue. A linear data structure stores data elements in a sequence. Stack and Queue are special because they follow strict rules for insertion and deletion. These rules make them useful in programming, operating systems, compilers, memory management and real-life simulation problems.

A stack works on the principle of LIFO, which means Last In First Out. The element inserted last is removed first. A queue works on the principle of FIFO, which means First In First Out. The element inserted first is removed first. Recursion is also related to stack because every recursive function call is stored in the system stack until the base condition is reached.

Stack as Abstract Data Type

A stack is an ordered collection of elements in which insertion and deletion are performed only from one end called TOP. Abstract Data Type means we focus on what operations are performed, not how they are internally implemented. In stack ADT, the main operations are push, pop, peek and display.

Basic Stack Operations

• Push: Insert an element into the stack.
• Pop: Delete the top element from the stack.
• Peek: Return the top element without deleting it.
• IsEmpty: Check whether the stack is empty.
• IsFull: Check whether the stack is full in array implementation.

Stack Representation

Here 40 is at the top, so it will be removed first. This is why stack follows Last In First Out.

Push Algorithm

Overflow occurs when we try to insert an element into a full stack. In array-based stack, maximum size is fixed, so overflow must be checked before insertion.

Pop Algorithm

Underflow occurs when we try to delete an element from an empty stack. This is a common condition that must be written in exam algorithms.

Implementation of Stack

Stack can be implemented using array and linked list. Array implementation is simple but has fixed size. Linked list implementation is dynamic because memory is allocated at runtime.

Multiple Stack

Multiple stack means maintaining more than one stack in a single array. This is done to use memory efficiently. The most common example is two stacks in one array, where one stack grows from left to right and the other grows from right to left.

Overflow occurs only when TOP1 + 1 equals TOP2. This method reduces wastage of array space.

Infix to Postfix Conversion

Infix expression is the normal mathematical expression in which operator is written between operands, such as A+B. Postfix expression is the expression in which operator is written after operands, such as AB+. Computers prefer postfix expression because it can be evaluated easily using stack without brackets and operator precedence confusion.

Operator Precedence

• Highest: ^
• Medium: *, /, %
• Lowest: +, -

Algorithm

Example

Convert A + B * C into postfix.

Multiplication has higher precedence than addition, so B*C is performed first. Therefore the postfix expression becomes ABC*+.

Evaluation of Postfix Expression

Postfix expression is evaluated using stack. When an operand is found, it is pushed into the stack. When an operator is found, required operands are popped from the stack, operation is performed and result is pushed back.

Algorithm

Example

Evaluate postfix expression: 23*54*+

Recursion

Recursion is a programming technique in which a function calls itself directly or indirectly. Every recursive function must have a base condition. Without a base condition, recursion continues infinitely and causes stack overflow.

Parts of Recursion

• Base Case: Condition where recursion stops.
• Recursive Case: Function calls itself with a smaller problem.

Factorial Example

For factorial(5), the calls are factorial(5), factorial(4), factorial(3), factorial(2), factorial(1), factorial(0). After reaching the base case, the values return back one by one.

Advantages and Disadvantages

Recursion makes code short and easy for problems like tree traversal, factorial and Fibonacci series. However, it uses extra memory because each function call is stored in stack. It may be slower than iteration for simple problems.

Queue as Abstract Data Type

A queue is a linear data structure in which insertion is performed from the rear end and deletion is performed from the front end. It follows First In First Out order. A real-life example is a ticket counter line where the person who comes first gets service first.

Queue Operations

• Enqueue: Insert an element at rear.
• Dequeue: Delete an element from front.
• Front: View first element.
• Rear: View last element.
• IsEmpty: Check empty queue.
• IsFull: Check full queue.

Queue Diagram

Enqueue Algorithm

Dequeue Algorithm

Circular Queue, Dequeue and Priority Queue

Circular Queue

A circular queue is an improved version of linear queue in which the last position is connected back to the first position. It solves memory wastage problem of simple queue. In circular queue, rear and front move in circular manner using modulo operation.

Double Ended Queue

Dequeue or Double Ended Queue allows insertion and deletion from both front and rear ends. It is more flexible than a simple queue. Input restricted dequeue allows insertion at one end but deletion from both ends. Output restricted dequeue allows deletion at one end but insertion from both ends.

Priority Queue

A priority queue is a special queue where each element has a priority. The element with highest priority is served before lower priority elements. If two elements have same priority, FIFO rule may be followed.

Priority queues are used in CPU scheduling, printer scheduling, graph algorithms and emergency service systems.

Applications of Stack and Queue

Important Questions for RGPV Exams

1. Define stack as ADT. Explain push and pop operations with algorithms.
2. Explain array and linked list implementation of stack.
3. Convert an infix expression into postfix using stack.
4. Evaluate a postfix expression using stack with example.
5. Explain recursion with suitable example.
6. What is stack overflow and underflow?
7. Define queue as ADT and explain enqueue and dequeue operations.
8. Differentiate between stack and queue.
9. Explain circular queue with algorithm.
10. Explain double ended queue and its types.
11. What is priority queue? Explain its applications.
12. Explain applications of queue in computer science.

PYQ Analysis and Topic Weightage

Related Data Structure Units

Previous: Unit 1 Next: Unit 3