Data Structures and Algorithms. JAVA. 8. A single array, stk[MAXELEMS], is used

Question

Data Structures and Algorithms. JAVA.

8. A single array, stk[MAXELEMS], is used to implement two stacks. The two stacks are grown in an array – one from each end. Two variables, head1 and head2 (head1 < head2), hold the index of the location of the top element in each of the stacks. Which of the following is the best for implementing the check for a full stack, given we want a space efficient algorithm.

(head1 = MAXELEMS / 2) and (head2 = MAXELEMS / 2+1)

head1 + head2 = MAXELEMS

(head1 = MAXELEMS / 2) or (head2 = MAXELEMS)

head1 = head2 – 1

     Answer:

Explanation / Answer

It has been mentioned clearly that we need a space efficient algorithm. For implementing space efficient two stacks in one array, both stacks can grow in opposite direction to any extent provided there is a space in array.

Let us assume we have an array of 10 elements. head1 starts at position 0 and head2 starts at position 9. stack1 can push element till position 8 if there are no elements in stack2. Like wise, stack2 can push element till position 1 if there are no elements in stack1.

Hence, condition to check for a full stack is head1 = head2 - 1

e.g. If head1 is at position 0 and head2 is at position 1, then there is no more space to insert an element. Hence stack is full.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.