Create a data structure twoStacks that represents two stacks. Implementation of twoStacksshould use only one array, i.e., both stacks should use the same array for storing elements.
Method 2 (A space efficient implementation)
The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.
The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.
class twoStacks{ int *arr; int size; int top1, top2;void push1(int x) { // There is at least one empty space for new element if (top1 < top2 - 1) { top1++; arr[top1] = x; } else { cout << "Stack Overflow"; exit(1); } } // Method to push an element x to stack2 void push2(int x) { // There is at least one empty space for new element if (top1 < top2 - 1) { top2--; arr[top2] = x; } else { cout << "Stack Overflow"; exit(1); } } // Method to pop an element from first stack int pop1() { if (top1 >= 0 ) { int x = arr[top1]; top1--; return x; } else { cout << "Stack UnderFlow"; exit(1); } } // Method to pop an element from second stack int pop2() { if (top2 < size) { int x = arr[top2]; top2++; return x; } else { cout << "Stack UnderFlow"; exit(1); } }};
No comments:
Post a Comment