Queue are very basic data structures in computer science and there are multiple variation of Queue. They simplest one being FIFO (http://en.wikipedia.org/wiki/FIFO) queue. The other well known queue is priority queue (http://en.wikipedia.org/wiki/Priority_queue ).
FIFO queues can be implemented using array or linked list and each implementation has some advantage over the other.
E.g.:
- If implemented using arrays. dequeue and enqueue operation be performed in O(1), but adds the limitation on the queue size.
- Linked list, overcome the size limitation and keeps the dequeue and enqueue operation to 0(1).
- We can use modern advance data structures such as vectors ( Dynamic arrays ) to implement queues, but whenever the existing capacity for vector is reached, a new vector of size of 2n is created and all the elements from old vector is copied to newly allocated vector.
Implementing FIFO queue is always preferred to be implemented in Linked List, but some time candidates are asked to implement a variation of the FIFO.
E.g.: 1) Use Array/Vector to implement queue.
2) Use stacks to implement queue.( Cracking the coding interview has the answers for this. )
Queue have very simple characteristics:
1) enqueue: add a new element at the end of the queue.
2) dequeue: remove an element from the from of the queue,
I wanted to implemented the array version and here is what I came up with.
FIFO queues can be implemented using array or linked list and each implementation has some advantage over the other.
E.g.:
- If implemented using arrays. dequeue and enqueue operation be performed in O(1), but adds the limitation on the queue size.
- Linked list, overcome the size limitation and keeps the dequeue and enqueue operation to 0(1).
- We can use modern advance data structures such as vectors ( Dynamic arrays ) to implement queues, but whenever the existing capacity for vector is reached, a new vector of size of 2n is created and all the elements from old vector is copied to newly allocated vector.
Implementing FIFO queue is always preferred to be implemented in Linked List, but some time candidates are asked to implement a variation of the FIFO.
E.g.: 1) Use Array/Vector to implement queue.
2) Use stacks to implement queue.( Cracking the coding interview has the answers for this. )
Queue have very simple characteristics:
1) enqueue: add a new element at the end of the queue.
2) dequeue: remove an element from the from of the queue,
I wanted to implemented the array version and here is what I came up with.
#include <iostream> #include <stdlib.h> using namespace std; enum queue_code { QUEUE_EMPTY = 0, QUEUE_FULL, QUEUE_SUCCESS }; class Queue{ public: queue_code enqueue( int value ); queue_code dequeue( int &queue_element ); Queue(); Queue(int size); ~Queue(); private: int queue_capacity; int *queue; int queue_end; int queue_start; int queue_size; }; queue_code Queue::enqueue( int value ) { if ( queue_size == queue_capacity ) { return QUEUE_FULL; } queue[queue_end] = value; queue_end = ( queue_end ) % queue_capacity; queue_size ; return QUEUE_SUCCESS; }; queue_code Queue::dequeue( int &queue_element ) { if ( queue_size == 0 ) { return QUEUE_EMPTY; } queue_element = queue[queue_start]; queue_start = ( queue_start ) % queue_capacity; queue_size--; return QUEUE_SUCCESS; }; Queue::Queue ( int size ) { queue_capacity = size; queue = new int[ queue_capacity ]; queue_end = 0; queue_start = 0; queue_size = 0; }; Queue::~Queue() { delete[] queue; }I hope this was hopeful.
No comments:
Post a Comment