Scribd
Upload
7 views1 page

Data Structures: Stacks and Queues Guide

The document provides an answer sheet for a Data Structures worksheet, detailing the characteristics and applications of stacks and queues. It includes examples of stack operations, queue state changes, and conditions for stack overflow and circular queue status. The document concludes with a total score of 40 marks for the worksheet.

Uploaded by

Ethan-Dale Brown
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views1 page

Data Structures: Stacks and Queues Guide

The document provides an answer sheet for a Data Structures worksheet, detailing the characteristics and applications of stacks and queues. It includes examples of stack operations, queue state changes, and conditions for stack overflow and circular queue status. The document concludes with a total score of 40 marks for the worksheet.

Uploaded by

Ethan-Dale Brown
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures Worksheet — Answer Sheet

1. When writing an algorithm to convert a decimal number to binary, the best data structure to use
is a stack.

2. A stack is defined as a data structure in which elements are added and removed in a Last
In, First Out (LIFO) order.

3. A queue is defined as a data structure in which elements are added at the rear and removed
from the front (FIFO order).

4. Two computerized applications/uses of queues:


1. Print spooling in an operating system
2. CPU process scheduling

5. Two computerized applications/uses of stacks:


1. Undo and redo operations in text editors
2. Expression evaluation (e.g., converting infix to postfix)

6. The output of the algorithm when expr = 923*82/+− is 9.

The stack on each iteration of the for loop is shown below:


Iteration Stack contents (top at right)
1 9
2 9, 2
3 9, 6 (2 * 3 = 6)
4 9, 6, 8
5 9, 6, 8, 2
6 9, 6, 4 (8 / 2 = 4)
7 9, 10 (6 + 4 = 10)
8 -1 (9 - 10 = -1)
9 (Final stack has one element)

7. The stack overflow condition occurs when the stack is full and a push operation is attempted.

8. Given a simple queue q with the head containing B:


a. After dequeue(B), dequeue(E), enqueue(C), enqueue(A): q = [C, A]
b. After dequeue(E), dequeue(A), enqueue(A), enqueue(C): q = [A, C]

9. Circular queue operations result:


After performing enqueue(L), enqueue(Q), dequeue(L), dequeue(L), dequeue(Q), enqueue(E),
enqueue(Z):
Final queue state (Head and Tail indicated):
Index 0 1 2 3 4 5 6 7 8 9 10
Queue Y L Q M O C R L E Z
Head → 2
Tail → 10

10. For the circular queue:


a. Q is full when (tail + 1) % size == head.
b. Q is empty when head == tail.

Total: 40 marks

You might also like