STACKS

A stack is an ordered collection of elements in which insertions and deletions are restricted to one end. The end from which elements are added or removed is referred as the top of the stack.Stacks are also referred as “piles”or “push down lists”.The first element placed in the stack will be at the bottom of the stack. The last element placed in the stack will be at the top of the stack. The last element added to stack is the first element to be removed. Hence stacks are referred as Last In First Out(LIFO)lists or First In Last Out(FILO) lists.

A stack is referred via a pointer to the top element of the stack referred as top pointer. The top pointer keeps track of the top element in the stack. The primary operations that can be carried on the stack are insertions and deletions. These operations on a stack are referred as push and pop respectively.

• Push-insertion

• Pop-deletion

A push operation adds a new element to the stack. Each time a new element is inserted in the stack,the top pointer is incremented by one before the element is placed on the stack.

A pop operation deletes the top most element in the stack. Each time an element is removed from the stack,the top pointer is decremented by one.

The insertions and deletions can occur only at the top of the stack. The elements from the stack may be popped(removed/deleted) only in the reverse order in which they are pushed(added/ inserted) on to the stack.

Consider a stack containing four elements

Empty stack

After pushing

After popping(one element)

IMPLEMENTATION OF STACKS:

Stacks can be implemented in the following ways

• simple array implementation

• array implementation(using ADT)

• linked list implementation

SIMPLE ARRAY IMPLEMENTATION OF STACK:

• One of the simplest way of representing a stack is by means of a single dimensional array.

• Both stacks and array are ordered collection of elements,but an array and a stack are two different things.

• The number of elements in the array is fixed and it is not possible to change the size of the array but the size of the stack varies continuously when elements are pushed and popped. The stack is stored in a part of the array,so an array can be declared large enough to hold the maximum number of elements of the stack.

• Usually this requires a high overestimate,which wastes considerable space. This could be a serious limitation,especially if there are large number of elements.

• Since the running time for insertion and deletions is slow and the size ie the number of elements must be known in advance,simple array implementation of stacks are not generally used.

ARRAY IMPLEMENTATION OF STACK(using ADT):

• In this method of implementation,the stack is defined as a pointer to the structure.

• The structure contains the topofstack and capacity fields.

• Once the maximum size array is known,the stack array can be dynamically allocated.

• The topofstack is associated a value of -1 which indicates that the stack is empty.

• To push some element X onto the stack,we increment Topofstack and then set stack[topofstack]=X,where stack is the array representing the actual stack.

• To pop,we set the return value to stack[topofstack] and then decrement the topofstack.

LINKED LIST IMPLEMENTATION OF STACK:

• The implementation of stack using list uses a single linked list.

• We perform the push operation by inserting at the front of the list.

• We perform pop by deleting the element at the front of the list.

• A top operation merely examines the element at the front of the list,returning its value.

• For creating an empty stack we merely create a header node and set the next pointer to NULL.

• The push is implemented as an insertion into the front of the linked list,where the front of the list serves as the top of the stack.

• We implement pop as a deletion from the front of the list.

• All the operations take constant time because nowhere in any of the routines is there even a reference to the size of the stack.

Now let us see how to implement a stack using ADT.