// Created by DarkRanger // implementing a queue // a data structure used for FiFo strategy // Author : DarkRanger // Requirements : all the functions or operattions should occur and consume constant time #include #include // Linked List Used to implement the data structure /* * empty * size * front * back * push_back * pop_front */ // .h header file template // template -> Note 5 class Queue // * Note 1 { public : // * [client interface] Queue(); // * only declarations ~Queue(); Queue( Queue& ) = delete; // * note 2 Queue operator = ( Queue& ) = delete; bool empty(); // Note 3 std::size_t size(); T& front(); T& back(); void push( T ); void pop(); private : struct Node{ // Note 6 T data; Node* next = 0; void doSomething(T param); // declaration }; std::size_t size_; Node* first; // * do not coment, use self descriptive names Node* last; // Note 7 }; /* Note 1 class names start with Uppercase - Use a good [naming convention] widely used. ClassName void doSomethng() bool isTrue ENUM_NAME general rule: when you feel you cannot name properly something this means there is something wrong in your design */ /* Note 2 [delete copy ctor] and assignement operator if you dont want it, this way you prevent the compiler to make default ones. And do it publicly.. you will get better error messages */ /* Note 3 [client interface] look how is clear what this class can do.. here we have the full list of the methods with parameter types, all the stuffs the client needs to know * The same apply to the constructor.. suppose you have a constructor with parameters.. MyClass( int value, char sign ...) The client will immediately know everything he needs to work with this class */ /* Note 5 use templates to make your class more flexible.. the type T will be the data type.. to create a Queue of ints just do: Queue myQueue; */ /* Note 6 Good Design! using a nested private struct inside the class prevents clients from using Node outside. */ /* Note 7 Put data members all togeter at the end, they should appear all in the constructor for initialization. */ // define outside the class // .cpp file /* ! ! ! warning ! ! ! because we are using templates the definition must be in the same file (header) option 1 : write it in the same file like in this case option 2 : put the implementation in a .hxx ("extention" file) and include it in the header file. ok this is a bit triky.. feel free to leave the template and just focus on a int Queue. */ template Queue::Queue(): size_( 0 ), first( nullptr ), last( nullptr ){} template bool Queue::empty(){ // ...... } template void Queue::Node::doSomething( T param ){ // ..... definition } class queue { // blueprint node for queue private: struct Node { int data; Node* next; // ctor init Node(int data) { this->data = data; next = NULL; } }; private: // queue attributes Node* Head; // front of queue Node* Tail; // rear of queue int size; // length of queue public: // ctor member initializer queue() :size(0) { Head = NULL; Tail = NULL; } public: // basic operations // function to push element into queue void enqueue(int data) { if (Head == NULL && Tail == NULL) { Node* newNode= new Node(data); Head = newNode; Tail = newNode; size++; } else { // size must be atleast one Node* newNode = new Node(data); // last node connects to new Tail->next = newNode; Tail = newNode; size++; } } //deq : function to pop an element // returns front data int dequeue() { if (Head == NULL) return -1; // returnable data int Data = Head->data; Node* temp = Head; Head = Head->next; delete temp; size--; return Data; } public: // additional functionality void FIFO_size() { if (Head == NULL) std::cout << "Empty queue\n"; else { std::cout << "\nFirst In : " << Head->data; // new line std::cout << std::endl; std::cout << "Last In : " << Tail->data; } // new line std::cout << std::endl; std::cout << "Size : "<< size; std::cout << std::endl; } // function to traverse the queue void ShowQueue() { if(Head->next == NULL) return; // temp ref to head Node* temp = Head; while (temp != NULL) { std::cout << temp->data; std::cout << " "; temp = temp->next; } } // to check if list is empty bool isEmpty() { if (Head == NULL && Tail == NULL) return true; return false; } // return front element int Front() { if (Tail == NULL) return -1; // exception else return (Head->data); } }; // end of queue class int main () { // creating queue on the stack queue newQueue; // inserting elemetns for(int a=100;a>=0;a=a-10) { newQueue.enqueue(a); } // 10 elements inserted :displaying newQueue.ShowQueue(); newQueue.FIFO_size(); // now popping some elemetns int b = newQueue.dequeue(); int c = newQueue.dequeue(); std::cout << std::endl; // new line newQueue.ShowQueue(); newQueue.FIFO_size(); std::cout << "first pop : " << b << std::endl; std::cout << "last pop : " << c << std::endl; return 0; } /* Main Function Output: . queue is created . queue is pushed with 10 entities . queue is displayed . queue is decreased by one element from front by dequeue function and value is stored in b and c (b should be 10 as front of queue was 10(int)) . queue is shoed again with one laess entity .FIFO_size function is used to show other data regarding queue */

queue @DarkRanger