В тему: http://codeforces.net/blog/entry/5309

stack<int> top, tail;

int q_size() {
  return top.size() + tail.size();
}

int q_push(int x) {
  tail.push(x);
}

void q_transform() {
  if (top.empty()) {
    while (!tail.empty()) {
      top.push(tail.top());
      tail.pop();
    }
  }
}

void q_pop() {
  q_transform();
  top.pop();
}

int q_front() {
  q_transform();
  return top.top();
}

Вроде все ок. Если найдете ошибки, пишите. Извините за говнокод, но идея вроде ясна. Если нет, то распишу подробнее.

UPD. Не успел, уже ответили(

Здесь описана идея работающая за амортизированное О(1).

http://e-maxx.ru/algo/stacks_for_minima

Смотрите раздел "Модификация очереди. Способ 2"

UPD: Опередили

Огромное спасибо всем ответившим :)

Мне казалось, я больше тебя не встречу после того случая, но судьба решила по-другому...