キュー実装スタック、スタック実装キュー


2つのスタックを使用して1つのキューを実装
#include 
#include 
#include 
using namespace std;

template<typename T>class Queue
{
public:
    Queue(void){};
    ~Queue(void){};

    void appendTail(const T& node);
    T delateHead();
private:
    stack stack1;
    stack stack2;
};

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

template<typename T> 
T Queue::delateHead()
{
    if (stack2.size() <= 0)
    {
        while (stack1.size() > 0)
        {
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }
    if (stack2.size() == 0)
        throw new exception("queue is empty");

    T head = stack2.top();
    stack2.pop();
    return head;
}

2つのキューを使用してスタックを1つ実現
template<typename T>class Stack
{
public:
    Stack(void){};
    ~Stack(void){};
    void push(const T& node);
    T pop();
private:
    queue queue1;
    queue queue2;
};

template<typename T> 
void Stack::push(const T& node)
{
    if (queue2.empty())
        queue1.push(node);
    else
        queue2.push(node);
}

template<typename T> 
T Stack::pop()
{
    T Front ;
    if(queue1.empty())
    {
        while (queue2.size() > 1)
        {
            queue1.push(queue2.front());
            queue2.pop();
        }
        if(queue2.size() < 1)
            throw new exception("Stack is empty");

        Front = queue2.front();
        queue2.pop();
    }
    else if(queue2.empty())
    {
        while (queue1.size() > 1)
        {
            queue2.push(queue1.front());
            queue1.pop();
        }
        if(queue1.size() < 1)
            throw new exception("Stack is empty");
        Front = queue1.front();
        queue1.pop();
    }
    return Front;
}