用两个栈实现队列

#include <cassert>
#include "List.h"
//链表栈
class Stack{
    List L;
public:
    void push(const T& t){L.insert_front(t);}
    T top(){return L.getHead();}
    void pop(){L.erase(L.getHead());}
    bool empty(){return L.empty();}
    void clear(){L.clear();}
    int size(){return L.size();}
};
////////////顺序栈
//////////class Stack1{
//////////    T a[10];
//////////    int num;
//////////public:
//////////    Stack1():num(0){}
//////////    void push(const T& t){
//////////        if(full())
//////////            throw "stack overflow";
//////////        a[num++]=t;
//////////    }
//////////    T top(){
//////////        if(empty())
//////////            throw "no top stack";
//////////        return a[num-1];
//////////    }
//////////    void pop(){
//////////        if(empty())
//////////            throw "empty stack";
//////////        num--;
//////////    }
//////////    bool empty(){return num==0;}
//////////    bool full(){return num==10;}
//////////    int size(){return num;}
//////////};
class Queue{
    Stack s1;
    Stack s2;
public:
    void appendTail(const T& t){
        s1.push(t);
    }
    void deletehead(){
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.top());
                s1.pop();
            }
        }
        assert(s2.size()>0);
        s2.pop();
    }
    T top(){
        if(s2.empty()){
            while(!s1.empty()){            
                s2.push(s1.top());
                s1.pop();
            }
        }
        assert(s2.size()>0);
        return s2.top();
    }
    bool empty(){return s1.empty()&&s2.empty();}
};
int main()
{
    Queue s;
    s.appendTail(1.0);
    s.appendTail(2.0);
    s.deletehead();
    s.appendTail(3.0);
    s.appendTail(4.0);
    s.deletehead();
    s.deletehead();
    s.appendTail(5.0);
    cout.setf(ios::showpoint);
    cout.precision(10);
    while(!s.empty()){
        cout<<s.top()<<" "<<endl;
        s.deletehead();
    }
    system("pause");
    return 0;
}

posted on 2011-05-20 13:18 Hsssssss 阅读(90) 评论(0)  编辑 收藏 引用 所属分类: C++代码


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年5月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿

文章分类

文章档案

收藏夹

搜索

最新评论