Data Structures and Algorithms - Old Questions

1. Define stack as ADT. Describe its primitive operations on Array implementation and linked list implementation.

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Fig::A stack containing items or elements

Stack as ADT

A stack of elements of type T is a finite sequence of elements of T together with the operations

• CreateEmptyStack(S): Create or make stack S be an empty stack
• Push(S, x): Insert x at one end of the stack, called its top
• Top(S): If stack S is not empty; then retrieve the element at its top
• Pop(S): If stack S is not empty; then delete the element at its top
•  IsFull(S): Determine if S is full or not. Return true if S is full stack; return false otherwise
• IsEmpty(S): Determine if S is empty or not. Return true if S is an empty stack; return false otherwise.

Thus by using a stack we can perform above operations thus a stack acts as an ADT.

Primitive operations of stack

The following operations can be performed on a stack:

1. PUSH operation: The push operation is used to add (or push or insert) elements in a Stack.

ü  When we add an item to a stack, we say that we push it onto the stack

ü  The last item put into the stack is at the top

2. POP operation: The pop operation is used to remove or delete the top element from the stack.

  üwe remove an item, we say that we pop item from the stack.

 üWhen an item popped, it is always the top item which is removed.

The PUSH and the POP operations are the basic or primitive operations on a stack. Some others operations are:

• CreateEmptyStack operation: This operation is used to create an empty stack.
• IsFull operation: The isfull operation is used to check whether the stack is full or not ( i.e. stack overflow)
•  IsEmpty operation: The isempty operation is used to check whether the stack is empty or not. (i. e. stack underflow)
• Top operations: This operation returns the current item at the top of the stack, it doesn’t remove it