C++ Deque VS Queue VS Stack

c++ deque vs queue vs stack

Moron/Aryabhatta is correct, but a little more detail may be helpful.

Queue and stack are higher level containers than deque, vector, or list. By this, I mean that you can build a queue or stack out of the lower level containers.

For example:

  std::stack<int, std::deque<int> > s;
  std::queue<double, std::list<double> > q;

Will build a stack of ints using a deque as the underlying container and a queue of doubles using a list as the underlying container.

You can think of s as a restricted deque and q as a restricted list.

All that is necessary is that the lower level container implements the methods needed by the higher level container. These are back(), push_back(), and pop_back() for stack and front(), back(), push_back(), and pop_front() for queue.

See stack and queue for more detail.

With respect to the deque, it is much more than a queue where you can insert at both ends. In particular, it has the random access operator[]. This makes it more like a vector, but a vector where you can insert and delete at the beginning with push_front() and pop_front().

See deque for detail.

Why is deque faster than queue?

From cppreference.com: std::queue

template<
    class T,
    class Container = std::deque<T>
> class queue;

Container - The type of the underlying container to use to store the elements.

So std::queue - by default - uses std::deque as its internal container, due to that it can only be at best as fast as std::deque (or the underlying container in general), and because being a wrapper it is - depending on the optimization the compiler can do - slower. So if you correctly measure a 20% slowdown, then you measure how good the compiler is in optimizing the wrapper code away at the given optimization level.

As std::queue exists to guarantee a FIFO usage, by only exposing these functions, I doubt - but I can't test it right now - that the slow down is that drastically with optimizations turned on. If it is I would consider that as a bug/defect of the capabilities of the compiler or library implementation.

What's the Big-O of a stack, queue, set, and deque?

This really depends on the implementation of each data structure. I'll go over a few, so you can get the idea of how to determine this.

Let's assume the Stack class is implemented using a Node (it can be implemented with an LinkedList, ArrayList, arrray, etc. as well).

Node top, bottom;
public Stack(Node n){
    top = bottom = n;
}

Stack has 3 primary methods: peek, push, and pop.

public int peek(){
    return top.value; //only return value
}

There wasn't much processing involved. It just returned a primitive value. This is O(1) for both time and space.

public void push(Node n){
    n.next = top;
    top = n;
}

Still no real processing. This is O(1) for both time and space. Let's skip pop() and try something more interesting. Let's try a method called contains(int v). It will search the stack to see if it contains a Node which contains a value equal to v.

public bool contains(int v){
    Node current = top;
    while(current != null){
        if(current.value == v){
            return true;
        }
        current = current.next;
    }
    return false;
}

Basically we'll move through the Node references until we find the value or we reach the end. In some cases, you'll find value early and in some cases later down the road. However, we care about the worst case! The worst possible case would be we have to check every single Node. Say there are n Nodes, then we have O(n).

You can apply these analysis skills to the other data structures, so you can solve the rest yourself. It's not too bad. Good luck. :)

Difference between enqueue and dequeue

Some of the basic data structures in programming languages such as C and C++ are stacks and queues.

The stack data structure follows the "First In Last Out" policy (FILO) where the first element inserted or "pushed" into a stack is the last element that is removed or "popped" from the stack.

Similarly, a queue data structure follows a "First In First Out" policy (as in the case of a normal queue when we stand in line at the counter), where the first element is pushed into the queue or "Enqueued" and the same element when it has to be removed from the queue is "Dequeued".

This is quite similar to push and pop in a stack, but the terms enqueue and dequeue avoid confusion as to whether the data structure in use is a stack or a queue.

Class coders has a simple program to demonstrate the enqueue and dequeue process. You could check it out for reference.

http://classcoders.blogspot.in/2012/01/enque-and-deque-in-c.html

Why use std::stack or std::queue?

To limit the user interface
You don't want your stack to be able to remove elements somewhere else instead of top. Why to use vector in place of stack if you have exactly same performance also stack improves readability and reliability.

std::stack is more expressive than std::vector when the container you want to implement is truly a LIFO.

What's the difference between deque and list STL containers?

From the (dated but still very useful) SGI STL summary of deque:

A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.

Here's the summary on list from the same site:

A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.

In summary the containers may have shared routines but the time guarantees for those routines differ from container to container. This is very important when considering which of these containers to use for a task: taking into account how the container will be most frequently used (e.g., more for searching than for insertion/deletion) goes a long way in directing you to the right container.

---

Related Topics