Question

1. Write a set of routines for implementing several stacks and queues within a single array. Hint: Look at the lecture material on the hybrid implementation.

Answer 1

Answer:

Out of the two methods The 2nd method is a better option for implementing several stacks and arrays using the single array system this is because Method 2 makes efficient use of the available space

Explanation:

A) Method 1 ( Divide the given single array in the size of n/k.)

• How to use method 1 to implement several stacks involves :

i)  To implement several stacks through an array (x) is by dividing the array in n/k parts.

ii) The k represents the slots in which the different stacks will be placed and the n represents the size of the array x.

iii) If you need to implement at least two stacks place the first stack in the slot of a [0] to a [n/k - 1], and another stack in the slot of a[n/k] to a[2n/k-1].

note: The  disadvantage of this method is that the use of the space of the array is not much efficient. therefore method 2 is better

• How to use method 1 to implement queues involves :

i) queues can also be implemented through an array. applying the same method above

ii) Divide the array in slots and place the queues in that slots.

This method has a problem with  the efficient utilization of the space.therefore method 2 is preferred

B) Method 2 ( uses the space efficiently ) uses two more arrays to implement stacks which are : Top_array and Next_array

• how to use method 2 to implement several stacks

i) Store the indexes of the next item that will also be stored in all stacks in this initial stack

ii)The initial actual array is x[] and this will store the stacks.

iii)Simultaneously with several stacks, the stack which contain the free slots in the array x[] will also be maintained.

iv)  The entries of the Top_array[] will be initialized to -1. This implies that all the stacks are empty.

v)  Firstly the entries of the array Next_array[i] will be initialized to i+1, since all the slots initially are free and are pointed to the next slot.

vi) Initialize The top of the free stack that is maintaining the free slots  as 0.

vii)  The complexity of push () (method to insert an element) and pop () (method to delete an element) operations by using this method is O (1).

• How to use method 2 to implement several queues

The same method applicable to implementing several stacks is used here but with a difference is the presence of three extra arrays which are :

Front_array[] = indicates the number of queues. This array stores the indexes of the front elements of the stacks.

Rear_array[] = determines the sizeof the array k . This array stores the indexes of the last elements of the stacks.

Next_array[] = The array n indicates the size of the single array say x. This array stores the indexes of the next items that is being pushed.

i) The initial actual array is a[] which will store the queues. The free slots will also be maintained.

ii)The entries of the Front_array[] will be initialized to -1. This means  that all the queues are empty initially

ii) Initially the entries of the array Next_array[i] will be initialized to i+1, since all the slots initially are free and are pointed to the next slot.

iv) Apply The complexity of enqueue ()  and dequeue ()  by using this method is O (1).