用兩個棧實現隊列，兩個棧實現隊列

用兩個棧實現隊列，兩個棧實現隊列

題目：用兩個棧實現一個隊列。隊列的聲明如下，請實現它的兩個函數appendTail和deleteHead，分別完成在隊列尾部插入結點和在隊列頭部刪除結點的功能。

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

解題思路：

插入操作在stack1中進行，刪除操作在stack2中進行，如果stack2為空，則將stack1中的所有元素轉移到stack2中。

#include<stack>
#include<stdio.h>
#include<iostream>

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)
    //當stack2為空時才可以將stack1中的數移過來 
    {
        while(stack1.size()>0)
        {
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }

    if(stack2.size() == 0)
        //throw new exception("queue is empty");
        exit(1);

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

    return head;
}


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

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');
    
    
    queue.appendTail('a');
    queue.appendTail('b');
    queue.appendTail('c');
    queue.appendTail('d');
    int length = 4;
    while(length > 0)
    {
        printf("%c ", queue.deleteHead());
        --length ;
    }
    return 0;
}