DS - UNIT 4 - Stack and Queue Study Material(BCA and BSC II semester GFGCWJ/KSWU)

 STACK 

✔ Basic Concepts        

    The piece/Item/Element added to a stack will be the first one Removed/withdrawn from the STACK since stacks are linear data structures that adhere to the Last-In-First-Out (LIFO) concept. 

    The two major operations are push, which adds an element to the top of the stack and pop, which removes the top element from the stack.

✔ Characteristics:

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

Top: The top element is the one that was added most recently.

Bottom: The bottom element is the one that was added least recently.

Size: Stacks have a limited size or capacity.

✔ Representation of Stacks:

There are various ways to implement stacks:

Array Representation: Using a fixed-size array to hold the stack elements. This has a limitation on size.

Linked List Representation: Using a linked list where each node points to the node below it. This can be more flexible in size.

✔ Operations on Stacks:

Push: Add an element to the top of the stack.(Like putting plate in to the bucket or box is same as PUSH operation)

Pop: Remove and return the top element from the stack.(Like taking or removing plate from the bucket or box is same as POP operation)

Peek (Top): Return the top element without removing it.

isEmpty: Check if the stack is empty.

isFull : Check if the stack is full (only relevant in array-based implementation).

✔ Applications of Stacks:

👉 Function Calls: Stacks are used to keep track of function calls and their local variables.

👉 Expression Evaluation: Stacks are used to convert infix expressions to postfix and evaluate postfix expressions.

👉 Undo Functionality: Stacks can be used to implement undo functionality in software applications.

👉 Backtracking: Stacks are used in algorithms that involve backtracking, like depth-first search in graphs.

👉 Infix, Postfix, and Prefix Notations:

★ Infix: Operators are written between the operands. e.g., A + B.

★ Postfix (Reverse Polish Notation): Operators are written after the operands. e.g., A B +.

★ Prefix (Polish Notation): Operators are written before the operands. e.g., + A B.

✅ Conversion from Infix to Postfix using Stack:

    The STACK is commonly used to convert infix expressions to postfix expressions. Two stacks are used, one for operators and the other for the output expression.

* Evaluation of Postfix Expression using Stack:

Postfix expressions are easy to evaluate using a stack. Scan the expression from left to right. When an operand is encountered, push it onto the stack. Pop the necessary number of operands from the stack when an operator is encountered, carry out the operation, and then push the outcome back into the stack.

Examples : 

1.    Infix  = AXB+C/D-EXF+G       

       Postfix Solution =   ABXCD/+EFXG+-   

2.    Infix  =  we will update soon......

      Postfix Solution = 

✅  Conversion from Infix to Prefix using Stack:

✅  Conversion from Infix to Prefix using Stack:

Application of Stack in Function Calls:

When a function is called, its return address and local variables are stored in a stack frame. This allows for nested function calls and proper execution order.

Queues:

✔ Basic Concepts:

A queue is another linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added to the queue will be the first one to be removed. It can be thought of as a line of elements waiting to be processed.

✔ Characteristics:

👉 FIFO: The first element added is the first one to be removed.

👉 Front: The front of the queue is where elements are removed.

👉 Rear: The rear of the queue is where elements are added.

👉 Size: Queues have a limited size or capacity.

✔ Representation of Queues:

Similar to stacks, there are different ways to implement queues:

✅ Array: Using a fixed-size array to hold the queue elements.

✅ Linked List: Using a linked list where each node points to the next node.

✔ Types of Queues:

★  Simple Queue: The basic form of a queue, with elements added at the rear and removed from the front.

★  Circular Queue: A variation of the simple queue where the rear "wraps around" to the front when it reaches the end of the array.

★  Double Ended Queue (Deque): Allows elements to be added and removed from both the front and rear.

★  Priority Queue: Elements have a priority associated with them, and the element with the highest priority is removed first.

✔ Operations on Simple Queues:

👉 Enqueue: Add an element to the rear of the queue.

👉 Dequeue: Remove and return the front element from the queue.

👉 Front: Return the front element without removing it.

👉 Rear: Return the rear element without removing it.

👉 isEmpty: Check if the queue is empty.

👉 isFull: Check if the queue is full (only relevant in array-based implementation).

✔ FAQs (Frequently Asked Questions):

Q: Why do we need both stacks and queues?

A: Stacks and queues serve different purposes. Queues are utilized in situations like handling tasks in a printer spooler, whereas stacks are used for activities like maintaining function call hierarchies.

Q: How is a circular queue different from a simple queue?

A: A circular queue "wraps around" when reaching its end, so the rear can become the front. This allows efficient use of space in some cases.

Q: What's the significance of converting infix to postfix?

A: Postfix notation eliminates the need for parentheses in expressions and simplifies the process of evaluation by eliminating operator precedence concerns.

Q: Why do we use a priority queue?

A: Priority queues are used when elements have varying levels of urgency or importance, like in scheduling tasks or processing events with different priorities.

Q: Can a stack or queue be implemented using each other?

A: Yes, you can implement a stack using two queues and vice versa. Although the implementation specifics may differ, it shows how adaptable these data structures are.

         Stacks follow the LIFO principle and are used in function calls and expression evaluation. Queues are effective in situations like task scheduling and managing resources with different priorities since they adhere to the FIFO principle.

 Effective programming and problem-solving depend on an understanding of STACK and QUEUE ideas.