A queue is a FIFO data structure . It is also a sequence of elements but the element that is pushed first is taken out first. Conceptually this is similar to a real life queue in which people stand in a line and the first person is served first. The operations on the queue are called "enQueue" and "deQueue" .
We can implement a queue using an array.. One simple approach is to keep 2 indexes called head and tail and keep adding elements to the tail and removing from the head.
array
head tail
However it's possible when we reach the end of the array with the tail index we might have removed some elements from the head so our array can still have space.
Ex1
Implement a queue using an array with head tail indexes. Mark the queue as full only when there is no space in the array.
#include <iostream>using namespace std; //------------------------------------------------------ class MyQueue1 { public: int arr1[5] ; int head = -1 ; int tail = -1 ; int noItems = 0 ; int capacity = 0 ; MyQueue1() { capacity = 5 ; } void enQueue( int value ) { } int deQueue() {
} void print() { int index ; if ( noItems == 0 ) return ; cout << "----Start of Print---" << endl ; int endIndex = head + noItems ; for( index = head ; index < endIndex ; index++ ) { cout << arr1[ index % capacity ] << " " ; } cout << endl ; cout << "----End of Print---" << endl ; } };
int main() { MyQueue1 queObj ; queObj.enQueue( 1) ; queObj.enQueue( 2) ; queObj.enQueue( 3) ; queObj.enQueue( 4 ) ; queObj.enQueue( 5) ; cout << queObj.noItems << endl ; queObj.print() ; cout << queObj.deQueue() << endl ; queObj.enQueue( 6 ) ; queObj.print() ; return 0 ; }
Output:
$ ./a.exe
5
----Start of Print---
1 2 3 4 5
----End of Print---
1
----Start of Print---
2 3 4 5 6
----End of Print---
Ex2
Modify the doubly linked list to include a tail pointer pointing to the last element in the list. Use that as the underlying implementation for a queue.
File: "ex_2.cpp"
#include <iostream> using namespace std; //------------------------------------------------------class Node { public: int data; Node* next ; Node* previous ; Node( int value ) { data = value ; next = NULL ; previous = NULL ; } Node( int value , Node* nextP) { data = value ; next = nextP ; previous = NULL ; } Node( int value , Node* nextP , Node* previousP ) { data = value ; next = nextP ; previous = previousP ; } }; //------------------------------------------------------ class MyDoublyLinkedList { public: Node* head = NULL ; Node* tail = NULL ; int noItems = 0 ; void add( int value ) { //TO DO //set value for tail if ( head == NULL ) { Node* ptrNode = new Node( value ) ; head = ptrNode ; } else { Node* newNode = new Node( value, head ) ; head->previous = newNode ; head = newNode ; } noItems++ ; } void remove( int value ) { Node* temp = head ; while ( temp != NULL ) { if( temp->data == value ) { if ( temp == head ) //very first element { if ( head->next != NULL ) head->next->previous = NULL ; head = head->next ; delete temp ; } else { temp->previous->next = temp->next ; if ( temp->next != NULL ) temp->next->previous = temp->previous ; delete temp ; } break ; } //if( temp->data == value ) temp = temp->next ; } //while } int removeAtEndOfList( ) { //TO DO int result ; if ( noItems == 0 ) throw "List is empty" ; return result ; } bool search( int value ) { Node* temp = head ; while ( temp != NULL ) { if ( temp->data == value ) return true ; temp = temp->next ; } //while return false ; } void insert( int value ) { if ( head == NULL ) { Node* ptrNode = new Node( value ) ; head = ptrNode ; } else { Node* temp = head ; //Node* previous = NULL ; while ( temp != NULL ) { if ( value < temp->data ) //found a place { if ( temp == head ) //need to set the head { Node* n1 = new Node( value , temp ) ; //if ( head->next != NULL ) head->previous = n1 ; head = n1 ; return ; } else { Node* n1 = new Node( value , temp, temp->previous ) ; temp->previous->next = n1 ; temp->previous = n1 ; return ; } } //if ( value < temp->data ) //previous = temp ; //reached the end //place the element at the end if ( temp->next == NULL ) { Node* n1 = new Node( value , NULL, temp) ; temp->next = n1 ; break ; } temp = temp->next ; } //while //if we reach here then element needs to be placed at the //end. //Node* n1 = new Node( value ) ; //previous->next = n1 ; } //if ( head == NULL ) } //void insert( int value ) void print( ) { Node* temp = head ; cout << "Start of print: --------------" << endl ; while ( temp != NULL ) { cout << temp->data << " " ; if ( temp->previous != NULL ) cout << "Previous:" << temp->previous->data << endl ; else cout << "Previous is null :" << endl ; temp = temp->next ; } //while cout << endl ; cout << "End of print: --------------" << endl ; } void reverseList() { //Node* previous = NULL ; Node* ptr1 = head ; Node* t1 ; while ( ptr1 != NULL ) { t1 = ptr1->next ; ptr1->next = ptr1->previous ; ptr1->previous = t1 ; if ( t1 == NULL ) { head = ptr1 ; break ; } ptr1 = t1 ; } //head = previous ; } }; //------------------------------------------------------ class MyQueue2 { public: MyDoublyLinkedList list1 ; int noItems = 0 ; void enQueue( int value ) { list1.add( value ) ; noItems++ ; } int deQueue() { int result ; if ( noItems == 0 ) { throw "Queue is empty." ; } noItems-- ; result = list1.removeAtEndOfList() ; return result ; } void print() { list1.print() ; } }; int main() { MyQueue2 queObj ; queObj.enQueue( 1) ; queObj.enQueue( 2) ; queObj.enQueue( 3) ; queObj.enQueue( 4 ) ; queObj.enQueue( 5) ; cout << queObj.noItems << endl ; queObj.print() ; cout << queObj.deQueue() << endl ; queObj.enQueue( 6 ) ; queObj.print() ; return 0 ; }
Output:
$ ./a.exe
5
Start of print: --------------
5 Previous is null :
4 Previous:5
3 Previous:4
2 Previous:3
1 Previous:2
End of print: --------------
1
Start of print: --------------
6 Previous is null :
5 Previous:6
4 Previous:5
3 Previous:4
2 Previous:3
End of print: --------------
Ex3
Use 2 stacks to implement a queue. Call the stacks 1 and 2 . Initially they are both empty. Add an item to stack 1 . Add another item to stack 1. Now if there is a pop operation then move all the elements from stack 1 to stack 2 except the last. Give the last element from stack 1 as the result and move all the elements from stack2 back to stack 1.