top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Stack implementation using LinkList?

+1 vote
496 views

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;
    }
}
posted Sep 1, 2014 by Salil Agrawal

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


Related Articles

What is Queue
Queue is a abstract data type with two operation add_data(enque) and get_data(deque) and provides the data in the form of its arrival or simply it maintains the first in first out machenism (FIFO). Data is always added to its top and retrieved from its rear.

Queue ADT

Required Functions

int queue_size()
struct node * create_node(int data)
void add_data(int data)
int get_data()
void traverse_queue()

Sample Code

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

struct node *top, *rear;
int length= 0;

int queue_size()
{
    printf("\n No. of elements in queue : %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 add_data(int data)
{
    struct node *new;
    new = create_node(data);

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

int get_data()
{
    struct node *temp_rear;
    int ret_val;

    temp_rear = rear;

    if (temp_rear == NULL)
    {
        printf("\n Error : Trying to pop from empty queue");
        return -1;  // Assuming -1 as error
    }
    else
    {
        temp_rear = temp_rear->next;
    }

    printf("\n Popped value : %d", rear->data);
    ret_val = rear->data;

    free(rear);
    rear = temp_rear;

    length--;
    return ret_val;
}

void traverse_queue()
{
    struct node *temp_rear;

    temp_rear = top;

    if (temp_rear == NULL)
    {
        printf("Queue is empty");
        return;
    }

    while (temp_rear != NULL)
    {
        printf("%d ", temp_rear->data);
        temp_rear = temp_rear->next;
    }
} 
READ MORE

What is Link List
W linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a link to the next node in the sequence.

enter image description here

Why Circular Link List
As you can see in the first image that the last->next is null but if last->next is pointing to the head node is called circular link list. The main advantage id that if you have access to any node then you can get access of any node.

Necessary Functions

struct node * create_node(int data)
void insert_at_begining(int info)
void insert_at_position(int info, int position)
void delete_at_begining()
void delete_at_position(int position)
void search(int key)
void update(int olddata, int newdata)
void traverse()
void rev_traverse(struct node *p)

Sample Code
C sample code someone can try C++ code...

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

/* We can have additional structure which can have head and last node is node pointer and 
   additionally can have length variable which contains the length of the link list */
struct node *head = NULL, *last = NULL;
int length = 0;


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 insert_at_begining(int info)
{
    struct node *new;
    new = create_node(info);

    if (head == NULL && last == null)
    {   
        head = last = new;
        head->next = last->next = NULL;
    }
    else
    {
        new->next = head;
        head = new;
        last->next = head;
    }
}

void insert_at_position(int info, int position)
{
    struct node *new, *ptr, *prevnode;
    int len = 0, i;

    new = create_node(info);

    if (head == NULL)
    {
        if (position == 1)
        {
            head = last = new;
            head->next = last->next = NULL; 
        }
        else
            printf("\n empty linked list you cant insert at that particular position");
    }
    else
    {
        if (length < position)
            printf("\n node cant be inserted as position is exceeding the linkedlist length");

        else
        {
            for (ptr = head, i = 1; i <= length; i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (i == position-1)
                {
                    prevnode->next = new;
                    new->next = ptr;
                    break;
                }
            }
        }
    }
}

void delete_at_begining()
{
    struct node *y;

    if (head == NULL) 
        printf("\n List is empty");
    else
    {
        x = last;
        y = head;
        head = y->next;
        last->next = head;
        length--;
        free(y);
    }
}

void delete_at_position(int position)
{
    int count = 0, i;
    struct node *ptr, *temp, *prevnode;

    if (head == last && head == NULL)
        printf("\n empty linked list you cant delete");
    else
    {
        if (length < position)
            printf("\n node cant be deleted at position as it is exceeding the linkedlist length");

        else
        {
            for (ptr = head,i = 1; i <= length; i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (position == 1)
                {   
                    length--;
                    head = ptr;
                    last->next = head;
                    free(prevnode);
                    break;
                }
                else if (i == position - 1)
                {   
                    length--;
                    prevnode->next = ptr->next;
                    free(ptr);
                    break;
                }
            }
        }
    }
}

void search(int key)
{
    int count = 0, i, f = 0;
    struct node *ptr;

    if (head == NULL)
        printf("\nlist is empty no elemnets in list to search");
    else
    {
        for (ptr = head,i = 0; i < length; i++,ptr = ptr->next)
        {
            count++;
            if (ptr->data == key)
            {
                printf("\n the value is found at position at %d", count);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n the value is not found in linkedlist");
    }
}


void update(int olddata, int newdata)
{   
    int i, f = 0;
    struct node *ptr;

    if (head == NULL)
        printf("\n list is empty no elemnts for updation");
    else
    {   
        for (ptr = head, i = 0; i < length; ptr = ptr->next,i++)
        {   
            if (ptr->data == olddata)
            {   
                ptr->data = newdata;
                printf("value is updated to %d", ptr->data);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n no such old value to be get updated");
    }
}

void traverse()
{
    if (head == NULL)
        printf("\n List is empty");
    else
    {
        x = head;
        while (x->next !=  head)
        { 
            printf("%d->", x->data);
            x = x->next;
        }
        printf("%d", x->data);
    }
}

void rev_traverse(struct node *p)
{
    int i = 0;

    if (head == NULL)
    {
        printf("empty linked list");
    }
    else
    {
        if (p->next !=  head)
        {
            i = p->data;
            rev_traverse(p->next);
            printf(" %d", i);
        }
        if (p->next == head)
        {
            printf(" %d", p->data);
        }
    }
}
READ MORE

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:-

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

READ MORE
...