Implementing queue using an array

[gevCplus]

Hello guys. I am trying to implement a queue by using an array. However my code has some flaws so please any piece of advice would be really helpfull.

#include <iostream>
#include <algorithm>

using namespace std;

class queue {
private:
    int data[100];  
    int top;         
                    
    int tail;
    int capacity;
public:
    queue() {};
    queue(int c) : tail(0), top(0), capacity(c) {};   
    bool empty() { return top == 0; };  
    void enqueue(int x) {};   
    int dequeue() {};        
};

void queue::enqueue(int x) {
    if (capacity == tail) {
        cout << "queue is full";
        return;
    }
    else 
        data[tail] = x;
        tail++;
        return
                     
}

int queue::dequeue() {  
    if (top == tail) {
        cout << "queue is empty";
        return;
    }
    else {
        for (int i = 0; i < tail - 1; i++){
            data[i] = data[i + 1];
        }
    
    tail--;
    }
    return; 
}

int main()
{
    queue q1;  
    int i;
    for (i = 0; i < 100; i++) {
        q1.enqueue(i);  
    }
    while (!q1.empty()) {    
        cout << q1.dequeue() << endl;  
    }

    return 0;
}

[Repeater]

You aren't setting capacity in your default queue.

int queue::dequeue() should return an int. It does not.

Line 29 is missing a semi-colon.

[gevCplus]

Thank you Repeater. I corrected these and my code behaves abnormal in a sense that it does not print anything. Any advice?

#include <iostream>
#include <algorithm>

using namespace std;

class queue {
private:
    int data[100];  
    int top;         
                    
    int tail;
    int capacity;
public:
    queue() {};
    queue(int c) : tail(0), top(0), capacity(c) {};
    void set_capacity(int c) { tail = 0; top = 0; capacity = c; };
    int get_capacity() { return capacity; };
    int get_top() { return top; };
    int get_tail() { return tail; };
    bool empty() { return top == 0; };
    void enqueue(int x);   
    int dequeue();        
};

void queue::enqueue(int x) {
    if (capacity == tail) {
        cout << "queue is full";
        return;
    } 
    data[tail] = x;
    tail++;
    return;
}

int queue::dequeue() {  
    if (top == tail) {
        cout << "queue is empty";
        return 1;
    }
    else {
        for (int i = 0; i < tail - 1; i++){
            data[i] = data[i + 1];
        }
    
    tail--;
    }
    return data[tail--];
}

int main()
{
    queue q1;
    q1.set_capacity(100);
    int i;
    for (i = 0; i < 100; i++) {
        q1.enqueue(i);  
    }
    while (!q1.empty()) {    
        cout << q1.dequeue() << endl;  
    }

    return 0;
}

[seeplus]

Why does dequeue need to shuffle elements? To enqueue, increment top mod 100 (size of array), to dequeue increment tail mod 100. To show an array, display from top to tail incrementing mod 100.

Consider:

#include <iostream>

using namespace std;

class queue {
private:
	static const size_t quemax {100};

	int data[quemax] {};
	size_t top {};
	size_t tail {};
	size_t capacity {quemax};
	size_t noelems {};

public:
	queue() {};
	queue(size_t c) : capacity(c > quemax ? quemax : c) {};

	void set_capacity(size_t c) { tail = 0; top = 0; noelems = 0; capacity = c > quemax ? quemax : c; };
	size_t get_capacity() const { return capacity; }
	//size_t get_top() const { return top; }
	//size_t get_tail() const { return tail; }
	size_t get_noelems() const { return noelems; }
	bool empty() const { return noelems == 0; };
	void enqueue(int x);
	int dequeue();
};

void queue::enqueue(int x) {
	if (noelems == capacity) {
		cout << "queue is full\n";
		return;
	}

	data[top] = x;
	top = (top + 1) % capacity;
	++noelems;
}

int queue::dequeue() {
	if (empty()) {
		cout << "queue is empty\n";
		return 1;
	}

	const auto d {data[tail]};
	tail = (tail + 1) % capacity;
	--noelems;
	return d;
}

int main()
{
	queue q1;

	q1.set_capacity(100);

	for (int i = 0; i < 103; ++i)
		q1.enqueue(i);

	while (!q1.empty())
		cout << q1.dequeue() << '\n';
}

[TheIdeasMan]

Any advice?

Learn to use a debugger :+)
It's necessary skill, might as well start now.

[dhayden]

        for (int i = 0; i < tail - 1; i++){
            data[i] = data[i + 1];

I'm sorry to say this, but your basic algorithm is wrong. You shouldn't move any items when you dequeue, you should just adjust tail.

The idea here is that top always points to the place where you will insert the next item and tail points to the next item that you will dequeue. So as a first approximation:

enqueue(item) { data[top++] = item; }
item dequeue() { return data[tail++]; }

So you add items at positions 1,2,3,4... and you remove them in the same order.

There are several things wrong with this first approximation:
- enqueue assumes that data has infinite space.
- dequeue assumes that the queue isn't empty.
- it wastes space. once you've enqueued and dequeued the item at position k, that memory is never used again.

To fix this, you use a circular buffer. Suppose you have space for 100 items, when enqueue gets to the 100th item, you reset top back to zero. By that point, you hope that that first item has been dequeued so that you can reuse position zero.

Dequeue() does the same thing: when you dequeue item last item, you reset tail to zero.

Now you just have to worry about when the queue is full and when it's empty. It's full when you would try to enqueue into an existing item, and it's empty if you try to dequeue an item that doesn't exist. To code these, first make sure you have clearly defined exactly what top and tail represent. Does top point to the location where the next item goes, or does it point to the location of the most recently inserted item? Ditto with tail. Once you define what they are, you can do the checks for full and empty queue.

[gevCplus]

Thank you all very much for your precious posts!