Data Structures and Algorithms: September 2014

Sunday 28 September 2014

Stack Implemented As Linked List

Stack Implemented as Linked List

In my previous post, i presented you the C-code of a stack implemented as an array. Now the same stack can be implemented with the help of a linked list. The major advantage is that there is no stack FULL condition when implemented as a linked list as compared to implementation with array.

Below is the working C code of a STACK implemented with the help of linked list.

// Stack implementation as a link list.
#include<stdio.h>
#include<stdlib.h>
struct Node
{
 int data;
 struct Node *next;
}*top=NULL;

void push(int query)
{
 struct Node *node=(struct Node *) malloc(sizeof(struct Node)); // type casting in malloc is not required in C, even then just to make sure things run OK.
 node->data=query;
 node->next=top;
 top=node;
}

int pop()
{
    int n=top->data;
 top=top->next;
 return n;
}
void display()
{
 struct Node *temp=top;
 printf("Elements of the STACK, from the top are: ");
 for(;temp!=NULL;temp=temp->next)
 printf("%d ",temp->data);
 printf("\n");
}

int main()
{
 int choice,query;
 while(1)
 {
  printf("Enter the operation for the stack.\n");
  printf("1. PUSH\n");
  printf("2. POP\n");
  printf("3. DISPLAY\n");
  printf("4. EXIt\n");
  scanf("%d",&choice);
  switch(choice)
  {
   case 1:
                  printf("Enter the element to be pushed: \n");
                  scanf("%d",&query);
    push(query);
    printf("The node with data %d is pushed in the STACK. :)\n",query);
    break;
   case 2:
                  if(top==NULL)
                  {
                       printf("Empty STACK. :(\n");
                       break;
                  }
    printf("Element %d poped from the STACK. :)\n",pop());
    break;
   case 3:
                  if(top==NULL)
                  {
                       printf("Empty STACK. :(\n");
                       break;
                  }
    display();
    break;
   case 4:
    return 0;
  }
 }
}

// There is no stack full condition in implementation of a stack as a linked list.

Wednesday 24 September 2014

Stacks as an Array

First i am going to explain what is a 'stack', a stack is a Data structures with a predefined method of storing , retrieving and deleting the elements stored in it.

Stacks follows Last In First Out(LIFO) mechanism, i.e., The element 'pushed' last into a stack will be the first one to be 'poped' out of the stack.
Push: The operation of inserting an element into the stack is familiarized as 'PUSH' in the world of stack.
Pop: The operation of removing an element from the stack is familiarized as 'POP'.

Below is a working C code for implementing stack as an array.
Stacks can also be implemented as linked list which i am going to discuss in my next post.

// STACK implemented as an array.
#include<stdio.h>
#define MAX 10
int a[MAX],top=-1;
void push(int n)
{
  printf("The element %d is PUSHED into the stack. :)\n",(a[++top]=n));
}
void pop()
{
  printf("the element %d is POPED. :)\n",a[top--]);
}
void display()
{
 int i;
 printf("The elements of stack are: ");
 for(i=0;i<=top;i++)
    printf("%d ",a[i]);
    printf("\n");
}
int main()
{
 int choice,n;
 while(1)
 {
  printf("Enter the operation to be done with STACK\n");
  printf("1.PUSH\n");
  printf("2.POP\n");
  printf("3.DISPLAY\n");
  printf("4.EXIT\n");
  scanf("%d",&choice);
  switch(choice)
  {
   case 1:
                if(top==MAX-1)
                {
                    printf("The stack is FULL. :(\n");
                    break;
                }
                printf("Enter the elemnt to be pushed\n");
                scanf("%d",&n);
    push(n);
    break;
   case 2:
                if(top==-1)
                {
                    printf("The stack is EMPTY. :(\n");
                    break;
                }
    pop();
    break;
   case 3:
                if(top==-1)
                {
                    printf("The stack is EMPTY. :(\n");
                    break;
                }
    display();
    break;
   case 4:
    return 0;
            default:
                printf("Please enter a valid option.\n");
                break;
  }
 }
}