How to Construct or Return the Underlying Deque from a Stack

How can I construct or return the underlying deque from a stack?

You'll need to do it manually:

while (!stk.empty())
{
    deq.push_back(stk.top());
    stk.pop();
}

Converting between STL stack and deque

stack is just an container adaptor, so you can just pass deque object to it to use it as a container:

std::deque<int> my_deque;
// Do something with deque here
std::stack<int> s(my_deque);

To covert in other direction, you can use constructor with the iterators:

I am not sure if you can do the direct conversion vice-versa (other than using my_deque directly). Only thing that I can think of is following:

std::deque<int> other_deck;
// Construct new stack:
std::stack<int> new_stack(other_deck);
// use std::swap
std::swap(new_stack, old_stack);

Now the other_deck should be filled with the from the old_stack.

Exchanges the contents of the container adaptor with those of other. Effectively calls using std::swap; swap(c, other.c);

Edit It seems that swap is just swapping the underlying containers, and not the container's contents, so this will not work.

C++: using deque member functions inside a class stack

You can indeed use directly the deque methods like that:

template<class T>
class Stack {

    public: 
        Stack(): s() {   // <-- creating an empty deque s
        }

        ~Stack() {                          
        }

        //Member functions
        int nitems() const { return s.size() ; }
        bool empty() const { return s.empty() ; }

        void push_back(const T& c) {
            s.push_back(c) ;  
        }

        const T& back() {
            return s.back();  
        }

        void pop_back() { 
            if (empty()) {
                std::cout << "Stack::pop() Error: stack is empty" << std::endl ;
            }
            s.pop_back();
        }

    private:
        std::deque<T> s ;
};

Why are deques used as the underlying container for stacks by default, when vectors would do the trick?

I don't see any reason to prefer deques.

A reason to prefer deque that applies to the stack use case is that individual push back has worst case constant complexity compared to vector whose individual push back is linear in worst case (it has amortised constant complexity over multiple push backs). This was particularly significant prior to C++11 when reallocating vector had to copy the elements which could be very expensive. Consider case where the elements themselves are long strings.

Another reason to prefer deques is that they release memory as they shrink. Vectors don't. Hence, if you have a stack that temporarily grows large, then shrinks and remains small for the rest of the execution, then an underlying vector would be wasting a lot of memory.

Historically, when STL was designed and thus when the default was chosen, there used to also be issues with very large vectors because the size of the address space didn't exceed (significantly, or at all) the amount of memory (this was before 64 bit processing was common). The consequence of the limited address space was that memory fragmentation would make it expensive or impossible to allocate large contiguous blocks of memory that a large vector would require. Furthermore, the way that vector grows by deallocating old buffers is a behaviour that causes such fragmentation.

What is underlying data structure of std::deque and how does it's iterator work?

The key point is that a deque is made of several chunks of contiguous memory.

When you add an element in the first position then there are two situations:

Either the first chunk has still place to add an element:

 |   |   | first element | second element | .... | ...
       ^
       inserted element can be placed here

Or there is no place in the first chunk, then the inserted element is placed in a different chunk that was empty before the insertion.

In both cases, the elements that were already in the container need not be moved in memory. Hence references to them are still valid. Iterators are different, because they need addtional book-keeping (for example to reach the next chunk when you increment an iterator to the last element in a contiguous chunk). The same holds for inserting an element at the end. Inserting elements in the middle however requires to rearrange already existing elements.

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.

How do I correctly pass converting constructor from an std::queue through to the underlying std::deque?

If you can't change CustomAlloc code as Ted Lyngmo suggested, the alternative is to define CustomQueue as a subclass of std::queue:

template<typename T, typename Alloc>
struct CustomQueue : std::queue<T, CustomDeque<T, Alloc>>
{
    CustomQueue(Alloc& alloc) :std::queue<T, CustomDeque<T, Alloc>>(STLAdaptor<T, Alloc>(alloc)) {}
};

Now you can construct it by passing merely the allocator:

int main()
{
    CustomAlloc customAlloc(3000000);

    CustomDeque<int, CustomAlloc> customDeque(customAlloc);

    CustomQueue<int, CustomAlloc> customQueue(customAlloc);

    customQueue.push(5);

    return 0;
}

This code was tested on VS 2019.

How do you implement a Stack and a Queue in JavaScript?

var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

taken from "9 JavaScript Tips You May Not Know"

---

Related Topics