用栈实现队列

面试题09. 用两个栈实现队列

• 栈A用于加入元素
• 栈B用于反转元素。栈顶元素就是队头元素。删除队头时
  • 先判断 B 是否为空，只要 B 不为空， 无论 A 是否为空都是从 B 弹出元素
  • B为空时
    • 若A为空，则返回-1
    • 若A不为空，则将其转反转到B中，返回B的栈顶元素

class CQueue {
private:
    stack<int> A;
    stack<int> B;
public:
    CQueue() {

    }

    void appendTail(int value) {
        A.push(value);
    }

    int deleteHead() {
        if (!B.empty()) { // 只要 B 不为空， 无论 A 是否为空都是从 B 弹出元素
            int tmp = B.top();
            B.pop();
            return tmp;
        } else if (B.empty()) { // B为空时
            if (A.empty()) { // 若A为空，则返回-1
                return -1;
            } else {
                while (!A.empty()) { // 若A不为空，则将其转反转到B中
                    int cur = A.top();
                    A.pop();
                    B.push(cur);
                }
            }
        }
//        此时B被A逆序填充了，返回B的栈顶元素
        int tmp = B.top();
        B.pop();
        return tmp;
    }
};

class CQueue {
private:
    stack<int> A;
    stack<int> B;
public:
    CQueue() {

    }

    void appendTail(int value) {
        A.push(value);
    }

    int deleteHead() {
//        只要B不为空（不用管A是不是空的），则直接弹出
        if (!B.empty()){
            int tmp=B.top();
            B.pop();
            return tmp;
        }
// ***********以下是B为空的情况***********
//        B和A都为空，返回-1
        if (A.empty()){
            return -1;
        }
//      B为空。若A里有元素，则将其翻转到B中，返回B的栈顶元素
        while (!A.empty()){
            int tmp=A.top();
            A.pop();
            B.push(tmp);
        }
        int tmp=B.top();
        B.pop();
        return tmp;
    }
};

class CQueue(object):

    def __init__(self):
        self.A=[]
        self.B=[]


    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.A.append(value)


    def deleteHead(self):
        """
        :rtype: int
        """
        if self.B: return self.B.pop()
        if not self.B and not self.A: return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()



# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

232. 用栈实现队列

在上题的基础上增加了peek操作和判断是否为空操作

• peek：和pop函数非常类似，只需要把pop函数中相关的（B栈）弹出操作取消掉即可
• empty：若都为空，则返回true

class MyQueue {
private:
    stack<int> A;
    stack<int> B;
public:
    MyQueue() {

    }

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

    int pop() {
        if (!B.empty()) { // 只要 B 不为空， 无论 A 是否为空都是从 B 弹出元素
            int tmp = B.top();
            B.pop();
            return tmp;
        } else if (B.empty()) { // B为空时
            if (A.empty()) { // 若A为空，则返回-1
                return -1;
            } else {
                while (!A.empty()) { // 若A不为空，则将其转反转到B中
                    int cur = A.top();
                    A.pop();
                    B.push(cur);
                }
            }
        }
//        此时B被A逆序填充了，返回B的栈顶元素
        int tmp = B.top();
        B.pop();
        return tmp;
    }
//    peek：和pop函数非常类似，只需要把pop函数中相关的（B栈）弹出操作取消掉即可
    int peek() {
        if (!B.empty()) { // 只要 B 不为空， 无论 A 是否为空都是取B的栈顶元素
            int tmp = B.top();
//            B.pop();
            return tmp;
        } else if (B.empty()) { // B为空时
            if (A.empty()) { // 若A为空，则返回-1
                return -1;
            } else {
                while (!A.empty()) { // 若A不为空，则将其转反转到B中
                    int cur = A.top();
                    A.pop();
                    B.push(cur);
                }
            }
        }
//        此时B被A逆序填充了，返回B的栈顶元素
        int tmp = B.top();
//        B.pop();
        return tmp;

    }
//    若都为空，则返回true
    bool empty() {
        return A.empty() && B.empty();
    }
};