Having trouble getting started on an assignment for my c++ class. I understand how stacks/queues work, but what I don't quite understand is how they work as adapters, i've read plenty of sites but none really have given me a good example of how they work when implemented using a container. The project we were given asks us to use the deque class to store 2 stacks.One stack updates its elements with push_front( ) / pop_front( ), and the other stack uses push_back( ) / pop_back( ).
My original idea:
-create a stack class, and #include <deque>
-create a deque named dualstk to use to store the stacks.
-create the methods/constructors used for stacks.

Overall the main confusion I myself am having is how to go about this, I don't really need code, I just need a better explanation/algorithm or something to help me understand how to work this. Any help would be greatly appreciated! Thanks!

have each of the two stacks to store a reference to a std::deque.
initialize them to refer to the same std::deque.
write a wrapper class to hold the two stacks.

template< typename T > struct dual_stack
{

  struct first_stack
  {
    explicit first_stack( std::deque<T>& seq ) : sequence(seq) {}
    // implement stack members
    // push/pop => sequence.push/pop_front()
    private : std::deque<T>& sequence ;
  };

  struct second_stack
  {
    explicit second_stack( std::deque<T>& seq ) : sequence(seq) {}
    // implement stack members
    // push/pop => sequence.push/pop_back()
    private : std::deque<T>& sequence ;
  };


  dual_stack() : _first_stack(sequence), _second_stack(sequence) {}

  first_stack& first() { return _first_stack ; }
  second_stack& second() { return _second_stack ; }
  // const versions of the above, other members.

  private: 
    std::deque<T> sequence ;

    first_stack _first_stack ;
    second_stack _second_stack ;
};

Lets assume you have Stack1 (push_back, pop_back) and Stack2 (push_front, pop_front)

Say you want to enqueue 1,2,3

Lets enqueue the numbers onto Stack1 using push_back

Stack1 looks like : back |3|2|1| front

Stack2 looks like: back |EMPTY| front

Now you want to dequeue a number. So lets pop_back all the numbers from Stack1 and push_front them onto Stack2

Stack1 looks like: back |EMPTY| front

Stack2 looks like: back |3|2|1| front

Now you can dequeue the number using pop_front on Stack2.

Now say you want to enqueue 10 .

Stack1 looks like: back |10| front

Stack2 looks like: back |3|2|1| front

So now you will keep enqueueing the elements onto Stack1 using push_back and dequeueing them from Stack2 using pop_front. Once Stack2 is empty, if you need to dequeue further elements, then you need to pop_back all the elements from Stack1 and add them onto Stack2.

I hope that helps.

This article has been dead for over six months. Start a new discussion instead.