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
– kaylum, Commented Mar 30, 2021 at 8:31
_head = _tail = n; should be written as separate assignments. top() and size() don't return anything if the queue is empty. — perivesta
– perivesta, Commented Mar 30, 2021 at 8:33
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
– kaylum, Commented Mar 30, 2021 at 8:34

Aman Kumar · Accepted Answer · 2021-03-30 08:47:10Z

0

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.

answered Mar 30, 2021 at 8:47

Aman Kumar

3241 gold badge9 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Evg Over a year ago

Why not just return _size; without if-else at all?

Aman Kumar Over a year ago

@Evg exactly my thoughts, but I tried to make minimal changes to OP's code

d901203 · Accepted Answer · 2021-03-30 08:57:48Z

0

My answer. Thanks Everyone.

class Queue {
    private:
        QueueNode *_head = NULL, *_tail = NULL;
        int _size = 0;
    public:
        int size() const {
            if (! is_empty())
              return _size;
            else
              return 0;
        }
        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 = _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;
        }
};

answered Mar 30, 2021 at 8:57

d901203

318 bronze badges

1 Comment

Evg Over a year ago

1) is_empty() could be written as return _size == 0;. 2) size() could be just return _size;. 3) Prefer nullptr to NULL. 4) top() is still broken. 5) Destructor is missing. 6) ...

Collectives™ on Stack Overflow

C++ Queue with Linked-list

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related