PLDS
UNIT 5
1. Define STACK
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.
Elements are added and removed only from the top of the stack. Think of it as a stack of
plates where you can only take the top plate off the stack or add a plate to the top.
2. Define QUEUE
A queue is a linear data structure that follows the First In, First Out (FIFO) principle.
Elements are added at the rear (end) and removed from the front (beginning). It's like a line
of people waiting for a service where the first person in line is the first to be served.
3. Differentiate STACK and QUEUE
Order of Operations:
o Stack: LIFO (Last In, First Out)
o Queue: FIFO (First In, First Out)
Insertion/Deletion:
o Stack: Insertion and deletion are done at the top.
o Queue: Insertion is done at the rear and deletion is done from the front.
Real-life Example:
o Stack: A stack of books.
o Queue: A line at a ticket counter.
o
4. List the applications of STACK
Expression evaluation (e.g., converting infix to postfix)
Undo mechanisms in text editors
Backtracking algorithms (e.g., solving mazes)
Function call management in recursion
5. List the applications of QUEUE
Managing tasks in a printer queue
Handling requests in web servers
Breadth-First Search (BFS) in graph traversal
CPU scheduling
6 Write a C code to check “STACK Overflow”
7 Write a code to check STACK underflow
8 Write a code for QUEUE EMPTY
9 Write a code for QUEUE FULL
10. Convert the following infix expression into postfix form
(A+B)(C+D)(E^F)
11. What are Enqueue and Dequeue operations in QUEUE
Enqueue: Adding an element to the end (rear) of the queue.
Dequeue: Removing an element from the front of the queue.
12. What is stack? Why it is known as LIFO? Write algorithm of PUSH and
POP operation on stack.
A stack is a data structure that follows the Last In, First Out (LIFO) principle. This means
that the last element added (pushed) onto the stack is the first one to be removed (popped).
It's called LIFO because the most recently added item is the first one to be removed.
Algorithm for PUSH operation:
1. Check if the stack is full.
2. If full, print "Stack Overflow" and exit.
3. If not full, increment the top and add the new element to the top of the stack.
Algorithm for POP operation:
1. Check if the stack is empty.
2. If empty, print "Stack Underflow" and exit.
3. If not empty, remove the element from the top and decrement the top.
13. What is queue? Why it is known as FIFO? Write an algorithm to insert
and delete an element from a simple queue
A queue is a data structure that follows the First In, First Out (FIFO) principle. This means
the first element added to the queue is the first one to be removed. It's called FIFO because
the oldest added item is the first one to be removed.
Algorithm to insert (Enqueue):
1. Check if the queue is full.
2. If full, print "Queue Full" and exit.
3. If empty, set the front to 0.
4. Increment the rear and add the new element to the rear of the queue.
Algorithm to delete (Dequeue):
1. Check if the queue is empty.
2. If empty, print "Queue Empty" and exit.
3. If not empty, remove the element from the front and increment the front.
14. Explain in detail about STACK operations with an example
Stack operations include:
Push: Adding an element to the top of the stack.
Pop: Removing the top element from the stack.
Peek/Top: Viewing the top element without removing it.
IsEmpty: Checking if the stack is empty.
IsFull: Checking if the stack is full.
15. Explain in details about QUEUE operations with an example
Queue operations include:
Enqueue: Adding an element to the end of the queue.
Dequeue: Removing the front element from the queue.
IsEmpty: Checking if the queue is empty.
IsFull: Checking if the queue is full.
Front: Viewing the front element without removing it.
16. Applications of Stack with Examples
1. Browser Navigation:
o Back and Forward Navigation: Web browsers use a stack to manage the
history of visited pages. Each new page is pushed onto the stack. When you
click the back button, the current page is popped off, and you are taken to the
previous page.
Example: If you visit pages in the sequence A -> B -> C -> D, and
then click the back button twice, pages C and B will be popped off the
stack, and you'll be back at page A.
2. Undo and Redo Functionality:
o Text Editors: Applications like Microsoft Word, Google Docs, and code
editors use stacks to manage the undo and redo operations. Each action (like
typing or deleting) is pushed onto an undo stack, allowing users to revert
actions by popping them off.
Example: Typing the sequence "abc" followed by "d" and then
pressing undo will remove "d", leaving "abc".
3. Call History in Phones:
Management of Call History: Your phone uses a stack to manage your call history.
The most recent call is on top of the stack, and when you make a new call, it gets
pushed onto the stack.
o Example: If your last three calls were to Alice, Bob, and Charlie, with Charlie
being the most recent, the call stack would be [Alice, Bob, Charlie]. Making a
new call to Dave would push it to [Alice, Bob, Charlie, Dave].
4. Plate Dispenser in Cafeterias:
Real-life Example of Stack: A plate dispenser where plates are stacked one on top of
another. You always take the top plate, which is the last one added.
o Example: If plates are added in the order 1, 2, 3, the first plate to be taken is
plate 3, followed by plate 2, then plate 1.
5. Reversing a Word:
Using Stack to Reverse a Word: Push each letter of the word onto the stack, and
then pop them off to get the word in reverse order.
o Example: For the word "hello", pushing each letter onto a stack gives [h, e, l,
l, o]. Popping them off gives "olleh".
17. Explain STACK implementation using Array Concept with code
19. Construct QUEUE ADT using Array.
18 Write a code to implement STACK using List
20.Explain QUEUE implementation using List
