• Stack is LIFO (last in first out) type of list.
• Queue is FIFO.
• ADT definition

template <class item_type, int max_size>

class queue

{

queue();

boolean is_empty();

boolean is_full();

void enqueue(item_type new_item);

item_type front();

void dequeue();

~queue();

};

• If we use list as the parent:
• The insertion is at one end and the deletion is at the other end. That means one of the operations will have to be done at position 1 in the list. The operation at position 1 will have linear time requirement.
• It is not possible to get a uniform constant time, if we use the list as the parent.
• We need a special type of array, called circular array.
• An array, two pointers (integers to keep track of the indices) one called head and the other called tail. Head will point to the item at the front of the queue and tail will point to the next vacant location if the queue is not full.
• Additional variable called size
• The indices will be incremented using a modulus operator % in C++
• head = (head+1)%max_size;
• tail = (tail+1)%max_size;

queue()

head=tail=size=0;

enque(new_item)

a[tail]=new_item;

tail = (tail+1)%max_size; size++;

dequeue()

head = (head+1)%max_size;

size--;

is_empty()

return size==0;

is_full()

return size==max_size;

front()

return(a[head]);

• If we used linked design of the list, we can derive queue very easily, because all operations are constant time for linked design.
• front()

temp=cursor;

cursor = head;

titem = current_item;

cursor = temp;

return titem;

• or

return head->item;

• enqueue()

if(is_empty()) insert_before(item);

else isert_after(item);

• dequeue()

tp = head; head = head->next; delete tp;