Stacks

A stack is a linear data structure, which can be operated upon at only one end, which is generally referred to as the top of the stack.  An example to illustrate stack arrangement is keeping a bunch of files in a drawer, which can only be inserted at the top as well as removed from the top.  For this reason, stack is called a LIFO structure i.e. Last In First Out.

The basic operations that may be performed on stacks are push and pop operations.  Push operation refers to putting an element on the top of the stack, whereas pop operation removes the topmost element from the stack.  Stacks are required in situations where data must be stored and then processed in reverse order.  Stack is an abstract data structure.

Example: Push 5, 6, 7 will be represented in fig (i), (ii) & (iii).

In the above figures, the downward pointing arrow refers to top that points to the topmost element of the stack.

Pop will be in LIFO order {7,6,5} as shown in fig. (i), (ii) & (iii).

The upward pointing arrow indicates element at the top of the stack, which is removed in the order (7,6,5) as shown above.

A stack may be represented using arrays and by keeping an integer variable ‘top’ that points to the topmost element of the stack.  Simply stating, stack may be represented using structures, which is composed of an array of elements and top that refers to the topmost element of the stack.  A stack may also be represented using a linked list.  One end of the stack is considered to be fixed which is the bottom of the stack and top shifts as elements are pushed and popped.  Thus stack may be represented as follows:

struct stack{
int top;
int arr[MAX];
};

The object of the structure stack may be instantiated as follows:

struct stack s;

Example:

• Program to implement Stack using structures




• Program to implement Stack using linked list