跳转至

3.5 栈和队列

是一个非常常见的数据结构, 它在计算机领域被广泛应用 比如操作系统会给每个线程创建一个栈来存储函数调用时各个函数的参数, 返回地址及临时变量等 栈的特点是后进先出, 最后被压入(push)栈的元素会第一个被弹出(pop), 面试题31, 栈的压入, 弹出序列

通常栈是一个不考虑排序的数据结构, 我们需要O(n)时间才能找到最大最小的元素. 如果想要在O(1) 时间内得到栈的最大值或最小值, 则需要对栈做特殊的设计, 面试题30, 包含min函数的栈

队列 是另外一种很重要的数据结构, 和栈不同的是, 队列的特点是先进先出, 即第一个进入队列的元素将会第一个出来. 面试题32

栈和队列虽然是特点针锋相对的数据结构, 但有意思的是它们却相互联系.

面试题9: 用两个栈实现队列

Question

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

template <typename T> class CQueue
{
public:
    CQueue();
    ~CQueue();

    void appendTail();
    T deleteHead();

private:
    stack <T> stack1;
    stack <T> stack2;
}

Tip

Answer

template <typename T>
void Queue<T>::appendTail(const T& val)
{
    stack1.push(val);
}

template <typename T>
T Queue<T>::deleteHead()
{
    if (stack2.size() <= 0)
    {
        if (stack1.size() <= 0)
            throw exception("Queue is empty");

        while (stack1.size() > 0)
        {
            T top = stack1.top();
            stack2.push(top);
            stack1.pop();
        }
    }
    T top = stack2.top();
    stack2.pop();
    return top;
}

void assert(bool b)
{
    static int count = 0;
    if (b)
        cout << "assert passed " << ++count << endl;
    else
        throw exception("assert failed");
}

完整代码: stackBuildQueue

本题考点:

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

用两个队列实现一个栈

Question

用两个队列实现一个栈

Tip

Answer

完整代码: QueueBuildStack