位操作技巧总结

栈实现队列

核心思想：使用两个栈。

#include <gtest/gtest.h>

#include <stack>

using namespace std;

class MyQueue {
 private:
  stack<int> s1, s2;

 public:
  void push(int v);
  int pop();
  int front();
  bool empty();
};

void MyQueue::push(int v) { s2.push(v); }

int MyQueue::pop() {
  auto v = front();
  if (v == -1) return -1;
  s1.pop();
  return v;
}

int MyQueue::front() {
  if (this->empty()) return -1;
  if (s1.empty()) {
    while (!s2.empty()) {
      s1.push(s2.top());
      s2.pop();
    }
  }
  return s1.top();
}

bool MyQueue::empty() { return s1.empty() && s2.empty(); }

TEST(Algo, myqueue) {
  MyQueue q;
  for (int i = 0; i < 10; i++) {
    q.push(i);
  }
  cout << "q.front(): " << q.front() << endl;
  while (!q.empty()) {
    cout << q.pop() << ", ";
  }
  cout << endl;
  cout << q.front() << ", " << q.pop() << endl;
}