随笔-13  评论-0  文章-2  trackbacks-0
队列的实现(链式结构) Alpha 1.0

 

  1/**
  2        Queue (Liked structure)
  3        Version: 1.0
  4        Member function as follow:
  5        size()
  6        front()        // the head element
  7        back()         // the rear element
  8        push(T)        // inset an elm
  9        pop()        // delete the last elm
 10        empty()         // if it is an empty list
 11        print()
 12
 13        Use C++ template
 14        @author fleap
 15        data: 2009/03/20
 16**/
 17
 18// queue.h
 19#ifndef QUEUE_H
 20#define QUEUE_H
 21
 22#include<iostream>
 23#include<string>
 24
 25template<typename T>
 26struct Node
 27{
 28    T   data;
 29    Node* link;
 30    Node():link(NULL){}
 31};
 32
 33template<typename T>
 34class queue
 35{
 36public:
 37    queue();
 38    ~queue();
 39    int Size()const { return size; }
 40    T front() const { return head->link->data; }
 41    T back()const { return rear->data; }
 42    bool empty() const{ return front == rear; }
 43    void push(const T&);
 44    void pop();
 45    void print()const;
 46private:
 47    Node<T>* head;
 48    Node<T>* rear;
 49    int size;
 50};
 51
 52#endif
 53
 54// queue.cpp
 55// #include"queue.h"
 56
 57using namespace std;
 58
 59template<typename T> queue<T>::queue()
 60{
 61    head = new Node<T>;
 62    rear = head;
 63    size = 0;
 64}
 65
 66template<typename T> queue<T>::~queue()
 67{
 68    while(size--)
 69    pop();
 70}
 71
 72template<typename T> void queue<T>::push(const T& one)
 73{
 74    Node<T>* node = new Node<T>;
 75    node->data = one;
 76    Node<T>* p = new Node<T>;
 77    p = head;
 78    while(p != rear)
 79    p = p -> link;
 80    p -> link = node;
 81    rear = node;
 82    size++;
 83}
 84
 85template<typename T> void queue<T>::pop()
 86{
 87    Node<T>* p = new Node<T>;
 88    p = head;
 89    while( p->link != rear )
 90    p = p -> link;
 91    rear = p;
 92    p = p ->link;
 93    delete p;
 94    rear -> link = NULL;
 95    size--;
 96}
 97
 98template<typename T> void queue<T>::print() const
 99{
100    Node<T>* p = new Node<T>;
101    p = head -> link;
102    while(p != NULL)
103    {
104        cout << p -> data <<" ";
105        p = p-> link;
106    }
107    cout << endl;
108}

// Test function
int main()
{
        using namespace std;
    queue<int> que;
    cout << "----------------Display the queue program-----------------------" << endl;
    cout << "\nInitial the queue,please input the number of element to push stack "<< endl;
    cout << "number = " ;
    int number;
    cin >> number;
    cout << "Secondly input the number in the following\n" << endl;
    int temp;
    for( int i = 0; i < number; i++ )
    {
        cin >> temp;
        que.push(temp);
    }
    cout << "You Input As Follow" << endl;
    que.print();
    cout << "head:" << que.front() << " rear:" << que.back() << endl;
    cout << "Would you like to display the pop functionYes or No" << endl;
    string answer;
    cin >> answer;
    if( answer == "yes" || answer == "YES" )
    {
        que.pop();
        que.print();
        cout << "head:" << que.front() << " rear:" << que.back() << endl;
    }
    cout <<"-----------------------------------------------------------------" << endl;
    system("pause");
    return 0;
}
posted on 2009-03-20 02:33 亦夏 阅读(462) 评论(0)  编辑 收藏 引用 所属分类: DataStruct

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 亦夏