6-FIFO Queues and Generalized Queue

FIFO Queues and Generalized Queues

  • it is same as pushdown stack except we remove the element that has been in the queue the longest.

  • FIFO queue ADT interface

    template <class Item>
    class QUEUE
    {
        private:
        	//Implementation dependant code
        public:
        	QUEUE(int);
        	int empty();
        	void put(Item);
        	Item get():
    }
    

    A FIFO queue is an ADT that comprises two basic operations: insert (put) a new item, and remove (get) the item that was least recently inserted.

  • Linked-list queue

    image-20200720091107943

    • insert new items at the end
    • to get the item we remove the item from front of the queue
  • Array Implementation

    • cumbersome as we have to decrease size and increase it.
    • we can take two pointer in array to achieve same
  • FIFO queue linked-list implementation

    template <class Item>
    class QUEUE
    {
        private:
        	struct node
            {
                Item item; node* next;
                node(Item x){
                    item=x ; next=0;
                }
            };
        		typedef node *link;
        		link head,tail;
        public:
        	QUEUE(int)
            { head = 0; }
        	int empty() const
            { return head ==0; }
        	void put(Item x)
            { 	link t = tail;
            	tail new node(x);
             	if(head == 0)
                    head=tail;
             	else t->next = tail;
                     }
        	Item get()
            {	Item v = head->item; link t = head->next;
            	delete head; head =t ; return v;}
    }
    

    Both operation are constant time in either implementation

  • specifically pushdown stacks and FIFO queue are special instances of a more generalized ADT: the the generalized queue.

  • There are other queue as well like randomized queue, deque ADT, Priority Queue