top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Summary On Stack.

0 votes
958 views

1.INTRODUCTION

 A stack is a linear data structure. It is very useful in many applications of computer science. It is a list in which all insertions and deletions are made at one end, called the top of the stack. Some of the analogies used to visualize this data structure are

a) Stack of Trays (or) Plates placed on a Table:- Here, one plate is placed on top of another, thus creating a stack of plates. Suppose, a person takes a plate off the top of the stack of plates. The plate mostly recently placed on the stack is the first one to be taken off. The bottom plate is the first one placed on the stack and the last one to be removed.

b) Shipment in a Cargo:- For the shipment of goods, they have to be loaded into a cargo. During unloading, they are unloaded exactly in the opposite order as they are loaded, that is, the goods which are loaded last should be unloaded first.

1.2 DEFINITION

A stack is an ordered collection of homogeneous data elements where the insertion and deletion operations occur at one end only, called the top of the stack. Other names for a stack are pushdown list, and LIFO (or) Last in First Out list. The stack allows access to only one item, i.e., the last item inserted. 

   Fig: Schematic diagram of a stack

1.3 Primitive Operations

The primitive operations that can be performed on a stack are given below:

 1. Inserting an element into the stack (PUSH operation)

 2. Removing an element from the stack (POP operation)

 3. Determining the top item of a stack without removing it from the stack (PEEP operation)

The syntax used for the PUSH operation is--

 PUSH (stack, item)

where stack is the name of the stack into which the item specified as the second argument is placed at the top position of the stack.

The syntax used for the POP operation is--

 POP (stack)

where stack is the name of the stack from which the item has to be removed, i.e., the element at the topmost position of the stack is removed.

1.4 Application of Stack :

  • Parsing

  • Recursive Function

  • Calling Function

  • Expression Evaluation

  • Expression Conversion

  • Infix to Postfix

  • Infix to Prefix

  • Postfix to Infix

  • Prefix to Infix

  • Towers of hanoi

1.5 AN ABSTRACT DATA TYPE (ADT)

An Abstract Data Type (ADT) is a keyword used in a programming language to specify the amount of memory needed to store data and the type of data that will be stored in that memory location.

ADT for Stack This is a Last-In First-Out structure. Items can only be inserted and removed from the top of the stack. The ADT for stack are the following:

 1) Push() (or) Put (or) insert new item on top of stack

 2) Pop() remove and return top item of stack

 3) Top() Verifies the top item of stack

 

1.6 IMPLEMENTATION

A stack can be implemented in any one of the following two ways:

 1. Using an array.

 2. Using a linked list.

 

1.6.1 Array Implementation of Stack:- In the array implementation of a stack, a stack can grow either towards the high-indexed end of the array (or) towards the low-indexed end of the array. 

The array implementation requires the following:

1) An array.

2) A variable top to hold the topmost element of the stack.

/*Array implementation of a stack */

#include<stdio.h>
#include<conio.h>
#define SIZE 10

void push(int);
void pop();
void display();

int stack[SIZE], top = -1;

void main()
{
   int value, choice;
   clrscr();
   while(1)

     {
      printf("\n\n***** MENU *****\n");
      printf("1. Push\n2. Pop\n3. Display\n4. Exit");
      printf("\nEnter your choice: ");
      scanf("%d",&choice);
      switch(choice)          

           {
     case 1: printf("Enter the value to be insert: ");
     scanf("%d",&value);
     push(value);
     break;
     case 2: pop();
     break;
     case 3: display();
     break;
     case 4: exit(0);
     default: printf("\nWrong selection!!! Try again!!!");
           }
     }
}
void push(int value)

    {
      if(top == SIZE-1)

        {
      printf("\nStack is Full!!! Insertion is not possible!!!");
       }      

      else

          {
           top++;
           stack[top] = value;
           printf("\nInsertion success!!!");
          }
    }
  void pop()

       {
         if(top == -1)

               {
         printf("\nStack is Empty!!! Deletion is not possible!!!");
               }

          else

             {
         printf("\nDeleted : %d", stack[top]);
         top--;
             }
       }
void display()

  {
   if(top == -1)

     {
   printf("\nStack is Empty!!!");

     }   

   else

       {
      int i;
      printf("\nStack elements are:\n");
      for(i=top; i>=0; i--)

          {
   printf("%d\n",stack[i]);

          }
       }
  }

1.6.2 Linked List Implementation of a Stack

In the case of linked-list implementation of a stack, the first element inserted into the stack is pointed out by the second element, the second element by the third, and so on. In general the (n-1)th element is pointed out by the nth element. The pointer address corresponding to the nth element has to be maintained. The linked-list implementation of a stack is as follows.

The linked-list implementation of a stack requires the following:

1. Structure declaration containing some n fields.

2. Pointer to the first node (or) the last node.

/*Linked List implementation of a stack */ Go Through This Video:-

References

R KRISHNAMOORTHY G INDIRANI KUMARAVEL.
posted May 10, 2017 by Mantosh Dubey

  Promote This Article
Facebook Share Button Twitter Share Button LinkedIn Share Button


Related Articles

Stack implementation using LinkList?

What is Stack
A stack is a ADT which has LIFO i.e. last in first out behavior. Which means the element which is enetered at the later would be accessed at first. A Stack has two basic operations which are called push and pop which are used to store and retrieve data from the stack.

Stack ADT

Required Functions
Though only push and pop are the necessary function but lets define the following function for the stack implementation in C using LinkList.

int stack_size()
struct node * create_node(int data)
void push(int data) 
void pop()
void traverse_stack()

Sample Code

struct node
{
    int data;
    struct node *next;
};

struct node *top;
int length= 0;

int stack_size()
{
    printf("\n No. of elements in stack : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void push(int data)
{
    struct node *new;
    new = create_node(data);

    if (top == NULL)
    {
        top = new;
    }
    else
    {
        new->next = top;
        top = new;
    }
}

void pop()
{
    struct node *temp_top;

    temp_top = top;

    if (temp_top == NULL)
    {
        printf("\n Error : Trying to pop from empty stack");
        return;
    }
    else
        temp_top = temp_top->next;

    printf("\n Popped value : %d", top->data);
    free(top);
    top = temp_top;

    length--;
}

void traverse_stack()
{
    struct node *temp_top;

    temp_top = top;

    if (temp_top == NULL)
    {
        printf("Stack is empty");
        return;
    }

    while (temp_top != NULL)
    {
        printf("%d ", temp_top->data);
        temp_top = temp_top->next;
    }
}
READ MORE
Summary On Heap.

A Heap is a partially sorted binary tree. Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −

                        key(α) ≥ key(β)

Why use a heap?
A heap can be thought of as a priority queue, the most important node will always be at the top, and when removed, its replacement will be the most important. This can be useful when coding algorithms that require certain things to processed in a complete order, but when you don't want to perform a full sort or need to know anything about the rest of the nodes. For instance, a well-known algorithm for finding the shortest distance between nodes in a graph, Dijkstra's Algorithm, can be optimized by using a priority queue. Heaps can also be used to sort data. 

As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Heap Construction Algorithm

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Heap Deletion Algorithm

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

 

Given below a C Program to Implement a Heap & provide Insertion & Deletion Operation:-

#include <stdio.h>

int array[100], n;

main()

{

    int choice, num;           

    n = 0; /*Represents number of nodes in the heap*/

    while(1)

    {

        printf("1.Insert the element \n");

        printf("2.Display all elements \n");

        printf("3.Quit \n");

        printf("Enter your choice : ");

        scanf("%d", &choice);

        switch(choice)

        {

        case 1:

            printf("Enter the element to be inserted to the list : ");

            scanf("%d", &num);

            insert(num, n);

            n = n + 1;

            break;

        case 2:

            display();

            break;

        case 3:

            exit(0);

        default:

            printf("Invalid choice \n");

    } /*End  of switch */

} /*End of while */

} /*End of main()*/

 

display()

{

    int i;

    if (n == 0)

    {

        printf("Heap is empty \n");

        return;

    }

    for (i = 0; i < n; i++)

        {

  printf("%d ", array[i]);

        printf("\n");       

        }

} /*End of display()*/

 

insert(int num, int location)

{

    int parentnode;

    while (location > 0)

    {

        parentnode =(location - 1)/2;

        if (num <= array[parentnode])

        {

            array[location] = num;

            return;

        }

        array[location] = array[parentnode];

        location = parentnode;

    } /*End of while*/

    array[0] = num; /*assign number to the root node */

} /*End of insert()*/

 

Please go through this video--

https://www.youtube.com/watch?v=njmr_D3E-dM

 

 READ MORE
Summary on Linked List.

Linked List is a linear data structure and it is very common data structure which consists of group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain. Linked Lists are used to create trees and graphs.

Following are the important points to be considered:

  • Linked List contains an link element called first.
  • Each Link carries a data field(s) and a Link Field called next.
  • Each Link is linked with its next link using its next link.
  • Last Link carries a Link as null to mark the end of the list.

Types of Linked List

  1. Simple Linked List 

  2. Doubly Linked List 

  3. Circular Linked List

Basic Operations

  • Insertion − add an element at the beginning of the list.

  • Deletion − delete an element at the beginning of the list.

  • Display − displaying complete list.

  • Search − search an element using given key.

  • Delete − delete an element using given key.

Advantages of Linked Lists

  • They are a dynamic in nature which allocates the memory when required.
  • Insertion and deletion operations can be easily implemented.
  • Stacks and queues can be easily executed.
  • Linked List reduces the access time.

Disadvantages of Linked Lists

  • The memory is wasted as pointers require extra memory for storage.
  • No element can be accessed randomly; it has to access each node sequentially.
  • Reverse Traversing is difficult in linked list.

Insertion Operation

Insertion is a three step process −

  • Create a new Link with provided data.
  • Point New Link to old First Link.
  • Point First Link to this New Link.

code snippet for insertion is given below:

    void insertFirst(int key, int data)

    {
     struct node *link = (struct node*) malloc(sizeof(struct node));     
     link->key = key;
     link->data = data;
     link->next = head;  //point it to old first node
     head = link;  //point first to new first node 
    }

Deletion Operation

Deletion is a two step process −

  • Get the Link pointed by First Link as Temp Link.
  • Point First Link to Temp Link's Next Link.

The code snippet for deletion is given below:

struct node* deleteFirst()

 {
   struct node *tempLink = head;
   head = head->next;  //mark next to first link as first
   return tempLink;   //return the deleted link
}

Navigation Operation

Navigation is a recursive step process and is basis of many operations like search, delete etc. −

  •  Get the Link pointed by First Link as Current Link.
  • Check if Current Link is not null and display it.
  • Point Current Link to Next Link of Current Link and move to above step.

The code snippet for Navigation is given below:

   void printList()     

   {
      struct node *ptr = head;
      printf("\n[ ");
      while(ptr != NULL)   //start from the beginning

        {       
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
        }
        printf(" ]");
   }       

Go through this video--

https://www.youtube.com/watch?v=Y0n86K43GO4

 

 READ MORE
Binary Search Tree - A Summary

A binary search tree (BST) binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right sub-tree.

Many a times binary tree and binary search tree looks same but they are not: a binary tree is a tree where each node has up to two leaves. In a binary tree, a left child node and a right child node contain values which can be either greater, less, or equal to parent node. But in Binary Search Tree each left child contains the value less then the parent node and each right child contains the value greater then Parent.

Balanced Binary Search Tree
BST - Balanced

Unbalanced Binary Search Tree
BST - Unbalanced

Sample C Implementation (Only functions)

typedef struct BST
{
    int data;
    struct BST *lchild,*rchild;
}node;

void insert(node *root,node *new_node)
{
  if(new_node->data < root->data)
     {
     if(root->lchild==NULL)
         root->lchild = new_node;
     else
         insert(root->lchild,new_node);
     }

  if(new_node->data > root->data)
     {
     if(root->rchild==NULL)
         root->rchild=new_node;
     else
         insert(root->rchild,new_node);
     }
}

node *search_recursive(node *root,int key)
{
    if (root == null) 
        return null;

    if (root->data == key)
        return node
    else 
    {
     if (key < root->data) then
        return search_recursive(root->lchild, key);
     else
        return search_recursive(root->rchild, key);
    }
}

node *search_iterative(node *root,int key)
{
 node *temp;
 temp=root;
    while(temp!=NULL)
    {
      if(temp->data==key)
         {
         return temp;
         }

      if(temp->data>key)
         temp=temp->lchild;
      else
         temp=temp->rchild;
    }
 return NULL;
}

Complexity

        Average    Worst
Space     O(n)      O(n)
Search  O(log n)    O(n)
Insert  O(log n)    O(n)
Delete  O(log n)    O(n)
READ MORE
...