3-2-4 Stacks and queues

Stacks and queues are abstract data types (ADT's). Both are dynamic data structures rather than static data structures. Both can be seen as special cases of lists. They differ n the way elements are added and removed.

Stacks

A stack is also known as a last-in first-out abstract data type. Imagine a pile of plates in a restaurant on a spring-loaded rack: plates are added to and taken away from the top.

Two operations can be carried out in a stack:

• add a new item to the top of the stack (known as pushing).
  
• remove an item from the top of the stack (known as popping).

In computing context, stacks are used to store the return address, parameters and register contents when a procedure or function call is made. When the procedure or function completes execution, the return address and other data are retrieved from the stack.

Stacks are used for compilers, when translating high-level language expressions in assignment statements.

Implementation

When implementing a dynamic structure using the linear list method, the structure becomes static.

Queues

A queue also known as the first-in last-out abstract data type.
In everyday life, we encounter queues in lots of different situations.

Two operations may be carried out in a queue:

• add a new item to the rear of the queue
  
• remove an item from the front of the queue

(Computing examples of queues include print jobs waiting to be printed, characters enter at the keyboard and held in a buffer, jobs waiting to be executed under a batch operating systems, and simulations)

A queue can be implemented in various ways. The simplest method is using an array. However, this makes the queue into a static data structure.

For dynamic implementations, memory locations are assigned form the heap and pointer type variables link the nodes.

Priority queue: each element of a priority queue has an associated priority.