Suppose that some applications require using two stacks whose elements are of th

Question

Suppose that some applications require using two stacks whose elements are of the same type. A natural storage structure of such a two-stack data type would consist of two arrays and two top pointers. a. Explain why this may not be a space-wise efficient implementation b. A better storage structure for a two-stack data structure would be to use a single array for the storage structure. Design a class for this two-stack data type. In your methods for the basic stack operations, the number of stack to be operated upon (1 or 2) should be passed as a parameter. Also, the push operation should not fail because of a stack-full condition until all locations in the storage array have been used. push (int stackNum, int value) int pop (int stackNum) boolean isFull () boolean isEmpty (int stackNum) void display(int stackNum)

Explanation / Answer

a. Not space efficiency because:
     If a situation arises when one stack is full, but other is almost empty, the one which is full will throw stack overflow exception soon, though there are spaces available in the other stack
     If both stacks are empty most of the time, many locations would remain unused, yet consuming memory.

b.
class TwoStackApp {
   int[] stacks;
   int top1, top2;

   TwoStackApp() {
       stacks = new int[50];
       top1 = -1;
       top2 = 50;
   }

   void push (int stackNum, int value) {
       if (isFull())
           return;
       if (stackNum == 1)
           stacks[++top1] = value;
       else if (stackNum == 2)
           stacks[--top2] = value;
   }

   int pop(int stackNum) {
       if (isEmpty(stackNum)
           return;
       if (stackNum == 1)
           return stacks[top1--];
       else if (stackNum == 2)
           return stacks[top2--];
   }

   boolean isFull(){
       return (top1 + 1) == top2;
   }

   boolean isEmplty(int stackNum) {
       if (stackNum == 1)
           return top1 == -1;
       else if (stackNum == 2)
           return top2 == 50;
       else
           return true; //this is useless
   }

   void display(int stackNum) {
       if (stackNum == 1)
           for (int i = top2; i<50; i++)
               System.out.println(stacks[i]+" ");
       else if (stackNum == 2)
           for (int i = top1; i>=0; i--)
               System.out.println(stacks[i]+" ");
   }
}

I kept the code as simple as possible for you. If you face trouble with the code, please feel free to comment below. I shall be glad to help you.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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