Implementation of stack (Dynamic and Static)

Stack can be implemented in two ways:

• Dynamic or linked list implementation

• Static or array implementation  

Static implementation of Stack:

                                     In Static implementation of Stack, the size of the stack should be predefined or declared, hence it is called static because of it's static size. In this implementation, we must know the number of data elements that are going to be inserted in the stack, or else:

If there are more number of data elements than our defined size, then the data cannot be inserted into the stack, hence loss of data.

If there are less number of data elements than our defined size, then it will result to the wastage of memory space.

Hence, We can implement this way if the number of data to be inserted in the stack is well-defined and constant.

Dynamic implementation of stack: 

                                        In this implementation of stack, the size of the stack is not pre-defined during the compile time. As we insert and remove elements from the stack, size of the stack can grow and shrink accordingly. Memory space are allocated to an data element only when the data is inserted and is deallocated when the data is popped out of the stack. Due to this, The dynamic implementation is effective in case if the number of data to be entered is not well-defined.

Stack as an Abstract Data Type (ADT)

Abstract Data Type (ADT):
                      An Abstract Data type is an mathematical model of an data type where the data type is defined by it's possible values, possible operations on the data of this type and the behaviour of these operations. An ADT is an class of object whose logical behaviour is defined by the set of possible values and the set of operations that can be perfomed.

Stack as an adt:

Stack can be defined as an ADT by the following operations:

CreateEmptyStack(S): Creates an empty stack S

Push(s,x): Inserts or pushes an element x at the top of the stack

Pop(S): Pops or removes the top element of stack

Top(S): retrieves the element at the top of the stack

IsEmpty(S): returns an true value if the stack is empty i.e. in stack underflow condition else retruns false

IsFull(S): returns an true value in stack overflow condition i.e. when stack is full, else false

Stack (Push and Pop Operation)

Stack is an ordered collection of homogeneous data where the insertion and the deletion operation can only be performed at one end called the Top of the stack (TOS). In stack, two basic operations can be performed namely,

• Push operation
• Pop operation

Push operation:
                    In order to insert an data in the stack, we use push operation. Using an push operation will insert a data to the top of the stack. If top = max - 1 where max is the size of stack, then the condition is called stack overflow that means the stack is full and no more data can be push into the stack. Hence, in an overflow condition, push operation cannot be performed.After every push operation, the top is incremented by one

Algorithm for Push operation:
                   
Step 1: Start
Step 2: Check if the stack is full or not ? if full, goto Step 3 else goto Step 4
Step 3: Print Stack overflow , and exit
Step 4: Input data to be inserted
Step 5: Stack[Top] <--- data
Step 6: Top = Top +1
Step 7: Stop

 C-implementation of Push Operation:

int top=-1,max=5;
int Stack[5];
void Push(int n){
     if (top != (max-1)){
                printf("Enter data to be inserted: \t");
                Stack[top]=n;
                top=top+1;
     }
     else{
               printf("Stack Overflow");
               exit(1);
      }            
}

Pop operation:
                  In order to remove an data from the stack, we use pop operation. In an stack, data cannot be randomly removed, the first element to be removed is the one on the top. Hence, using an pop operation will remove an element from the top of the stack. If top = -1 then this condition is called stack underflow that means the stack is empty.So, during an stack underflow condition, pop operation cannot be performed as there are no elements to be removed.After every pop operation, the top is decremented by one.

Algorithm for Pop operation:
                   
Step 1: Start
Step 2: Check if the stack is empty or not ? if empty, goto Step 3 else goto Step 4
Step 3: Print Stack underflow , and exit
Step 4: Stack[Top] ---> dataStep 5: Top = Top -1
Step 6: Stop

 C-implementation of Pop Operation:

int top=-1,max=5;
int Stack[5];
void Push(int n){
     if (top != -1){
                printf("Enter data removed: \t%d",Stack[top]);
                top=top-1;
     }
     else{
               printf("Stack Underflow");
               exit(1);
      }            
}

Characteristics of Algorithm

Algorithms are the step-by-step instructions to designed perform an specific task. The major Characteristics of an Algorithm are:

Precision and Clarity :
                      Each and Every steps written precisely and must have an clear meaning. An single step must not contain double meaning i.e. each instruction must be free from ambiguity

Finiteness :  
                     An algorithm must come to an end at an certain point i.e. it must contain an stopping condition and exit from the process if an certain condition is true. The steps to conduct an specific operation must be finite in number, an algorithm must not enter in an endless loop or cycles of instructions.

Effectiveness:
                      Effectiveness means each instruction must be the basic form to carry out an operation. i.e. unwanted instructions that don't affect the output in anyway must be removed.

Input:
        An algorithm has an finite number of input may be zero.But it should not keep taking inputs from the user leading it into an endless loop.

Output:
          An algorithm once completed must give the desired output or complete the given operation correctly.

An algorithm should be work correctly regardless of what computer language the programmer uses.

Different Types of Arrays

An array basically is an homogeneous collection of values with similar data type referred by an common name.It is simply an group of data with similar types. An data in an Array is called an Element of the array, an element can be accessed in an array by using it's index. Index is simply an position in which the array element is stored.

Types of Arrays:

One-Dimensional Arrays:

An One-dimensional Array is an list of data with similar DataTypes referred by an common name.

It can be Defined as:

         Array_name[size of array] = {x,y....,z}

*note: The Array index always starts at 0

It is the simplest form of array in which data are stored in an linear fashion.
say,

int num[4] ={2,6,5,4}

 then the elements in array are stored as:

                                    data         2      6      5     4    
                                    index       0      1      2     3  

Total memory occupied by an One-Diamensional array : (size of dataType) * size of array

Two-Dimensional Arrays:

Instead of being an list of data's, an Two-dimensional Array is an array of arrays with similar datatype referred by an common name.An Two-dimensional Array consists of List of lists rather than list of data's.

It can be defined as:

                          Array_name[row][column]={x,y,.....z}

             In Two dimensional Array, data are stored in matrix form.
say (let's take the same example as in One-Dimensional Array and implement it in 2-D Array),
     
           int num[2][2]={2,6,5,4}

then the elements in array are stored as:

                                         data             2      6      5      4
                                         index          0,0   0,1   1,0   1,1
                         
total memory occupied by an Two-Dimensional Array: (size of DataType) * size of 1st index * size of 2nd index

Multi-Dimensional Arrays:

Multi-Dimensional Arrays are arrays containing two or more than two levels. As the Two-Dimensional Array contained Two levels i.e. Rows and Columns, it is also an Multi-Dimensional Array.An multi-dimensional array may contain n levels,

                   Array_name[a][b][c]....[n]={x,y.....z}