剑指offer笔记面试题9----用两个栈实现队列

佚名 6年前 (2019-10-17) 算法 2197人围观抢沙发百度已收录

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead,分别完成在尾部插入节点和在队列头部删除节点的功能。

测试用例：

往空的队列里添加、删除元素。
往非空的队列里添加、删除元素。
连续删除元素直至队列为空。

测试代码：

void test(char actual, char expected){
    if(actual == expected)
        printf("test passed.\n");
    else 
        printf("test failed.\n");
}

本题考点：

考查应聘者对栈和队列的理解。
考察应聘者写与模板相关的代码的能力。
考查应聘者分析复杂问题的能力。本题解法的代码虽然只有二十几行，但形成正确的思路却不容易。应聘者能否通过具体的例子分析问题，通过画图的手段把抽象的问题形象化，从而解决这个相对复杂的问题，是能否顺利通过面试的关键。

实现代码：

//==========================Queue.h=======================
#pragma once

#include <stack>
#include <stdexcept>

using namespace std;

template <typename T> class CQueue{
public:
    CQueue(void);
    ~CQueue(void);
    void appendTail(const T& node);
    T deleteHead();
private:
    stack<T> stack1;
    stack<T> stack2;
};

template <typename T> CQueue<T>::CQueue(void){}
template <typename T> CQueue<T>::~CQueue(void){}
template <typename T> void CQueue<T>::appendTail(const T& element){
    stack1.push(element);
}
template <typename T> T CQueue<T>::deleteHead(){
    if(stack2.size() <= 0){
        while(stack1.size() > 0){
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }
    if(stack2.size() == 0)
        throw logic_error("queue is empty");
    T head = stack2.top();
    stack2.pop();
    return head;
}
//==================QueueWithTwoStacks.cpp=================
#include "Queue.h"
#include <cstdio>

int main(){
    CQueue<char> queue;
    queue.appendTail('a');
    queue.appendTail('b');
    queue.appendTail('c');
    char head = queue.deleteHead();
    test(head, 'a');
    head = queue.deleteHead();
    test(head, 'b');
    queue.appendTail('d');
    head = queue.deleteHead();
    test(head, 'c');
    queue.appendTail('e');
    head = queue.deleteHead();
    test(head, 'd');
    head = queue.deleteHead();
    test(head, 'e');
}