This program implements two stacks using a single deque. Thanks to that each operation takes a constant number of deque operations.

using System;
using System.Text;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            DoubleStack ds = new DoubleStack();

            ds.PopLeft();
            ds.PopRight();

            ds.PushLeft("A");
            ds.PushRight("X");
            ds.ShowItems();

            ds.PushLeft("B");
            ds.PushLeft("C");
            ds.PushLeft("D");
            ds.ShowItems();

            ds.PopRight();
            ds.ShowItems();

            ds.PopLeft();
            ds.ShowItems();

            ds.PopLeft();
            ds.ShowItems();

            ds.PushRight("Y");
            ds.PushRight("Z");
            ds.ShowItems();

            ds.PopLeft();
            ds.ShowItems();

            ds.PopLeft();
            ds.ShowItems();

            ds.PopRight();
            ds.ShowItems();

            ds.PopRight();
            ds.ShowItems();

            Console.ReadKey();
        }

        class DoubleStack
        {
            Deque d;

            int L; // the size of the left stack
            int R; // the size of the right stack

            public bool IsLeftEmpty { get { return L == 0; } } 
            public int LeftSize { get { return L; } }

            public bool IsRightEmpty { get { return R == 0; } }
            public int RightSize { get { return R; } }

            public DoubleStack()
            {
                d = new Deque();
                L = 0;
                R = 0;
            }

            public void PushLeft(T item)
            {
                d.PushLeft(item);
                ++L;
            }

            public void PushRight(T item)
            {
                d.PushRight(item);
                ++R;
            }

            public T PopLeft()
            {
                // If empty, return a default value.
                if (L == 0)
                    return default(T);

                T item = d.PopLeft();
                --L;
                return item;
            }

            public T PopRight()
            {
                // If empty, return a default value.
                if (R == 0)
                    return default(T);

                T item = d.PopRight();
                --R;
                return item;
            }

            public void ShowItems()
            {
                d.ShowItems();
            }

            class Deque
            {
                private DoubleNode first;
                private DoubleNode last;
                private int N; // the size of deque

                public bool IsEmpty { get { return first == null; } } // the same as N == 0
                public int Size { get { return N; } }

                // Add an item to the left end.
                public void PushLeft(T item)
                {
                    DoubleNode oldFirst = first;
                    first = new DoubleNode();
                    first.Item = item;
                    first.Next = oldFirst;
                    first.Prev = null;

                    // Adjust the last item if necessary.
                    if (oldFirst == null) // check if this is the first item pushed
                        last = first;
                    else
                        oldFirst.Prev = first; // otherwise, update the former first node

                    ++N;
                }

                // Add an item to the right end.
                public void PushRight(T item)
                {
                    DoubleNode oldLast = last;
                    last = new DoubleNode();
                    last.Item = item;
                    last.Next = null;
                    last.Prev = oldLast;

                    // Adjust the first item if necessary.
                    if (oldLast == null) // check if this is the first item pushed
                        first = last;
                    else
                        oldLast.Next = last; // otherwise, update the former last node

                    ++N;
                }

                // Remove an item from the left end.
                public T PopLeft()
                {
                    if (first == null)
                        return default(T);

                    T item = first.Item;

                    first = first.Next;

                    if (first != null)
                        first.Prev = null;
                    else
                        last = null; // there are no more nodes in the list

                    return item;
                }

                // Remove an item from the right end.
                public T PopRight()
                {
                    if (first == null)
                        return default(T);

                    T item = last.Item;

                    last = last.Prev;

                    if (last != null)
                        last.Next = null;
                    else
                        first = null; // there are no more nodes in the list

                    return item;
                }

                // ShowItems traverses all the items in the list.
                public void ShowItems()
                {
                    if (first == null)
                    {
                        Console.Write(".");
                    }
                    else
                    {
                        for (DoubleNode node = first; node != null; node = node.Next)
                        {
                            if (node.Prev == null) Console.Write(". ");
                            Console.Write("{0} ", node.Item.ToString());
                            if (node.Next == null) Console.Write(". ");
                        }
                    }

                    Console.WriteLine();
                }

                private class DoubleNode
                {
                    public T Item { get; set; }
                    public DoubleNode Prev { get; set; }
                    public DoubleNode Next { get; set; }

                    public override string ToString() { return (Item == null ? "null" : Item.ToString()); }
                }
            }
        }
    }
}

Output:

. A X .
. D C B A X .
. D C B A .
. C B A .
. B A .
. B A Y Z .
. A Y Z .
. Y Z .
. Y .
.