Queue. General concepts. Ways to implement the queue. Implementing a queue as a dynamic array
Contents
- 1. Queue data structure. Features of the implementation of the queue
- 2. Types of Queues
- 3. Ways to implement a Queue
- 4. Circular Queue
- 5. Queue with priorities. Implementation ways
- 6. An example implementation of a queue in the form of a dynamic array
- Related topics
Search other websites:
1. Queue data structure. Features of the implementation of the queue
A queue is a dynamic data structure that consists of a set of elements that are placed sequentially one after another. In this case, the addition of elements is carried out on the one hand, and the removal (stretching) on the other hand.
The queue works according to the FIFO principle – First In – First Out. Figure 1 shows the principle of operation of the queue.
Figure 1. The dynamic data structure Queue
One of the features of the queue is that in the queue some of the sequential elements can be occupied at a given moment in time (Figure 2).
Figure 2. A queue in which some of the elements are currently occupied
In everyday life, the use of a queue is quite common, for example:
- queue in the store;
- queue of documents for printing on a printer;
- a sequence of operators in the algorithm that are executed one after another;
- other cases.
⇑
2. Types of Queues
The following types of queues are distinguished:
- simple queue;
- circular queue. In such a queue, an element that comes from the beginning of the queue will be placed at its end;
- priority queue. In such a queue, elements are placed according to their priorities (weighting factors). The first item in the queue is the one with the highest priority.
Any type of queue may have a size limit (the number of elements in the queue).
⇑
3. Ways to implement a Queue
In the program, the queue can be implemented as:
- static array with size limit in the queue;
- dynamic array;
- singly linked list;
- doubly linked list.
⇑
4. Circular Queue
In the circular queue, the element that exits (is deleted) from the queue is placed at its end (Figure 3).
Figure 3. Circular Queue
Figure 4 shows the operation of the ring queue in the case when some of the elements are busy.
Figure 4. Circular Queue. The case when some of the elements are busy
Examples of circular queue:
- the movement of trams on a circular route;
- an event queue for processing them in Windows.
⇑
5. Queue with priorities. Implementation ways
В очереди с приоритетами элемент, имеющий наивысший приоритет, выходит (удаляется) первым. In the priority queue, each element is assigned a priority (weight coefficient).
The priority queue can be implemented in one of two ways:
- Queue with priority inclusion. In this case, the element that is added to the queue is immediately placed in it in accordance with its priority (Figure 5). When deleted, this item is simply pulled from the end of the queue;
- Queue with the priority exclusion. In this case, the new item is simply added to the end of the queue. And pulling an element from the queue is carried out according to its priority, that is, the element with the highest priority is pulled (Figure 6).
Figure 5. The queue with priority inclusion. Adding a new item according to its priority
Figure 6. Queue with priority exclusion. The item is added to the end of the queue, pulled according to priority
⇑
6. An example implementation of a queue in the form of a dynamic array
In the example, the Queue template class is declared, which implements the queue in the form of a dynamic array for some generalized type T.
The following fields and methods are implemented in the class:
- integer internal variable count – the number of elements in the queue;
- internal variable p is a pointer to type T. This pointer is an array of data forming a queue. An array element with index 0 is the beginning of the queue. The element with index count-1 is the end of the queue;
- default constructor;
- copy constructor Queue(const Queue&);
- copy operator operator=(const Queue&);
- method push() – adds an item to the end of the queue;
- destructor;
- method pop() – pulls the first element from the queue;
- method GetItem() – reads the first element from the queue without pulling it;
- method clear() – clears the queue;
- method IsEmpty() – checks if the queue is empty;
- method Get() – returns the number of elements in the queue;
- method print() – displays the queue on the screen.
The class code is as follows:
#include <iostream> #include <new> using namespace std; // Dynamic data structure Queue template <typename T> class Queue { private: T* p; // dynamic array int count; // number of items in the queue public: // default constructor Queue() { count = 0; // queue is empty } // copy constructor Queue(const Queue& obj) { // copy obj to the current object count = obj.count; try { // attempt to allocate memory for p p = new T[count]; // fill with values for (int i = 0; i < count; i++) p[i] = obj.p[i]; } catch (bad_alloc e) { // if no memory is allocated, then display the error text cout << e.what() << endl; count = 0; // create an empty queue } } // add item to the queue void push(T item) { T* p2; // declare an additional pointer p2 = p; // redirect an additional pointer to p try { // attempt to allocate a new piece of memory for p, but 1 more p = new T[count + 1]; // copy data for (int i = 0; i < count; i++) p[i] = p2[i]; // copy last item p[count] = item; // increase the number of items by 1 count++; // release previously allocated memory if (count > 1) delete[] p2; } catch (bad_alloc e) { // if no memory is allocated cout << e.what() << endl; // display error message // return old pointer to p p = p2; } } // pull the first item from the queue T pop() { if (count == 0) return 0; // fill in the item that is pulled from the queue T item; item = p[0]; // form a new piece of memory that is 1 less try { T* p2; // attempt to allocate memory p2 = new T[count - 1]; count--; // p=>p2 for (int i = 0; i < count; i++) p2[i] = p[i + 1]; // all but the first element are copied // release the section pointed to by p if (count > 0) delete[] p; // redirect p to p2 p = p2; // return item return item; } catch (bad_alloc e) { // if memory is not allocated, then return 0 cout << e.what() << endl; return 0; } } // operator function operator=(), // implements assignment of objects of type Queue Queue& operator=(const Queue& obj) { T* p2; // pointer to additional memory try { // attempt to allocate memory for p2 p2 = new T[obj.count]; // if the memory is allocated successfully, // you can free pre-allocated memory for p if (count > 0) delete[] p; // copy obj to the current object p = p2; // redirect p to p2 count = obj.count; // fill with values for (int i = 0; i < count; i++) p[i] = obj.p[i]; } catch (bad_alloc e) { // if the memory is not allocated, then display the corresponding message cout << e.what() << endl; } return *this; // return the current object } // destructor ~Queue() { if (count > 0) delete[] p; } // take the first element from the queue without pulling it T GetItem() { if (count > 0) return p[0]; else return 0; } // queue clearing void clear() { if (count > 0) { delete[] p; count = 0; } } // checking the existence of elements in the queue bool IsEmpty() { return count == 0; } // number items in the queue int GetN() { return count; } // method that displays queue void print(const char* objName) { cout << "Object: " << objName << endl; for (int i = 0; i < count; i++) cout << p[i] << "\t"; cout << endl; cout << "---------------------" << endl; } }; void main() { Queue<int> Q1; Q1.print("Q1"); Q1.push(5); Q1.print("Q1"); Q1.push(8); Q1.push(11); Q1.push(17); // Q1 = {5,8,11,17} Q1.print("Q1"); int d; d = Q1.GetItem(); cout << "d = " << d << endl; Q1.print("Q1"); Queue<int> Q2 = Q1; Q2.print("Q2"); Queue<int> Q3; Q3 = Q1 = Q2; Q1.push(333); Q2.push(555); Q1.print("Q1"); Q2.print("Q2"); Q3.print("Q3"); Q2.clear(); if (Q2.IsEmpty()) cout << "OK" << endl; else cout << "NO" << endl; cout << "n = " << Q3.GetN() << endl; }
The result of the program
Object: Q1 --------------------- Object: Q1 5 --------------------- Object: Q1 5 8 11 17 --------------------- d = 5 Object: Q1 5 8 11 17 --------------------- Object: Q2 5 8 11 17 --------------------- Object: Q1 5 8 11 17 333 --------------------- Object: Q2 5 8 11 17 555 --------------------- Object: Q3 5 8 11 17 --------------------- OK n = 4
⇑
Related topics
⇑