A stack is a finite sequence of elements in which insertions and deletions can take
place at only one end of the sequence, called the top of the stack. Because the most
recently inserted element is the next element to be removed, a stack is a last in, first
out (LIFO) structure. Compilers implement recursion by generating code for pushing
and popping activation records onto the run-time stack whose top record holds the
state of the method currently being executed. Another stack application occurs in the
translation of infix expressions into machine code. With the help of an operator stack,
an infix expression can be converted into a postfix expression, which is an intermediate
form between infix and machine language. For this conversion, worstTime(n) is
linear in n, the size of the infix expression.
A queue is a finite sequence of elements in which insertions can take place only
at the back, and removals can take place only at the front. Because the first element
inserted will be the first element to be removed, a queue is a first in, first out (FIFO)
structure. The inherent fairness of this first come, first served restriction has made
queues important components of many systems. Specifically, queues play a key role
in the development of computer models to study the behavior of those systems.
