# a question in stacks

alex lotel

Ranch Hand

Posts: 191

posted 8 years ago

i have two stack S1 and S2 the total amount of objects

in them is "n"

in both stack all the objects are sorted in accending order

(the biggest number is on top the smallest number is on the bottom)

and thats the way it goes in both stacks

the question asks me to build a method which

puts all of the objects from stacks S1 and S2 into stack S3

in accended order plus we have to accomplish this using 4n-4 moves ??

(the biggest number is on top the smallest number is on the bottom)

i tried to solve that by

flipping the stacks using the S3 so they will be sorted from the smallest

to the biggest

taking two templorary variables pop each object from each stack

into the temporary variable

and then we compare them and the smallest goes to S3

and the other one waits till we have an object from the other stack which is smaller than him,

and then we have to flip S3 in order have the biggest on top

also i tried using TOP commang but i found out that

its implementation also has push and pop in it.

but in that way we have more than 4n-4 moves

[ February 16, 2008: Message edited by: donaldth smithts ]

in them is "n"

in both stack all the objects are sorted in accending order

(the biggest number is on top the smallest number is on the bottom)

and thats the way it goes in both stacks

the question asks me to build a method which

puts all of the objects from stacks S1 and S2 into stack S3

in accended order plus we have to accomplish this using 4n-4 moves ??

(the biggest number is on top the smallest number is on the bottom)

i tried to solve that by

flipping the stacks using the S3 so they will be sorted from the smallest

to the biggest

taking two templorary variables pop each object from each stack

into the temporary variable

and then we compare them and the smallest goes to S3

and the other one waits till we have an object from the other stack which is smaller than him,

and then we have to flip S3 in order have the biggest on top

also i tried using TOP commang but i found out that

its implementation also has push and pop in it.

but in that way we have more than 4n-4 moves

[ February 16, 2008: Message edited by: donaldth smithts ]

posted 8 years ago

I can see how to do it in 4n moves.

Hint: use a 'merge sort' and move stack1 and stack2 onto stack3. The result of stack3 will be sorted but will be the wrong way, so you could order stack3 by popping off the 2n elements that it contains onto an empty stack.

This is 4n which is Order-n , in "big-Oh" notation, that is O(n).

The minus-four isn't really significant because it's just a constant.

[ February 17, 2008: Message edited by: Kaydell Leavitt ]

Hint: use a 'merge sort' and move stack1 and stack2 onto stack3. The result of stack3 will be sorted but will be the wrong way, so you could order stack3 by popping off the 2n elements that it contains onto an empty stack.

This is 4n which is Order-n , in "big-Oh" notation, that is O(n).

The minus-four isn't really significant because it's just a constant.

[ February 17, 2008: Message edited by: Kaydell Leavitt ]

alex lotel

Ranch Hand

Posts: 191

posted 8 years ago

i cant see how you counted the moves

can you be more spesific on the moves on the stack

like when you say merge sort

merge sort works on an array

we take each on a half of a part from an arraya sort

and then merge again

i dont know how to imagine this on a stacks??

i dont know how its done in order to calculate the number of moves

can you explain you system with more details please?

[ February 17, 2008: Message edited by: donaldth smithts ]

can you be more spesific on the moves on the stack

like when you say merge sort

merge sort works on an array

we take each on a half of a part from an arraya sort

and then merge again

i dont know how to imagine this on a stacks??

i dont know how its done in order to calculate the number of moves

can you explain you system with more details please?

[ February 17, 2008: Message edited by: donaldth smithts ]

posted 8 years ago

The minus four is significant because it is not a problem with Big O -- the problem states that you must do it in 4n-4 moves. It is a worst case limitation on the moves, which must be honored.

Yes, you can do it in 4n moves. The merge sort will be the first n moves. The move from S3 to either s1/s2 will be the second n moves. The move from s1/s2 to s2/s1 will be the third n moves. And finally, the move from s2/s1 back onto s3 will be the final n moves.

Now how do you get the 4 moves back? You can get it back by consolidating the phases. For example, you can save one move between the third n and forth n moves. This is the easy one to envision -- the other three are a bit harder to find... which I will leave for everyone to try to find first...

Henry

Originally posted by Kaydell Leavitt:

I can see how to do it in 4n moves.

Hint: use a 'merge sort' and move stack1 and stack2 onto stack3. The result of stack3 will be sorted but will be the wrong way, so you could order stack3 by popping off the 2n elements that it contains onto an empty stack.

This is 4n which is Order-n , in "big-Oh" notation, that is O(n).

The minus-four isn't really significant because it's just a constant.

The minus four is significant because it is not a problem with Big O -- the problem states that you must do it in 4n-4 moves. It is a worst case limitation on the moves, which must be honored.

Yes, you can do it in 4n moves. The merge sort will be the first n moves. The move from S3 to either s1/s2 will be the second n moves. The move from s1/s2 to s2/s1 will be the third n moves. And finally, the move from s2/s1 back onto s3 will be the final n moves.

Now how do you get the 4 moves back? You can get it back by consolidating the phases. For example, you can save one move between the third n and forth n moves. This is the easy one to envision -- the other three are a bit harder to find... which I will leave for everyone to try to find first...

Henry

posted 8 years ago

I just looked up "merge sort" in wikipedia.org and I must have used the wrong terminology.

What I meant was:

1. Create a new stack, called stack4

2. loop as long as stack1 or stack2 has objects on them

3. compare the object on the top of stack1 to the object that is on the top of stack2

4. pop the larger object off of its stack and push it onto stack4

5. end of loop // you loop until both stack1 and stack2 are empty

// At this point all 2n objects are on stack4 in descending order.

// We now need to reverse the objects

1. Create a new stack, called stack3

2. loop until stack4 is empty

3. pop the top object off of stack4 and push it onto stack3

4. end of loop // the loop ends when stack4 is empty.

// At this point, stack3 has all 2n objects in ascending order

// How many moves did it take? 4n. I'll leave it to you to do it in less than 4n moves.

// but as long as we're optimizing the code, what if instead of using a stack for stack4,

// we used a Queue. Then we wouldn't have to reverse stack4. The Queue would

// already be in the correct order after 2n moves (but I guess this isn't what was specified).

// Does the specification require that we only use Stack objects?

Kaydell

[ February 18, 2008: Message edited by: Kaydell Leavitt ]

What I meant was:

1. Create a new stack, called stack4

2. loop as long as stack1 or stack2 has objects on them

3. compare the object on the top of stack1 to the object that is on the top of stack2

4. pop the larger object off of its stack and push it onto stack4

5. end of loop // you loop until both stack1 and stack2 are empty

// At this point all 2n objects are on stack4 in descending order.

// We now need to reverse the objects

1. Create a new stack, called stack3

2. loop until stack4 is empty

3. pop the top object off of stack4 and push it onto stack3

4. end of loop // the loop ends when stack4 is empty.

// At this point, stack3 has all 2n objects in ascending order

// How many moves did it take? 4n. I'll leave it to you to do it in less than 4n moves.

// but as long as we're optimizing the code, what if instead of using a stack for stack4,

// we used a Queue. Then we wouldn't have to reverse stack4. The Queue would

// already be in the correct order after 2n moves (but I guess this isn't what was specified).

// Does the specification require that we only use Stack objects?

Kaydell

[ February 18, 2008: Message edited by: Kaydell Leavitt ]

alex lotel

Ranch Hand

Posts: 191

posted 8 years ago

A merge sort works with arrays. A merge sort is recursive. Blah. Blah. Blah. Both stacks are already sorted -- so when you said "merge sort", I just thought you meant "merge" the two stacks together... Which from your description, I understood correctly.

No... the total amount of items is n. If you create a forth stack, you can do the whole thing in 2n. This is why I assumed a forth stack is not allowed -- and that it must be solved within the three allocated stacks.

Henry

I just looked up "merge sort" in wikipedia.org and I must have used the wrong terminology.

A merge sort works with arrays. A merge sort is recursive. Blah. Blah. Blah. Both stacks are already sorted -- so when you said "merge sort", I just thought you meant "merge" the two stacks together... Which from your description, I understood correctly.

1. Create a new stack, called stack4

2. loop as long as stack1 or stack2 has objects on them

No... the total amount of items is n. If you create a forth stack, you can do the whole thing in 2n. This is why I assumed a forth stack is not allowed -- and that it must be solved within the three allocated stacks.

Henry

alex lotel

Ranch Hand

Posts: 191

alex lotel

Ranch Hand

Posts: 191

posted 8 years ago

move bank:

push =1 move

pop =1 move

top =2 moves (because its implemented using i pop and one push command)

1)we look at the values of each two top object from stack S1 and S2

and push the smallest to S3

in this step we make the Top command n times

we make the pop command n times and we make the push command n times

thats makes us 2n+n+n =4n

2)now we need to flip S3 but we already got an overdraw in our bank account

and IRS is knocking on my door righ now

you said

"you can save one move between the third n and forth n moves. This is the easy one to envision -- the other three are a bit harder to find... which I will leave for everyone to try to find first... "

i dont know how to make that any simpler

i thought of it many time

???

push =1 move

pop =1 move

top =2 moves (because its implemented using i pop and one push command)

1)we look at the values of each two top object from stack S1 and S2

and push the smallest to S3

in this step we make the Top command n times

we make the pop command n times and we make the push command n times

thats makes us 2n+n+n =4n

2)now we need to flip S3 but we already got an overdraw in our bank account

and IRS is knocking on my door righ now

you said

"you can save one move between the third n and forth n moves. This is the easy one to envision -- the other three are a bit harder to find... which I will leave for everyone to try to find first... "

i dont know how to make that any simpler

i thought of it many time

???

posted 8 years ago

Ohh... My definition of a move as an item being moved from one stack to another.

If you define this as two moves. And to even look at the top of the stack as two moves.... then you're done. With your definition, I don't believe the problem can be solved.

Henry

[ February 18, 2008: Message edited by: Henry Wong ]

move bank:

push =1 move

pop =1 move

top =2 moves (because its implemented using i pop and one push command)

Ohh... My definition of a move as an item being moved from one stack to another.

If you define this as two moves. And to even look at the top of the stack as two moves.... then you're done. With your definition, I don't believe the problem can be solved.

Henry

[ February 18, 2008: Message edited by: Henry Wong ]

posted 8 years ago

First of all, you need to confirm the rules first. Your homework assignment can't be done if you don't know what you are supposed to do.

Second of all, it is still a homework assignment. And based on my definition, I did most of it for you in a previous post (more than I would like actually).

On the chance that my definition is the correct one, it is against JavaRanch best-practices to give you the answer without you trying it yourself. See...

http://faq.javaranch.com/java/DoYourOwnHomework

Henry

Originally posted by donaldth smithts:

so by your definition how whould you solve it??

First of all, you need to confirm the rules first. Your homework assignment can't be done if you don't know what you are supposed to do.

Second of all, it is still a homework assignment. And based on my definition, I did most of it for you in a previous post (more than I would like actually).

On the chance that my definition is the correct one, it is against JavaRanch best-practices to give you the answer without you trying it yourself. See...

http://faq.javaranch.com/java/DoYourOwnHomework

Henry

alex lotel

Ranch Hand

Posts: 191

posted 8 years ago

in my threades i showed some ways

in which i tried to solve it

in your first thread you sayd that there is some way to save moves

between the 4th and the 5th step

and you will live that to me

thats not helping me

i need your full solution

[ February 18, 2008: Message edited by: donaldth smithts ]

in which i tried to solve it

in your first thread you sayd that there is some way to save moves

between the 4th and the 5th step

and you will live that to me

thats not helping me

i need your full solution

[ February 18, 2008: Message edited by: donaldth smithts ]

alex lotel

Ranch Hand

Posts: 191