Interview Questions And Answers 
-
Is it possible to keep 2 stacks in a single array, if one grows from position one of the array, and the other grows from the last position. Write a procedure PUSH(x,s) that pushes element x onto stack S, where S is one or the other of these two stacks. Include all necessary error checks (Sent by Puneet Saraf)
6,659 Views |
(21 votes, avg: 3.38)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Its better to use nodes here - in this way you use what is called the dynamic data structure. This means the size of the structure grows at run time.
Start by defining a pointer to node structure.
each node has a data field and pointer field
The question did not ask for a suggestion. It is definitely possible to implement 2 stacks using a single array. The array shud be visible to both stacks (and therefore be global, or shud provide equivalent effect). Also the stack tops shud be taken care of. one top will decrement everytime the push method is called and one would be incremented. As soon as s1.top==s2.top we shud throw an exception.
As stated that the array should grown towards one point.so when s[i]==s[j] then it should through an exception.If we will look care fully if u will just mention the delete option that is LIFO than the result data structure will be nothing but the double ended queue.
Imagine the situation whereby the array is only two ‘items’ ( bytes ) long
You may have:
——————
One stack that will overflow at three pushes
OR
Two stacks that will overflow at three pushes IF either of them has zero bytes in them
OR
Two stacks that will overflow at two pushes IF either of them has at least one byte in them
OR
Two stacks that will overflow at one push IF either of them has at least two bytes in them
#define M 100
int Stack[M];
int top1=-1,top2=M;
//s determine which stack
void push(int s,int n)
{
if(top1+1==top2)
printf(”Stack is full”);
else
{
if(s==1) //push into first stack
{
top1++;
Stack[top1]=n;
}
else if(s==2) //push into second stack
{
top2–;
Stack[top2]=n;
}
else
{
printf(”Invalid stack”);
}
}
}
Invalid stack
Seems like you could denote a single array using separate rows to indicate your separate stacks. (i.e. - array1 [2][n]). Then, it would be an easy “swap” type program. Just a thought…
Leave an Answer/Comment