Stack:                     
  void PushBack(int x)
  int PopBack()

Queue:
  void PushBack( int x )
  int PopFront()

DeQueue:
  void PushBack( int x )
  void PushFront( int x )
  int PopFront()
  int PopBack()

List:
  iterator Next(iterator)
  iterator Prev(iterator)
  Value(iterator)

----------------------------

const int N = (int)1e5;

int st = 0, end = 0, a[N];
// [st, end) st % N, (st + 1) % N .... (end - 1) % N
// size = end - st <= N
// if (end == N - 1) end = 0;

PushFront( int x ) { st = (st + N - 1) % N; a[st] = x; }
PushBack( int x )  { a[end++] = x; end %= N; }
int PopFront()     { int res = a[st++]; st %= N; return res; }

// 1. a[(st + i) % N] (random access)
// 2. size <= N

// a[st + rand() % (end - st)] // rand() = 0..