Data structures: the Queue

One again the queue is an intuitive form of data structure which has a bunch of uses in computers and apps.

What is a queue?
A queue consists of an array where you can input elements on the back and remove them from the front in the form of a FIFO* system.

What can you do with a queue?

• Create: begin the queue data structure, reserve space.
• Queue: put a new element at the end of the queue (and keep it moving forward if its priority is bigger that the others' in a priority queue).
• Unqueue: remove the element at the front of the queue (depending on the implementation, this would also give said element as the return object).
• First: examine the element the front of the stack.
• Size: gives the number of queued objects
• Empty: checks whether the stack has no elements.

Advantages

• Easy to implement
• Simple
• Small chance of causing errors
• Able to implement priorities
• Good for sequential systems.

Setbacks

• Only object we can check is the frontal
• Objects take a long time to be back on the front
• If using priorities, some low-priority objects may be forever at the back of the queue.
• Very sequential.

Sequential programming is common. An operating system for instance answers to the requests of its applications in the form of a prioritized queue, in the way that first which comes is the first served (unless apps have more urgency than others).

Implementation

I will implement a priority queue for integers instead of templates for simplicity's sake. Still templates can be used, and I'll still program it in C++. I want to implement it including priorities so the lesson can be appreciated in full.

/*
 * queue.h
 *
 *  Created on: 02/06/2012
 *      Author: Daniel
 *
 *  this snippet of code is free to use.
 */
#include <iostream>

#ifndef QUEUE_H_
#define QUEUE_H_

template<typename T>
class Queue {
private:
    T *_queue; //_s are so as not to have ambiguity with the methods.
    int *_priorities;

    int _size;
    int _endPos;
    bool _priority;

public:

    Queue(bool hasPriority) { //Will implement queues with and without priorities
        _size = 10;
        _queue = new T[_size];
        _priority = hasPriority;
        if (_priority) {
            _priorities = new int[_size];
        }
        _endPos = 0;
    }

    Queue(int startSize, bool hasPriority) {
        _size = startSize;
        _queue = new T[_size];
        _priority = hasPriority;
        if (_priority) {
            _priorities = new int[_size];
        }
        _endPos = 0;
    }

    bool queue(T value) {
        if (_endPos >= _size) {
            resize(_size + 1);
        }

        if (!_priority) {
            _queue[_endPos] = value;
            _endPos++;
            return true;
        }
        std::cout << "lacks priority argument - not added\n";
        return false;

    }

    void queue(T value, int priority) {
        if (_endPos >= _size) {
            resize(_size + 1);
        }

        if (!_priority) {
            std::cout
                    << "Warning: queue hasn't got priority enabled - no need to add a priority argument when queueing"
                    << std::endl;
            _queue[_endPos] = value;
        }

        else {
            //The idea is to keep pulling elements back until we reach an element with higher priority than us.
            for (int i = _endPos; i >= 0; i--) {
                if (i == 0 || _priorities[i-1] < priority) {
                    _queue[i] = value;
                    _priorities[i] = priority;
                    i = 0;
                } else {
                    _queue[i] = _queue[i - 1];
                    _priorities[i] = _priorities[i - 1];
                }
            }
        }

        _endPos++;
    }
    T unqueue() {
        if (!empty()) {
            T first = _queue[0];

            for (int i = 0; i < _endPos - 1; i++) { //one of the less optimal things
                _queue[i] = _queue[i + 1];
            }

            if (_priority) {
                for (int i = 0; i < _endPos - 1; i++) { //one of the less optimal things
                    _priorities[i] = _priorities[i + 1];
                }
                _priorities[_endPos] = 0;

            }

            _queue[_endPos] = 0;

            _endPos--;

            return first;
        }
        std::cout << "Queue empty\n";
        return -1;

    }
    T first() {
        return _queue[0];
    }
    int size() {
        return _endPos;
    }
    bool empty() {
        return _endPos <= 0;
    }
    bool resize(int newSize) { //again, no resizing that can result in data loss
        if (newSize <= _endPos) {
            std::cout << "Won't resize queue - may result in data loss"
                    << std::endl;
            return false;
        }

        T *newQueue = new int[newSize];
        for (int i = 0; i < _endPos; i++) {
            newQueue[i] = _queue[i];
        }
        if (_priorities) {
            int *newPriorities = new int[newSize];
            for (int i = 0; i < _endPos; i++) {
                newPriorities[i] = _priorities[i];
            }
            _priorities = newPriorities;
        }

        _queue = newQueue;
        _size = newSize;

        return true;
    }

};

#endif /* QUEUE_H_ */

*Annex: Terminology

-First In First Out (FIFO) is a term used to describe a system where the first elements that have been stored will also be the first to be used.

------

This will start to get complicated, at least implementation-wise. Lists are the next!