Implementation of Stacks and Queues

[komalac]

Hi All,
Can any on guide me in the logic / algorithm to implement 2 stacks using one array and a queue using 2 stacks. I need this very urgently.

Thanks in advance.
Komala

[fahad]

Hello,
Its very simple to use 2 stacks to maintain one queue
the algorithm goes likem this

declare two stacks st1 and st2
whenever u want to enqueue an element in the queue simply push it in the stack st1
when u want to dequeue an element pop all the elements from st1 one by one and push them in st2 (now st2 contains the elements in inverse order then that of previous st1)
Pop first element from st2 , (remember st1 is empty at this time) , this element is the required element which was to be dequeued
Then push all the element form st2 one by one and push them back in st1

******************************************************
For example

To Enqueue
We want to enqueue 29

Originally

St1 St2
26 Empty
25
18
15
10
12

St1.push(29) //To insert Insert 29

St1 St2
29 Empty
26
25
18
15
10
12

To Dequeue
We want to dequeue 12 as it was the first element to be enqueued

originally

St1 St2
29 Empty
26
25
18
15
10
12

While(st1 is not empty)

St2.push(st1.pop);//pop elements from st1 and push them in St2

St1 ST2
Empty 12
10
15
18
25
26
29

int result = St2.Pop() // it will give result 12

now
St1 ST2
Empty 10
15
18
25
26
29

then again

While(st2 is not empty)

St1.push(st2.pop);//pop elements from st1 and push them in St2

St1 St2
29 Empty
26
25
18
15
10

*********************************************************

If u want to check isEmpty() just check if st1 is Empty.

I hope u will understand it , if their is still any confusion u can ask.......
Fahad

[fahad]

there is some problem in the above example as the format is changed so some members of the stack are out of their places
/*problamatic area

St2.push(st1.pop);//pop elements from st1 and push them in St2

St1 ST2
Empty 12
10
15
18
25
26
29

int result = St2.Pop() // it will give result 12

now
St1 ST2
Empty 10
15
18
25
26
29
*/

It should be like this

St2.push(st1.pop);//pop elements from st1 and push them in St2

St1 ST2
Empty 12
............10
............15
............18
............25
............26
............29

int result = St2.Pop() // it will give result 12

now
St1 ST2
Empty 10
............15
............8
............25
............26
............29

Fahad

[komalac]

Thanks a lot :))
Very clear explanation. I got it.

Do you know the other logic (2 stack with an array).

Thanks again,
Komala.

[fahad]

hello;
yes i think know it also but let me think for five minutes and then i will post it
Fahad

[fahad]

hi;
make an array
declare two stacks St1 and St2
make top1==-1 for st1 and top2==MAX_SIZE
when u push an element in st1

push it as st1.push(int x){ top1++; array[top1]=x;}

when u push an element in st2

push it as st1.push(int x){ top2--; array[top2]=x;}

when u pop an element from st1

pop it as st1.pop(){top1--; return array[top1++]=x;}

when u pop an element from st2

pop it as st2.pop(){top1++; return array[top2--]=x;}

I hope u will understand it also.
fahad

[fahad]

hi ,

The above mentioned way is actually to way growing array , stack 1 grows from left to right and stack 2 grows from right to left

tell me if their is still any problem reagrding it

[komalac]

Hi Fahad,
Oh gr8.
:) Thanks once again.

Komala

[fahad]

hi,
So u got both of them ,
thats good
r u indian?

[pavan]

Fahad,
The solution you have suggested for 2 stacks in an arry, in that you mean to say that there should be 2 classes for two stacks ???

Can you clarify this to me ?

hi,
So u got both of them ,
thats good
r u indian?

[fahad]

Hi pavan;
By saying two stacks in an array I dont mean two different classes,
It could be handeled in a single class ,
but the difference will be that the class will contain two pointers ,although in simple stack class there is only one pointer pointing towards the top element ,
This class containing two stacks will contain two pointers Top1 and Top2
Top1 will move with the expansion of stack1 while Top2 will move with the expansion of stack2.
Also Top1 will be incremented each time when an element is pushed into stack1 while Top2 will be decremented each time when an element is pushed into stack2. and opposite would be the case with Pop operation
but dont forget to make top1==-1 for st1 and top2==MAX_SIZE in the constructor.................

I hope u would have understand it ...............
If still therz some doubt , feel free to ask it again....

Bye
Fahad

[pavan]

Fahad,
Thank you for your clarification. So if we place 2 stacks in the same class then we may need 2 push functions, 2 pop functions right?
one for each stack as they want different expressions to be included in those functions.
would it be good to do like that?

Hi pavan;
By saying two stacks in an array I dont mean two different classes,
It could be handeled in a single class ,
but the difference will be that the class will contain two pointers ,although in simple stack class there is only one pointer pointing towards the top element ,
This class containing two stacks will contain two pointers Top1 and Top2
Top1 will move with the expansion of stack1 while Top2 will move with the expansion of stack2.
Also Top1 will be incremented each time when an element is pushed into stack1 while Top2 will be decremented each time when an element is pushed into stack2. and opposite would be the case with Pop operation
but dont forget to make top1==-1 for st1 and top2==MAX_SIZE in the constructor.................

I hope u would have understand it ...............
If still therz some doubt , feel free to ask it again....

Bye
Fahad

[fahad]

Hi;
yes u r right, u have to use two push and two pops,

where as this is concerned that it is good or not , u would have to understand why we use two stacks within an array , the reason is quite simple , in making two stacks in the same array , here we use only one data structure at a time but we can use it for two different puposes ,stack1 for some purpose and stack2 for some separate purpose,
also we achieve optimal use of given space,

Hope u would understand it easily , but still dont hesitate to ask again...if u have some problem
Fahad

[pavan]

Fahad,
That is a nice explanation
Thank you

[preethis]

Hi,

How to implement a stack using two queues ? Please help.

Thanks,
Preethi

[Dogtree]

Start a new thread, dude. It's bad form to bring an old thread back from the dead.

[Dave Sinkula]

Let me help by closing this one.