Leetcode day 15: a queue from two stacks

An old favorite, which I got at a Google interview. Not understanding the Google mindset at the time (2007 or so), I had my engineer hat on first, and pointed out that if you’re going to build a data structure, build the damn data structure. It’s ludicrous to build two stacks when you could build one queue in approximately the same amount of time.

However, the real purpose was “do you understand that pushing onto one stack and then popping items off onto the other reverses their order?”. Sure. OK. Fine. You could ask me “what would happen if…”, but no, it needs to be a no-one-with-any-brains-would-ever-do-this programming problem. (Again, this is a “let’s talk about your algorithm choices in our next 1-1” problem.)

Anyway, yeah. So I tried with arrays again to start and it was a huge PITA. I tried that for about ten minutes and said, forget this, I’m building it with linked lists.

So we have a Node that is added at the head to push, and delinked to its tail to pop. Easy-peasy.

The push operation just adds to the incoming stack, and doesn’t do anything else until we have our first pop, and which point we call the core routine here, Cycle. Cycle pops items one at a time off the in stack and pushes them to the out stack. Now a pop pulls the first item that was pushed, as required, since we’ve just reversed the in stack. I did have one error, caught in the submit, in that you don’t just check for the in stack being empty, but you also need to check for the out stack not being empty. If you don’t, you end up queueing an item out of order. Always wait for the output to be empty before actually cycling.

I did have to refresh my memory on adding a method to a struct – it’s func (this *Node) Cycle – but otherwise this was almost as much a breeze as the tree inversion.

I do need to do some exercises on managing arrays better, though — you can’t always use a linked list, especially if you need actual indexing.

Overall, pleased with the solution: 82nd percentile runtime, but 18th percentile memory. Might be better if I kept the popped nodes on a free list.

type Node struct {
    Val int
    Next *Node
}

type MyQueue struct {
    In *Node
    Out *Node
    free *Node
}

func Constructor() MyQueue {
    return MyQueue{
        In: nil,
        Out: nil,
    }
}

func(this *MyQueue) Cycle() {
    fmt.Println(">>>cycling in to out")
    if this.In == nil {
        // Nothing to cycle
        fmt.Println(">>cycle empty in")
        return
    }
    if this.Out != nil {
        // Don't cycle yet
        return
    }
    // Pop items off the in stack, push on the out stack
    for {
        current := this.In
        this.In = this.In.Next // Pop In
        fmt.Println("cycle>> pop in", current.Val)
        
        current.Next = this.Out // Push Out
        this.Out = current

        current = this.In
        if current == nil {
            break
        }
    }
    // Clear in stack
    fmt.Println("cycle>> clear in")
    this.In = nil
}

func (this *MyQueue) Push(x int)  {
    // Append to in stack. Leave there until we cycle.
    n := &Node{
        Val: x,
        Next: this.In,
    }
    this.In = n
    fmt.Println(">>push on in", x)
}


func (this *MyQueue) Pop() int {
    if this.Empty() {
        panic("popped empty stack")
    }
    if this.Out == nil {
        this.Cycle()
    }
    value := this.Peek()
    fmt.Println(">>pop Out")
    this.Out = this.Out.Next
    return value
}


func (this *MyQueue) Peek() int {
    if this.Empty() {
        panic("peek on empty stack")
    }
    this.Cycle()
    fmt.Println("peek>>")
    return this.Out.Val
}


func (this *MyQueue) Empty() bool {
    fmt.Println("check for empty")
    return this.In == nil && this.Out == nil    
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

Editorial note: other solutions submitted really stretch the definition of stack – a lot of them do do appends and slices, but of a single array, which is kind of not implementing two stacks at all.

Note 2: adding a free queue of nodes improves memory usage by 1%. Not worth it.