6

I want to be able to convert a std::stack<> to a std::deque<>. Is there a straightforward conversion?

BeeBand
  • 10,953
  • 19
  • 61
  • 83

5 Answers5

19

It is possible to access the underlying container without copying the data, but it requires a certain amount of evil. The container is exposed as a protected member, called c, which allows shenanigans such as this:

template <typename T>
class Shenanigans : private stack<T>
{
public:
    explicit Shenanigans(stack<T>& victim) : victim(victim)
    {
        swap(victim);
    }

    ~Shenanigans()
    {
        swap(victim);
    }

    using stack<T>::c;

private:
    stack<T>& victim;
};

int main()
{
    stack<int> s;
    s.push(42);

    {
        Shenanigans<int> sh(s);
        // The deque is accessible as sh.c, but the stack is temporarily empty.
        cout << "Size: " << s.size() << " Data: " << sh.c.front() << "\n";
    }

    // The stack is restored.
    cout << "Size: " << s.size() << " Data: " << s.top() << "\n";
}

Of course a far, far better solution is to choose a container that meets your needs.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
6

You'll need to do it manually:

while (!stk.empty())
{
    deq.push_back(stk.top());
    stk.pop();
}
R Samuel Klatchko
  • 74,869
  • 16
  • 134
  • 187
  • Ah, ok - thanks. Was just wondering if I could do it without having to make a copy of the stack, and popping it into a deque. – BeeBand Jun 13 '10 at 18:59
  • 5
    @Stephen: Except `deque` has no such function. :) – GManNickG Jun 13 '10 at 19:27
  • @GMan: Holy crap, you're right. Makes sense, given that you wouldn't know which way to grow it. I guess you could create the deque with `std::deque deq(stk.size());`, but then you can't use `push_back`. – Stephen Jun 13 '10 at 23:15
3

You need to pop all the elements off of the stack and into a different container.

If you need to do this, perhaps std::stack is the wrong data structure for your use case.

James McNellis
  • 348,265
  • 75
  • 913
  • 977
  • Well - its so that I can compare stacks. The `equal` function in the standard lib, needs a container with `begin()` and `end()` functions. And I need to easily see the reverse of my stacks as well, so I thought about converting them to deques. – BeeBand Jun 13 '10 at 19:00
  • 2
    @BeeBand: Why not just use a `std::deque` instead of a `std::stack` then? It can be used for the same purpose, just instead of `top()`, `push()`, and `pop()`, you need to use `back()`, `push_back()`, and `pop_back()`. – James McNellis Jun 13 '10 at 19:02
  • @James - because the pop, push interface is very useful. I need `stack` functionality (i.e. `push`, `pop`, and `top` ) and don't want to call `push_back()` or `pop_back()`. – BeeBand Jun 13 '10 at 19:04
  • 3
    @BeeBand: But you're *not* just using `stack` functionality. If you need to see elements in reverse, it's not a stack. Just use a `deque`. – GManNickG Jun 13 '10 at 19:08
  • 2
    @BeeBand: The naming of member functions is an odd reason to choose one data structure over another. Given your use case, `std::stack` is the wrong data structure. The right answer is to use a `std::deque`. If the names _really_ bother you that much, then write non-member wrapper functions that do what you want; you can call those whatever you'd like. – James McNellis Jun 13 '10 at 19:08
  • @James... re. non member wrapper, how might I do that for a `deque`- do I not need to write an entire adaptor around a `deque`? I didn't realise you could just wrap up functions in the STL independently.. sorry - probably a whole other question in itself. – BeeBand Jun 13 '10 at 19:19
  • @BeeBand: Just write a function template `top()` that takes a deque as a parameter and returns the result of calling `pop_back()` on the deque. – James McNellis Jun 13 '10 at 19:28
  • 1
    @BeeBand: I think he means for example `template void push(T &con, const U &val) { con.push_back(val); }` etc. But by all means you could take the source for `stack` in your implementation, and use it as the basis to write your own complete container adaptor, with `push`, `pop`, `top`, `begin` and `end`. – Steve Jessop Jun 13 '10 at 19:29
  • 1
    "its so that I can compare stacks" - if you're just comparing stacks (of the same type), then they have an `operator==` overload. Comparing a stack to some other container is the tricky part, or seeing it in reverse. – Steve Jessop Jun 13 '10 at 19:34
  • @Steve, hmm. I didn't realise `stack` had an `operator==` overload. Well yes, actually I am going to have to iterate over the stacks also, a container adaptor might be a good idea in that case. – BeeBand Jun 13 '10 at 19:39
2

I think if you need this, you would be better off using deque in the first place, instead of a stack. There is no way of getting at the underlying storage used by the stack adaptor, if that is what you are asking.

  • @Neil, that's exactly what I was asking yes. I see. well. The stack interface fits my needs - its just that I need to be able to compare the items in the stacks. – BeeBand Jun 13 '10 at 19:02
  • @BeeBand Really, a deque pretty much works like a stack anyway - you just say pop_front and push_back instead of pop and push. –  Jun 13 '10 at 19:05
  • @Neil - this is true. I just like the small function names, and the idea of `back` and `front` make things confusing for what I'm doing. – BeeBand Jun 13 '10 at 19:08
  • @Neil - actually yes you are right. I should be using a `deque` instead. – BeeBand Jun 13 '10 at 19:10
  • 5
    "The stack interface fits my needs - its just that..." this is another way of saying, "The stack interface does not fit my needs" ;-) – Steve Jessop Jun 13 '10 at 19:30
  • @Steve. :) yes ok this is true, hehe. – BeeBand Jun 13 '10 at 19:39
0

As all other answers have pointed out, this should never be part of the final program flow, and if your program needs the features of a deque, you should not use a stack. That being said, I can see the rare convenience for debugging and unit testing with special types to e.g. print the contents inside the stack / queue without having to alter the original container or create a copy.

An alternative evil to swapping the data back and forth is to reinterpret the std::stack as an equivalent type which exposes the underlying container. This allows to e.g. provide a simple const std::deque<T>& asDeque(const std::stack<T>&)

#include <deque>
#include <iostream>
#include <stack>

// Expose underlying container
template <typename T>
class StackHacker : std::stack<T> {
    public:
        using std::stack<T>::c;
};

// Hide the "StackHacker" wrapper
template <typename T>
const std::deque<T>& asDeque(const std::stack<T>& s) {
    return reinterpret_cast<const StackHacker<T>*>(&s)->c;
}

// Example usage to print the content of the stack
template <typename T>
void printStackContent(const std::stack<T>& s) {
    for (const T& elem : asDeque(s)) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::stack<int> s;
    s.push(40);
    s.push(41);
    s.push(42);

    // The stack contains some data.
    std::cout << "Size: " << s.size() << " Data: " << s.top() << std::endl;

    // Inspect the content via the underlying deque
    std::cout << "Content of stack: " << std::endl;
    printStackContent(s);

    return 0;
}
Cedric
  • 278
  • 1
  • 9