[第二轮] 3/4-3/10 CareerCup 3.6

Write a program to sort a stack in ascending order (with biggest items on top). You may use additional stacks to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

No limitations to the number of the stack? Push each value to a single stack, then sort?

EchoMemory 发表于 2013-3-3 21:23
No limitations to the number of the stack? Push each value to a single stack, then sort?

you are given only one additional stack.

lty900301 发表于 2013-3-4 12:26
you are given only one additional stack.

ok..my solution is based in the description of the problem, where "You may use additional stacks" used Nouns in Plural Form...

lty900301 发表于 2013-3-4 12:26
you are given only one additional stack.

could I use additional variable?

lty900301 发表于 2013-3-4 12:26
you are given only one additional stack.

I don't think they specify the number of stacks we can use. So, theoretically, EchoMemory's algorithm is OK.

EchoMemory 发表于 2013-3-4 12:53
could I use additional variable?

I think you could, but I guess they prefer not to

I have a not very good solution, because I think the algorithm involves too many pop and push. I use two additional stacks.
The algorithm is somewhat similar to insertion sort: we maintain a sorted stack s3(the top element of this stack is the smallest one), then we compare the top of the original stack s1 with every element in s3, using stack s2 as temporal holder. After all elements are in the right position, then we pop every elements in s3 back into s1.
https://gist.github.com/ryancooper/9e58b62b43d7373aaa9f

ryancooper 发表于 2013-3-4 13:13
I think you could, but I guess they prefer not to

if I could use additional variable(not array) to record the min_val and pop_size in my sub stack, I could use two stacks to sort. Every time push pop_size times(initial stack.size()) from first stack to the second stack(), and record the min_element(should update every time). When push_back, firstly push the min_val to the first stack; pop_size--; and push the value in the second stack to first stack. if the value pushing_back is the min_val, just delete.

EchoMemory 发表于 2013-3-4 14:00
if I could use additional variable(not array) to record the max_val and pop_size in my sub stack,  ...

If I can be allowed to use one additional variable, then I can reduce two additional stacks to just one too.And it seems you have a slightly mistake. Because at last, we have the biggest element at top of the stack. If I comprehend your algorithm correctly, then you seem to put the largest one at the bottom of the stack