Under (method 2):
if (!q.empty() && q.front().second == cnt_removed)
q.pop_front();
cnt_removed++;

Correct me if I'm wrong, but this should either not include the empty check at all, or increment cnt_removed only if the queue is nonempty.