How to implement a deque using two stacks

Question

Deque ("doubled-ended queue") operations, en-queue and de-queue are possible from both ends.

How do to I define ADT operations for deque using 2 stacks?

The implementation should also take performance into consideration.

Landmeier

@MitchWheat - I am not able to find any good link which explains the concept clearly. If you found one can you please share. – Landmeier

@MitchWheat - Only queue implementation using stacks is available not dequeue using two stacks. – Landmeier

@Landmeier Is this for homework? – Expurgatory

@TylerCrompton - No. One of my friends was asked this is in an interview, the only solution we could think of has been mentioned by Andreas in the answers but it's not good performance-wise. – Landmeier

Well, that's the only way to do it. A dequeue should really be implemented with a linked list (preferably a singly linked list). The question was probably more of trying to determine your friend's problem solving skills. That's actually why it is also referred to as a head-tail linked list. – Expurgatory

I don't think it's that bad performance wise actually. Sure, there are certain workloads that really kill the performance, but if you roughly know what your workload will be you can use other (maybe faster) things than linked lists. – Ananias

@AndreasHenning Well, a stack is very basically a specialized case of a linked list. So I fail to see how using two stacks would be more efficient than using one singly linked list seeing as the two-stack implementation must transfer it's content between stacks periodically. This can cause some (or even many) operations to be linear, whereas a singly linked list implementation is guaranteed to be constant time. – Expurgatory

@TylerCrompton but you'll also have to see memory allocation as a factor. I'm implying C/C++ as a language here, where stacks are usually implemted via arrays as opposed to linked lists, because the time overhead for memory allocation is significantly higher for linked lists. Also, the two-stack implementation would only have linear time for a dequeue operation when the stack is empty. and again, if your workload suggests this is unlikely to happen, then two stacks should be fine. – Ananias

@TylerCrompton Please note that really I don't want to imply that two stacks are generally better than a doubly linked list, just that there are certain edge cases where they CAN theoretically perform better. :) – Ananias

Answer 1

the simplest solution would be to use one stack as the head of the queue, and one as the tail. The enqueue operations would just be a push to the respective stack, and the dequeue operations would just be a pop on the respective stack.

However, if the stack you want to dequeue from is empty, you'd have to pop each element from the other stack and push it back to the stack you want to dequeue from, and then dequeue the last one. That's not really good performance, so the overall performance of this implementation strongly depends on the workload. If your workload is a balanced number of front/back enqueue and dequeue operations, then this will be really really fast. But if your workload consists of a lot of alternating head-dequeues and tail-dequeues while the queue is large, then this will obviously be a bad approach.

Hope this helps

Ananias

This is the solution I came up with as well but as you correctly pointed out performance is not good. Can any modification be made to this implementation to improve performance. – Landmeier

@Landmeier well, as I said, the performance strongly depends on your workload. the only workload that will really get the weak point of this implementation is when you alternately call frontDequeue and backDequeue on a large queue. otherwise, this will be fine. – Ananias

You mean frontEnqueue and backDequeue? – Landmeier

@Landmeier no, front enqueue and back dequeue will be fine, because the elements would have to be moved the the "back dequeue"-stack only once. but if you dequeue from both ends, you'd have to move the elements from one stack to the other every time you dequeue from a different end. EDIT: given the stack is empty... – Ananias

Got confused with back-front-enqueue-dequeue :P. Thanks for the good explanation in above comment :) – Landmeier

This is obviously an interview question, and not a practical one. Using two stacks to make a dequeue will fail to meet big O expectations under certain conditions. – Garate

The missing key to this answer is the fact that you don't have to dump the entire stack into the other. Instead, you should dump until the stacks are roughly equal in size. This gives optimal amortized complexity for a deque. – Caro

Answer 2

This is how I did it, what really matters is that you make sure when you keep poping from one and it gets empty then it starts to pop from the other one, ( we got to make sure it pop from the end of stack ) we can do this by emptying one stack into the another. and keep poping there.

public class NewDeque {

Stack<E> frontstack;
Stack<E> endstack;

public NewDeque() {

    frontstack = new Stack<>();
    endstack = new Stack<>();

}

void addFirst(E e) {

    frontstack.push(e);
}

E delFirst() {
    if (frontstack.isEmpty()) {
        while (!endstack.isEmpty()) {
            frontstack.push(endstack.pop());
        }
        return frontstack.pop();
    }
    return frontstack.pop();
}

void addLast(E e) {

    endstack.push(e);
}

E delLast() {
    if (endstack.isEmpty()) {
        while (!frontstack.isEmpty()) {
            endstack.push(frontstack.pop());
        }
        return endstack.pop();
    }
    return endstack.pop();
}

int size() {
    return frontstack.size() + endstack.size();
}

boolean isEmpty() {
    return (size() == 0) ? true : false;
}

E get(int i) {
    if (i < endstack.size()) {
        return endstack.get(endstack.size() - i - 1);
    } else {
        return frontstack.get(i - endstack.size());
    }

}

static void print(NewDeque<Integer> ds) {
    for (int i = 0; i < ds.size(); i++) {
        System.out.print(" " + ds.get(i) + " ");
    }
}

Caylor

Answer 3

an interesting way to do this is as follows

enqueue(q,  x)
  1) Push element x to stack1. This very simple, the problem is dequeue

dequeue(q)
  1) If stacks1 and stack2 are empty then error  "UNDERFLOW"
  2) If stack2 is empty, then 
       while (stack1 is not empty) do
           push all element from satck1 to stack2.
        end while;
  3) Pop the element from stack2 and return it.

Corselet

This implements a queue, not a dequeue. – Binghi

Answer 4

Found this solution for ArrayStacks. I think, something like that could work for any kind of stacks. You can use Andreas Grapentin answer, but add to it a balance function, that should be called sufficiently rarely. The idea is that when the balance between two stacks is too shifted, you should push them into an array (ordered as the queue), then split this array at the middle and copy its halves back to stacks.

Insist