0

Stack Data Structure – An Ultimate Guide 2021

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.

The basic implementation of a stack is also called a LIFO (Last In First Out).

Stack Data Structure Definition:

A stack data structure is a list of elements in which an element may be inserted or deleted only at one end, called me top of the stack. This means, in particular, that elements are removed from a stack in the reverse order of that in which they were inserted into the stack.

Special terminology is used for two basic operations associated with stacks:

(a) “Push” is the term used to insert an element into a stack.

(b) “Pop” is the term used to delete an element from a stack.

  • There are basically three operations that can be performed on stacks.
    1) Inserting an item into a stack (push).
    2) Deleting an item from the stack (pop).
    3) Displaying the contents of the stack(pip).

Below are some of operations a stack data type supports:

Stack<item-type> Operations
push (new-item :item-type)
Adds an item onto the stack.
top ():item-type
Returns the last item pushed onto the stack.
pop ()
Removes the most-recently-pushed item from the stack.
is-empty ():Boolean
True if no more items can be popped and there is no top item.
is-full ():Boolean
True if no more items can be pushed.
get-size ():Integer
Returns the number of elements on the stack.
  • All operations except get-size() can be performed in O(1) time. get-size() runs in at worst O(N).

Array Implementation of a Stack Data Structure:

When an array is used to implement a stack, the push and pop operations are realized by using the operations available on an array. The limitation of an array implementation is that the stack cannot grow and shrink dynamically as per the requirement.

C program to implement a stack using an array.

#include <stdio.h>
#define MAX 10 /* The maximum size of the stack */
#include <stdlib.h>

void push(int stack[], int *top, int value)
{
   if(*top < MAX )
   {
      *top = *top + 1;
      stack[*top] = value;
   }
  else
  {
      printf("The stack is full can not push a value\n");
      exit(0);
   }
}

void pop(int stack[], int *top, int * value)
{
   if(*top >= 0 )
   {
       *value = stack[*top];
      *top = *top - 1;
   }
   else
   {
      printf("The stack is empty can not pop a value\n");
      exit(0);
   }
}

void main()
{
   int stack[MAX];
   int top = -1;
   int n,value;
   do
   {
      do
      {
            printf("Enter the element to be pushed\n");
         scanf("%d",&value);
         push(stack,&top,value);
            printf("Enter 1 to continue\n");
         scanf("%d",&n);
      } while(n == 1);

      printf("Enter 1 to pop an element\n");
      scanf("%d",&n);
      while( n == 1)
      {
            pop(stack,&top,&value);
         printf("The value poped is %d\n",value);
            printf("Enter 1 to pop an element\n");
            scanf("%d",&n);
      }
      printf("Enter 1 to continue\n");
      scanf("%d",&n);
   } while(n == 1);
}

Example Output:

Enter the element to be pushed

10

Enter 1 to continue

1

Enter the element to be pushed

20

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 20
Enter 1 to pop an element

0

Enter 1 to continue

1

Enter the element to be pushed

40

Enter 1 to continue

1

Enter the element to be pushed

50

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 50

Enter 1 to pop an element

1

The value popped is 40 Enter 1 to pop an element

1

The value popped is 10 Enter 1 to pop an element

0

Enter 1 to continue

0

Linked List Implementation

type Stack<item_type>
data list:Singly Linked List<item_type>
constructor()
list := new Singly-Linked-List()
end constructor

When you want to push something onto the list, you simply add it to the front of the linked list. The previous top is then ”next” from the item being added and the list’s front pointer points to the new item.

method push(new_item:item_type)
list.prepend(new_item)
end method

To look at the top item, you just examine the first item in the linked list

method top():item_type
return list.get-begin().get-value()
end method

When you want to pop something off the list, simply remove the first item from the linked list.

method pop()
list.remove-first()
end method

A check for emptiness is easy. Just check if the list is empty

method is-empty():Boolean
return list.is-empty()
end method

A check for full is simple. Linked lists are considered to be limitless in size.

method is-full():Boolean
return False
end method

A check for the size is again passed through to the list.

method get-size():Integer
return list.get-size()
end method
end type
  • In a linked list, accessing the first element is an O(1) operation because the list contains a pointer that checks for empty as done here are also O(1). Most of the time, users of a Stack do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.

Complexity:

All operations are O(1) with exception of occasional push and clear, which should replace all entries by null in order to let them be garbage-collected. Array implementation does not replace null entries. The Vector implementation does.

Program for implementation of a stack using the linked list.

# include <stdio.h>
# include <stdlib.h>
struct node
{
   int data;
   struct node *link;
};
struct node *push(struct node *p, int value)
{
   struct node *temp;
   temp=(struct node *)malloc(sizeof(struct node));
       /* creates new node
       using data value
       passed as parameter */
   if(temp==NULL)
   {
      printf("No Memory available Error\n");
      exit(0);
   }
   temp->data = value;
   temp->link = p;
   p = temp;
   return(p);
}

struct node *pop(struct node *p, int *value)
{
   struct node *temp;
   if(p==NULL)
   {
      printf(" The stack is empty can not pop Error\n");
      exit(0);
   }
   *value = p->data;
   temp = p;
   p = p->link;
   free(temp);
   return(p);
}

void main()
{
   struct node *top = NULL;
   int n,value;
   do
   {
      do
      {
            printf("Enter the element to be pushed\n");
         scanf("%d",&value);
         top = push(top,value);
         printf("Enter 1 to continue\n");
         scanf("%d",&n);
      } while(n == 1);

      printf("Enter 1 to pop an element\n");
      scanf("%d",&n);
      while( n == 1)
      {
            top = pop(top,&value);
         printf("The value poped is %d\n",value);
            printf("Enter 1 to pop an element\n");
            scanf("%d",&n);
      }
      printf("Enter 1 to continue\n");
      scanf("%d",&n);
   } while(n == 1);
}

Example Output:

Input and Output
Enter the element to be pushed

10

Enter 1 to continue

1

Enter the element to be pushed

20

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 20
Enter 1 to pop an element

1

The value poped is 10
Enter 1 to pop an element

0

Enter 1 to continue

1

Enter the element to be pushed

30

Enter 1 to continue

1

Enter the element to be pushed

40

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 40
Enter 1 to pop an element

0

Enter 1 to continue

1

Enter the element to be pushed

50

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 50
Enter 1 to pop an element

1

The value popped is 30
Enter 1 to pop an element

0

Enter 1 to continue

0

Applications of Stack Data Structure

Naveed S Tawargeri
 

I am a graduate of Information Science Engineering, I work on freelancing projects primarily to learn new technologies. I am passionate about programming and look out for different ways to contribute in this area.

Click Here to Leave a Comment Below 0 comments

Leave a Reply: