Monday, February 10, 2014

queue with 2 stacks, stack with 2 queues

queue with 2 stacks. for enqueue, s2->s1 and push into s1. for dequeue, s1->s2 and pop from s2.

enqueue(T x):
    while !s2.isEmpty():
        s1.push(s2.pop())
    s1.push(x)
    
T dequeue():
    while !s1.isEmpty():
        s2.push(s1.pop())
    return s2.pop()

stack with 2 queues. for push, enqueue into non-empty queue (or q2). for pop, dequeue all from non-empty queue, enqueue into other and return last.

push(T x):
    if !q1.isEmpty():
        q = q1
    else
        q = q2
    q.enqueue(x)

T pop():
    if q1.isEmpty() && q2.isEmpty():
        throw "empty"
    if !q1.isEmpty():
        q = q1
        other = q2
    else
        q = q2
        other = q1
    n = null
    while !q.isEmpty():
        n = q.dequeue()
        if q.isEmpty():
            break;
        other.enqueue(n)
    return n

No comments:

Post a Comment