两个栈实现一个队列

  • push：直接push进stIn

  • pop：

    • 如果stOut不为空，直接pop

    • 如果stOut为空，先将stIn中所有元素push进stIn，再pop

      1. // push的时候直接push进st1，pop的时候如果st2不为空，直接出栈；如果st1为空，将st1的元素全部push进st2后，再出栈。
      2. class CQueue {
      3. public:
      4. CQueue() {
      6. }
      8. void appendTail(int value) {
      9.    stIn.push(value);
      10. }
      12. int deleteHead() {
      13.    if (stOut.empty()) {
      14.        if (stIn.empty()) return -1; 
      15.        while (!stIn.empty()) {
      16.            stOut.push(stIn.top());
      17.            stIn.pop();
      18.        }
      19.    }
      20.    int num = stOut.top();
      21.    stOut.pop();
      22.    return num;
      23. }
      25. int top() {
      26.    int num = deleteHead();  // 代码复用
      27.    stOut.push(num);
      28.    return num;
      29. }
      31. int empty() {
      32.    return (stIn.empty() && stOut.empty());
      33. }
      34. private:
      35. stack<int> stIn;
      36. stack<int> stOut;
      37. };

      队列实现栈

      pop实现，将队列队首的元素一个个弹出重新放入队列的队尾，只留下原来队列中的最后一个元素弹出
      push就是直接将元素插入队尾

      class MyStack {
public:
MyStack() {

}

void push(int x) {
   que.push(x);
}

int pop() {
   if (que.empty()) return -1;
   int cnt = que.size() - 1;
   while (cnt--) {
       que.push(que.front());
       que.pop();
   }
   int res = que.front();
   que.pop();
   return res;
}

int top() {
   int res = pop();
   que.push(res);
   return res;
}

bool empty() {
   return que.empty();
}
queue<int> que;
};