C++ Two stacks of positive integers are needed, one containing elements with val

Question

C++ Two stacks of positive integers are needed, one containing elements with values less than or equal to 1,000 and the other containing elements with values larger than 1,000. The total number of elements in the small-value stack and the large-value stack combined are not more than 200 at any time, but we cannot predict how many are in each stack. (All of the elements could be in the small-value stack, they could be evenly divided, both stacks could be empty, and so on.) Can you think of a way to implement both stacks in one array? a. Draw a diagram of how he stack might look. b. Write definitions for such a double-stack structure. c. Implement the push operation; it should store the new item into the correct stack according to its value (compared to 1,000).

Explanation / Answer

Two stacks can be implemented using a single array. First create an array that has the capacity more than the two stacks combined.

Create the array double_stacks()

push1(int x) –> pushes x to first stack
push2(int x) –> pushes x to second stack

pop1() –> pops an element from first stack and return the popped element
pop2() –> pops an element from second stack and return the popped element

Approach: we can divide the array into two parts but it is not affective so another approach is to use two ends of the array as two seperate stacks.

The stack1 is pushed from arr[0] place and the stack2 is inserted from the place arr[n-1].To check for overflow, all we need to check is for space between top elements of both stacks.

free = 0; top1 = -1 , top2 = -1

next[i] = i+1,

next[n-1] = -1 initially

Condition for full, full= -1,

stack empty condition, top1= -1

Insert into stack1=   

Pop from stack 1=

similarly implement pop2 and push2 from opposite sides.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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