#include<iostream>
#include<deque>
#include<stack>
#include<queue>
using namespace std;

/*
 * deque ( double ended queue )
 * these allow fast inserts at either end
 * and allow random access
 *
 * stack and queue are just adapters to
 * deque, but you may specify a list or vector
 *
 */

// overloading the output stream operator
ostream & operator << ( ostream & ost, const deque<int> & d )
{
    for ( deque<int>::const_iterator i = d.begin() ; i != d.end() ; ++i )
        ost << *i << " ";
    return ost;
}

int main()
{
    deque<int> d;

    // I can treat it like a queue
    for ( int i = 0 ; i < 10 ; ++i )
        d.push_back( i );

    while ( !d.empty() )
    {
        cout << d.front() << " ";
        d.pop_front();
    }
    cout << endl;

    // I can treat it like a stack
    for ( int i = 0 ; i < 10 ; ++i )
        d.push_front( i );

    while ( !d.empty() )
    {
        cout << d.front() << " ";
        d.pop_front();
    }
    cout << endl;

    for ( int i = 0 ; i < 10 ; ++i )
        d.push_front( i );
    d.resize( 15, -86 );

    cout << d << endl;

    // it supports random access
    cout << d[5] << endl;
    deque<int>::iterator di = d.begin() + 3;
    cout << *di << endl;

    // removing an element is not part of the interface
    // d.remove( di );
    di = d.erase ( di );
    d.erase ( di + 5, di + 9 );
    cout << d << endl;

    sort( d.begin(), d.end() );
    cout << d << endl;

    // there are also adapters for stack and queue
    // the interfaces are different
    stack<int> s;
    for ( int i = 0 ; i < 10 ; ++i )
        s.push( i );

    while ( !s.empty() )
    {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    queue<int> q;
    for ( int i = 0 ; i < 10 ; ++i )
        q.push( i );

    while ( !q.empty() )
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    return 0;
}