Thread: queue linked implementation

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    12

    queue linked implementation

    template <class T>
    class Queue
    {
    public:
    Queue();
    Queue(const Queue&);
    ~Queue();
    Queue& operator=(const Queue&);
    int size() const;
    bool empty() const;
    T& front();
    T& back();
    void push(const T&);
    void pop();
    void dispValues();
    protected:
    class Node
    {
    public:
    Node(const T& x, Node* next=0) : _(x), _next(next) {}
    T _;
    Node* _next;
    };
    Node *_front, _back;
    int _size;
    };

    template <class T> Queue<T>::Queue() : _back(0), _size(0)
    {
    }

    template <class T>
    Queue<T>::Queue(const Queue& s) : _back(0), _size(s._size)
    {
    if (_size==0) return;
    Node* pp=0;
    for (Node* p = s._back; p; p = p->_next)
    if (p==s._back) pp = _back = new Node(p->_);
    else pp = pp->_next = new Node(p->_);
    }

    template <class T> Queue<T>::~Queue()
    {
    while (_back)
    {
    Node* p=_back;
    _back = _back->_next;
    delete p;
    }
    }

    template <class T> int Queue<T>::size() const
    {
    return _size;
    }

    template <class T> bool Queue<T>::empty() const
    {
    return _size==0;
    }

    template <class T> T& Queue<T>::front()
    {
    return _front->_;
    }

    template <class T> T& Queue<T>::back()
    {
    return _back->_;
    }

    template <class T> void Queue<T>:ush(const T& x)
    {
    if (_size==0) _front = _back = new Node(x);
    else _back = _back->_next = new Node(x);
    ++_size;
    }

    template <class T> void Queue<T>:op()
    {
    Node* p = _front;
    _front = _front->_next;
    delete p;
    --_size;
    }


    template <class T>
    void Queue<T>:: dispValues()
    {
    cout << "front = " << _front << endl;
    cout << "back = " << _back << endl;
    cout << "size = " << _size << endl;
    for ( Node* p = _front; p; p = p->_next)
    cout << p->_ << endl;
    }

    template <class T>
    void print(const Queue<T> &ss)
    {
    Queue<T> s = ss;
    cout << "size = " << s.size();
    if (s.size() > 0)
    {
    cout << ", back=" << s.back() << ": (" << s.front();
    s.pop();

    while (!s.empty())
    {
    cout << "," << s.front();
    s.pop();
    }
    cout << ")";

    }
    cout << endl;
    }

    void main()
    {
    Queue<string> s; print(s);
    s.push("first"); print(s);
    s.push("second"); print(s);
    s.push("third"); print(s);
    s.pop(); print(s);
    s.push("fourth"); print(s);
    s.push("fifth"); print(s);
    s.push("sixth"); print(s);
    s.pop(); print(s);
    // s.dispValues();
    }


    //need help with debuggin this file

  2. #2
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    Have you tried to create a non-template version first (it's easier to debug)?

    1) Node *_front, _back; should be


    Node *_front, *_back;

    2) If you want your print function to pop it's way through your queue without destroying your original queue you'll have to implement your overloaded = operator so that it assigns the queues properly or call the copy constructor in your print function instead of the assignment operator and ensure that your copy constructor initialises your _front pointer.
    zen

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Queue implementation
    By kolliash in forum C Programming
    Replies: 1
    Last Post: 06-01-2008, 08:25 AM
  3. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM
  5. Linked List implementation of Queue
    By tdm2792 in forum C Programming
    Replies: 5
    Last Post: 11-04-2001, 04:04 PM