栈/队列

Que7: 用 2 个栈实现队列

实现 
    void push(const T&); 
    T topAndPop();

Que 类:

成员数据: 2 个 std::stack
2个成员函数: 转调 2个 stack 的 memFunc

push: 放 stk1

topAndPop 思想: 1个 elem 想出队, 必须依次经过 stk1 -> stk2

// Queue.h
#pragma once
#include <stack>
#include <exception>

template <typename T> 
class Queue
{
public:
    Queue();
    ~Queue();
    
    void push(const T& elem);

    T topAndPop();

private:
    std::stack<T> stk1;
    std::stack<T> stk2;
};

template <typename T> 
Queue<T>::Queue(){}

template <typename T> 
Queue<T>::~Queue(){}

// push: 放 stk1
template<typename T> 
void Queue<T>::push(const T& elem)
{
    stk1.push(elem);
} 

// topAndPop 思想: 1个 elem 想出队, 必须依次经过 stk1 -> stk2 
template<typename T> 
T Queue<T>::topAndPop()
{
    // (1) 若 stk2 空, 将 stk1 中所有 elem 取出, 放 stk2
    if(stk2.size() <= 0)
    {
        while( stk1.size() > 0 )
        {
            T& data = stk1.top();
            stk2.push(data);
            stk1.pop();
        }
    }

    if(stk2.size() == 0)
        throw new std::exception("queue is empty");
    
    // (2) 从 stk2 取 & pop 
    T head = stk2.top();
    stk2.pop();

    return head;
}

// Queue.cpp
#include "Queue.h"
#include <queue>

// QueueWithTwoStacks.cpp

#include "Queue.h"

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

int main(int argc, char* argv[])
{
    Queue<char> queue;

    queue.push('a');
    queue.push('b');
    queue.push('c');

    char head = queue.topAndPop();
    Test(head, 'a');

    head = queue.topAndPop();
    Test(head, 'b');

    queue.push('d');
    head = queue.topAndPop();
    Test(head, 'c');

    queue.push('e');
    head = queue.topAndPop();
    Test(head, 'd');

    head = queue.topAndPop();
    Test(head, 'e');
}