The problem is from the cracking coding Interview programming book.

The problem is that:

Sort Stack: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array).

Below is my code in scala to sort Stack s, however, I think it is not the optimal solution in scala, may I know any other solutions can be written in functional programming language scala.

import scala.collection.mutable.Stack
    def sorted(s: Stack[Int]): Unit={
        def sortedwithtemp(original: Stack[Int], temp:Stack[Int], current: Int): Unit=(current, temp.top)match{
          case (a,b) if a>=b =>temp.push(a); 
          if(original.size==0) original.pushAll(temp)
          else {
            val curr= original.pop()
          sortedwithtemp(original, temp, curr) 

          case (a,b) => original.push(temp.pop()); 
           if (temp.isEmpty) {temp.push(current); val curr= original.pop();sortedwithtemp(original, temp, curr)}
           else sortedwithtemp(original, temp, current)       

        val tempstack=new Stack[Int]
        if (s.size>=2){
          val current=s.pop()
          sortedwithtemp(s, tempstack, current)
  • \$\begingroup\$ You can compare to this version of 2 stack sort . The problem statement is not quite right, you need to be able to move 1 element to a local variable in order to be able to manipulate the stacks in order to "move" that element. \$\endgroup\$
    – rcgldr
    Dec 7 '16 at 9:13
  • \$\begingroup\$ @rcgldr, I use current as the local variable to store, pls check, thanks \$\endgroup\$
    – sweetyBaby
    Dec 7 '16 at 9:17
  • \$\begingroup\$ Using current as the local variable is OK. My point was that the problem statement is faulty, not your code. \$\endgroup\$
    – rcgldr
    Dec 7 '16 at 9:18
  • \$\begingroup\$ problem statement I just copy from the book, and my main concern is how to improve it as scala is the functional programming :( \$\endgroup\$
    – sweetyBaby
    Dec 7 '16 at 9:19
  • \$\begingroup\$ With just 2 stacks, the time complexity is O(n^2), and similar to insertion sort. You pop off an element, then move the stacks to find where to insert the element, move the stacks back, then repeat the process until the stack is sorted. With 3 stacks, the sort can be done in O(n log(n)), using merge sort or better still polyphase merge sort (almost no one knows polyphase sort anymore). \$\endgroup\$
    – rcgldr
    Dec 7 '16 at 9:26

It's easier if you define your own Stack type, as the Scala Stack is a collection type which makes it a bit heavyweight.

A stack is either an Empty stack or an element (top) pushed onto a stack (pop):

// Define a simple immutable stack datatype.
trait Stack[+T]
object Empty extends Stack[Nothing]
case class Push[+T](top : T, pop : Stack[T]) extends Stack[T]

We can sort a stack by inserting each element onto a sorted stack. The insertion is done by popping the stack until we find the right position, and then rebuilding the stack when the call-stack returns.

object StackSort {
    // Sort a stack using insertion-sort.
    def sort[T](s : Stack[T])(implicit ord : Ordering[T]) : Stack[T] =
        s match {
            case Empty => s
            case Push(top, pop) => insert(top, sort(pop))

    // Insert an element into a sorted stack.
    def insert[T](x : T, s : Stack[T])(implicit ord : Ordering[T]) : Stack[T] =
        s match {
            case Push(top, pop) if (ord.lt(x, top)) => Push(top, insert(x, pop))
            case _ => Push(x, s)

A simple test:

object Test {
    import StackSort._

    def main(args : Array[String]) : Unit = {
        val test = Push(3, Push(1, Push(2, Push(5, Empty))))

        val sorted = sort(test)

which outputs:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.