C++ Queue with Linked-list

Question

Question:

struct QueueNode {
    int data;
    QueueNode *next;
};

do

int size() const: return data size.
bool is_empty() const:
void enqueue(int val): add a new node to the end of the list.
void dequeue(): remove the node which head point to.
int top() const: return the data which will be dequeue next.

This is my code

class Queue {
    private:
        QueueNode *_head = NULL, *_tail = NULL;
        int _size = 0;
    public:
        int size() const {
            if (! is_empty())
              return _size;
        }
        bool is_empty() const {
            if (_size == 0)
                return true;
            else
                return false;
        }
        void enqueue(int val) {
            QueueNode *n = new QueueNode;
            n -> data = val;
            n -> next = NULL;
            if (is_empty()) {
                _head = n;
                _tail = n;
                _size ++;
            }
            else {
                _tail -> next = n;
                _tail = n;
                _size ++;
            }
        }
        void dequeue() {
            QueueNode *temp;
            temp = _head;
            if (! is_empty()) {
                _head = _head -> next;
                delete temp;
                _size --;
            }
        }
        int top() const {
            if (! is_empty())
                return _head -> data;
        }
};

The Online Judge displayed wrong answer. I think the "int top() const" is wrong. But I have no idea. Ask for help. Thanks.

What do size() and top() return when the queue is empty? — kaylum
_head = _tail = n; should be written as separate assignments. top() and size() don't return anything if the queue is empty. — dave
Er, that's not how methods work. If you define it to return something it must do so for every case. Otherwise the result is undefined behaviour. — kaylum

Professor of Stupidity Professor of Stupidity · Accepted Answer · 2021-03-30T08:47:10

As @Kaylum pointed out, you have not returned the size of the queue if it is empty. It should return 0 in that case, but you have no else part in your size() method.

This should probably work:

int size() const {
            if (! is_empty())
              return _size;
            else
              return 0;
        }

EDIT: Similarly you should return something from top() too. If you're using an online judge, then it would have specified what to return in case of empty queues. Read the constraints again please, I guess it would help. It would most probably some exception or some default integer which would be required by the online judge to judge an empty queue's output.

C++ Queue with Linked-list

2 Answers