2020-11-14 05:31:11 +03:30
|
|
|
/**
|
|
|
|
|
* @file
|
|
|
|
|
* @brief Implementation of Linear [Queue using array]
|
|
|
|
|
* (https://www.geeksforgeeks.org/array-implementation-of-queue-simple/).
|
|
|
|
|
* @details
|
|
|
|
|
* The Linear Queue is a data structure used for holding a sequence of
|
|
|
|
|
* values, which can be added to the end line (enqueue), removed from
|
|
|
|
|
* head of line (dequeue) and displayed.
|
|
|
|
|
* ### Algorithm
|
2020-11-22 23:05:01 +05:30
|
|
|
* Values can be added by increasing the `rear` variable by 1 (which points to
|
|
|
|
|
* the end of the array), then assigning new value to `rear`'s element of the
|
|
|
|
|
* array.
|
|
|
|
|
*
|
|
|
|
|
* Values can be removed by increasing the `front` variable by 1 (which points
|
|
|
|
|
* to the first of the array), so it cannot reached any more.
|
|
|
|
|
*
|
2020-11-14 05:31:11 +03:30
|
|
|
* @author [Pooja](https://github.com/pooja-git11)
|
|
|
|
|
* @author [Farbod Ahmadian](https://github.com/farbodahm)
|
|
|
|
|
*/
|
2020-11-22 23:05:01 +05:30
|
|
|
#include <array> /// for std::array
|
2024-11-04 17:38:54 +05:30
|
|
|
#include <cstdint>
|
2020-11-22 23:05:01 +05:30
|
|
|
#include <iostream> /// for io operations
|
2020-03-01 20:43:26 +05:30
|
|
|
|
2020-11-22 23:05:01 +05:30
|
|
|
constexpr uint16_t max_size{10}; ///< Maximum size of the queue
|
2020-03-01 20:43:26 +05:30
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
/**
|
|
|
|
|
* @namespace data_structures
|
|
|
|
|
* @brief Algorithms with data structures
|
|
|
|
|
*/
|
|
|
|
|
namespace data_structures {
|
2020-03-01 20:43:26 +05:30
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
/**
|
|
|
|
|
* @namespace queue_using_array
|
|
|
|
|
* @brief Functions for [Queue using Array]
|
2020-11-22 23:05:01 +05:30
|
|
|
* (https://www.geeksforgeeks.org/array-implementation-of-queue-simple/)
|
|
|
|
|
* implementation.
|
2020-11-14 05:31:11 +03:30
|
|
|
*/
|
|
|
|
|
namespace queue_using_array {
|
2020-03-01 20:43:26 +05:30
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
/**
|
2020-11-22 23:05:01 +05:30
|
|
|
* @brief Queue_Array class containing the main data and also index of head and
|
|
|
|
|
* tail of the array.
|
2020-11-14 05:31:11 +03:30
|
|
|
*/
|
2020-03-01 20:43:26 +05:30
|
|
|
class Queue_Array {
|
2020-11-22 23:05:01 +05:30
|
|
|
public:
|
2020-11-14 05:31:11 +03:30
|
|
|
void enqueue(const int16_t&); ///< Add element to the first of the queue
|
2020-11-22 23:05:01 +05:30
|
|
|
int dequeue(); ///< Delete element from back of the queue
|
|
|
|
|
void display() const; ///< Show all saved data
|
|
|
|
|
private:
|
|
|
|
|
int8_t front{-1}; ///< Index of head of the array
|
|
|
|
|
int8_t rear{-1}; ///< Index of tail of the array
|
|
|
|
|
std::array<int16_t, max_size> arr{}; ///< All stored data
|
2020-03-01 20:43:26 +05:30
|
|
|
};
|
|
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
/**
|
|
|
|
|
* @brief Adds new element to the end of the queue
|
|
|
|
|
* @param ele to be added to the end of the queue
|
|
|
|
|
*/
|
2020-11-22 23:05:01 +05:30
|
|
|
void Queue_Array::enqueue(const int16_t& ele) {
|
2020-11-14 05:31:11 +03:30
|
|
|
if (rear == arr.size() - 1) {
|
2020-03-01 20:43:26 +05:30
|
|
|
std::cout << "\nStack is full";
|
|
|
|
|
} else if (front == -1 && rear == -1) {
|
2020-11-14 05:31:11 +03:30
|
|
|
front = 0;
|
|
|
|
|
rear = 0;
|
2020-03-01 20:43:26 +05:30
|
|
|
arr[rear] = ele;
|
2020-11-14 05:31:11 +03:30
|
|
|
} else if (rear < arr.size()) {
|
|
|
|
|
++rear;
|
2020-03-01 20:43:26 +05:30
|
|
|
arr[rear] = ele;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
/**
|
|
|
|
|
* @brief Remove element that is located at the first of the queue
|
|
|
|
|
* @returns data that is deleted if queue is not empty
|
|
|
|
|
*/
|
2020-03-01 20:43:26 +05:30
|
|
|
int Queue_Array::dequeue() {
|
2020-11-14 05:31:11 +03:30
|
|
|
int8_t d{0};
|
2020-03-01 20:43:26 +05:30
|
|
|
if (front == -1) {
|
|
|
|
|
std::cout << "\nstack is empty ";
|
|
|
|
|
return 0;
|
|
|
|
|
} else if (front == rear) {
|
2020-11-14 05:31:11 +03:30
|
|
|
d = arr.at(front);
|
2020-03-01 20:43:26 +05:30
|
|
|
front = rear = -1;
|
|
|
|
|
} else {
|
2020-11-14 05:31:11 +03:30
|
|
|
d = arr.at(front++);
|
2020-03-01 20:43:26 +05:30
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return d;
|
|
|
|
|
}
|
|
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
/**
|
|
|
|
|
* @brief Utility function to show all elements in the queue
|
|
|
|
|
*/
|
|
|
|
|
void Queue_Array::display() const {
|
2020-03-01 20:43:26 +05:30
|
|
|
if (front == -1) {
|
|
|
|
|
std::cout << "\nStack is empty";
|
|
|
|
|
} else {
|
2020-11-14 05:31:11 +03:30
|
|
|
for (int16_t i{front}; i <= rear; ++i) std::cout << arr.at(i) << " ";
|
2020-03-01 20:43:26 +05:30
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
} // namespace queue_using_array
|
|
|
|
|
} // namespace data_structures
|
2020-03-01 20:43:26 +05:30
|
|
|
|
2020-11-14 05:31:11 +03:30
|
|
|
/**
|
|
|
|
|
* @brief Main function
|
|
|
|
|
* @details
|
|
|
|
|
* Allows the user to add and delete values from the queue.
|
|
|
|
|
* Also allows user to display values in the queue.
|
|
|
|
|
* @returns 0 on exit
|
|
|
|
|
*/
|
|
|
|
|
int main() {
|
|
|
|
|
int op{0}, data{0};
|
|
|
|
|
data_structures::queue_using_array::Queue_Array ob;
|
2020-03-01 20:43:26 +05:30
|
|
|
|
|
|
|
|
std::cout << "\n1. enqueue(Insertion) ";
|
|
|
|
|
std::cout << "\n2. dequeue(Deletion)";
|
|
|
|
|
std::cout << "\n3. Display";
|
|
|
|
|
std::cout << "\n4. Exit";
|
2020-11-14 05:31:11 +03:30
|
|
|
while (true) {
|
2020-03-01 20:43:26 +05:30
|
|
|
std::cout << "\nEnter your choice ";
|
|
|
|
|
std::cin >> op;
|
|
|
|
|
if (op == 1) {
|
|
|
|
|
std::cout << "Enter data ";
|
|
|
|
|
std::cin >> data;
|
|
|
|
|
ob.enqueue(data);
|
|
|
|
|
} else if (op == 2) {
|
|
|
|
|
data = ob.dequeue();
|
|
|
|
|
std::cout << "\ndequeue element is:\t" << data;
|
|
|
|
|
} else if (op == 3) {
|
|
|
|
|
ob.display();
|
|
|
|
|
} else if (op == 4) {
|
|
|
|
|
exit(0);
|
|
|
|
|
} else {
|
|
|
|
|
std::cout << "\nWrong choice ";
|
|
|
|
|
}
|
|
|
|
|
}
|
2020-11-14 05:31:11 +03:30
|
|
|
|
|
|
|
|
return 0;
|
2020-03-01 20:43:26 +05:30
|
|
|
}
|
