Data Structures And Algorithms

Tutorial Five:
Arrays (CONT’D)
Sequential Stacks and Queues
Lecture Instructors :
Prof. Dr. Ahmed El Nahas Prof. Dr. Amira Youssef

Tutorial Instructors:
Eng. Ahmed Abdelhamid Waheed Abdelwahab Eng. Mohamed Essam
Eng. Ahmed Ashraf Eng. Aya Salah Eng. Tamim Sherif
1
 Exercises(1)
1. a) Describe how the following sparse matrix may be stored using
coordinates method, assume 1-based indexing and the maximum
number of elements is assumed to be 9.
b) What is the percentage of reduction in memory following the
representation above?
0.0 6.6 0.0 0.0 0.0 0.0 0.0 0.0
7.7 0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 3.3 0.0 4.4 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 2.2 1.1

2
 Solution(a)
2-D array  2 coordinate arrays
1 value (V) array
Value of top is 6
1 2 3 4 5 6 7 8 9
Row 1 2 4 4 6 6

1 2 3 4 5 6 7 8 9
Column 2 1 3 5 7 8

1 2 3 4 5 6 7 8 9
V 6.6 7.7 3.3 4.4 2.2 1.1
3
 Solution(b)
Number of cells if represented using as 2-D Array = number of rows
x number of columns = 6 x 8 = 48
Number of cells if represented using coordinates three vectors
method (ignoring Top) = max x 3 = 9 x 3 = 27
Percentage reduction = (48 - 27)/48 * 100 = 43.75%

4
Quick Review: Stack

5
Quick Review: Sequential Stacks

6
Quick Review: Operations on Stack

7
Quick Review: Representation of a Stack with Array

8
Quick Review: Representation of a Stack with Array

9
 Exercises(2)
2. Given an empty stack initially. Show the content of the stack and
the top of stack after carrying out the following sequence of
operations. Clearly show your steps.
a) Push(7)
b) Push(8)
c) Push(9)
d) Push(6)
e) Pop()
f) Pop()
g) Push(20)

10
 Solution
a) Initially
max
.
.
5
4
3
2
1
Top

11
 Solution
a) Push(7)
max
.
.
5
4
3
2
Top 1 7

12
 Solution
b) Push(8)
max
.
.
5
4
3
Top 2 8
1 7

13
 Solution
c) Push(9)
max
.
.
5
4
Top 3 9
2 8
1 7

14
 Solution
d) Push(6)
max
.
.
5
Top 4 6
3 9
2 8
1 7

15
 Solution
e) Pop()
max
.
.
5
4
Top 3 9
2 8
1 7

16
 Solution
f) Pop()
max
.
.
5
4
3
Top 2 8
1 7

17
 Solution
f) Push(20)
max
.
.
5
4
Top 3 20
2 8
1 7

18
 Exercises(3)
3. A stack is represented using am array as shown.
A field “top” is used to keep track of the top
element in the stack, and two flags “overflow”
and “underflow” to record the existence of
overflow or underflow errors occurring in any
operation.
a) Give the algorithm for pushing an item x in the stack.
b) Give the algorithm for popping top of stack and
storing it in variable x.

19
Solution(a)

20
Solution(b)

21
Quick Review: Queues

22
Quick Review: Sequential Queues Implementation

23
Quick Review: Sequential Queues Representation

24
Quick Review: Sequential Queues Operations

25
Quick Review: Sequential Queues using Sequential
Arrays Dilemma

26
Quick Review: Sequential Queues Representation
using Circular Arrays

27
Quick Review: Sequential Queues using Circular
Arrays Implementation

28
Quick Review: Sequential Queues using Circular
Arrays Implementation

29
Quick Review: Sequential Queues using Circular
Arrays Implementation

30
Quick Review: Sequential Queues using Circular
Arrays Implementation

31
 Exercises(4)
4. Using a sequential circular implementation for an initially empty
queue with length 4, illustrate the result of each operation in the
sequence mentioned. Assume that you are keeping an extra count
variable to keep the number of items in the queue. Clearly show the
front and rear pointers, and the count variable in the initial step
and after each operation.
 Enqueue(4)
 Enqueue(1)
 Enqueue(3)
 Enqueue(7)
 Dequeue(),
 Enqueue(8)
 Dequeue()

32
 Solution
Initially Front
Q[4]
Rear
count = 0 Q[3]
Q[2]
Q[1]

33
 Solution
Enqueue(4)
Q[4]
Front
count = 1 Q[3]
Q[2]
Rear Q[1] 4

34
 Solution
Enqueue(1)
Q[4]
Front
count = 2 Q[3]
Rear Q[2] 1
Q[1] 4

35
 Solution
Enqueue(3)
Q[4]
Front
count = 3 Rear Q[3] 3
Q[2] 1
Q[1] 4

36
 Solution
Enqueue(7) Front Q[4] 7
Rear
count = 4 Q[3] 3
Q[2] 1
Q[1] 4

37
 Solution
Dequeue() Rear Q[4] 7
count = 3 Q[3] 3
Q[2] 1
Front Q[1]

38
 Solution
Enqueue(8)
Q[4] 7
count = 4 Q[3] 3
Q[2] 1
Rear Q[1] 8
Front

39
 Solution
Dequeue()
Q[4] 7
count = 3 Q[3] 3
Front Q[2]
Q[1] 8
Rear

40
 Exercises(5)
5. Using a sequential circular implementation for an initially empty
queue with length 4, illustrate the result of each operation in the
sequence mentioned. Assume that you don’t allow the last entry to
be filled in order to handle the overflow-underflow problem. Clearly
show the front and rear pointers in the initial step and after each
operation.
 Enqueue(4)
 Enqueue(1)
 Enqueue(3)
 Dequeue(),
 Enqueue(8)
 Dequeue()

41
 Solution
Initially Front
Q[4]
Rear
Q[3]
Q[2]
Q[1]

42
 Solution
Enqueue(4)
Q[4]
Front
Q[3]
Q[2]
Rear Q[1] 4

43
 Solution
Enqueue(1)
Q[4]
Front
Q[3]
Rear Q[2] 1
Q[1] 4

44
 Solution
Enqueue(3)
Q[4]
Front
Rear Q[3] 3
Q[2] 1
Q[1] 4

45
 Solution
Dequeue()
Q[4]
Rear Q[3] 3
Q[2] 1
Front Q[1]

46
 Solution
Enqueue(8)
Rear Q[4] 8
Q[3] 3
Q[2] 1
Q[1]
Front

47
 Solution
Dequeue() Rear Q[4] 8
Q[3] 3
Front Q[2]
Q[1]

48
 Exercises(6)
6. Suppose in exercise(2) in the forth operation we performed an
enqueue(9) instead of dequeue(), what will be the output in this
case.

49
 Solution
Overflow since ( R mod max ) + 1 = F in this case.
R=3
F=4

50
 Exercises(7)
7. A queue is represented using a circular array as shown. A field
“count” is used to keep track of the number of items in the queue,
and two flags “overflow” and “underflow” to record the existence
of overflow or underflow errors occurring in any operation.
a) Give the algorithm for inserting an item x in the queue.
b) Give the algorithm for removing an item from the queue and storing it in
variable x.

51
Solution(a)

52
Solution(b)

53
 Exercises(8)
8. A queue is represented using a circular array as shown. Two flags
“overflow” and “underflow” are used to record the existence of
overflow or underflow errors occurring in any operation.
a) Give the algorithm for inserting an item x in the queue.
b) Give the algorithm for removing an item from the queue and storing it in
variable x.

54
Solution(a)

55
Solution(b)

56
 Exercises(09)
9. Describe the type of errors that may occur in performing pop or
push operations on a stack.

57
Solution

58
 Exercises(10)
10. Describe the type of errors that may occur in performing en-queue
or de-queue operations on a queue.

59
Solution

60