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
Array Implementation
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