---

Previous

Next

---

Stacks in Data Structure

• A stack is a non-primitive linear data structure. It is an ordered list in which addition of new data item and deletion of already existing data item is done from only one end, known as top of stack(TOS).
• As all the deletion and insertion in a stack is done from top of the stack, the last added element will be the first to be removed from the stack. That is the reason why stack is also called Last-in-First-out (LIFO).
• A stack is simply a list of elements with insertions and deletions permitted at one end—called the stack top. That means that it is possible to remove elements from a stack in reverse order from the insertion of elements into the stack. Thus, a stack data structure exhibits the LIFO (last in first out) property.
• Push and pop are the operations that are provided for insertion of an element into the stack and the removal of an element from the stack, respectively.

 

Stack Implementation

Stack can be implemented in two ways : 

1. Static implementation
2. Dynamic implementation

Static implementation uses arrays to create stack. Static implementation though a very simple technique but is not a flexible way of creation, as the size of stack has to be declared during program design, after that the size cannot be varied.

Dynamic implementation is also called linked list representation and uses pointers to implement the stack type of data structure.

Operations on a Stack

A stack supports two basic operations:

• Push Operation
• Pop Operation

Push Operation : The push operation is used to insert an element into the stack. The new element is added at the topmost position of the stack. However, before inserting the value, we must first check if TOP=MAX–1, because if that is the case, then the stack is full and no more insertions can be done. If an attempt is made to insert a value in a stack that is already full, an OVERFLOW message is printed.

Pop Operation : The pop operation is used to delete the topmost element from the stack. However, before deleting the value, we must first check if TOP=NULL because if that is the case, then it means the stack is empty and no more deletions can be done. If an attempt is made to delete a value from a stack that is already empty, an UNDERFLOW message is printed.

Example: Write a program to perform Push and Pop operations on a stack.

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 3 // Altering this value changes size of stack created 

int st[MAX], top=-1; 
void push(int st[], 
int val); 
int pop(int st[]); 
int peek(int st[]); 
void display(int st[]); 

int main(int argc, char *argv[])
 {
  int val, option;
  do
    {
      printf(" *****MAIN MENU*****");
      printf(" 1. PUSH");
      printf(" 2. POP");
      printf(" 3. DISPLAY");
      printf(" 4. EXIT");
      printf(" Enter your option: ");
      scanf("%d", &option);
      switch(option)
      { 
       case 1: 
         printf(" Enter the number to be pushed on stack: "); 
         scanf("%d", &val);
         push(st, val); 
         break;
       case 2:
         val = pop(st);
         if(val != -1)
         printf(" The value deleted from stack is: %d", val);
         break;
       case 3:
         display(st);
         break;
      }
   }
   while(option != 4); return 0;
 }
 void push(int st[],
 int val)
 {
  if(top == MAX-1)
  {
   printf(" STACK OVERFLOW");
  }
  else
  {
   top++;
   st[top] = val;
  }
 }
 int pop(int st[])
 {
  int val; if(top == -1)
  {
   printf(" STACK UNDERFLOW");
   return -1;
  }
  else
  {
   val = st[top];
   top--;
   return val;
  }
 }
 void display(int st[])
 {
  int i;
  if(top == -1)
   printf("STACK IS EMPTY");
  else
  {
   for(i=top;i>=0;i--)
    printf("%d",st[i]);
    printf(""); // Added for formatting purposes
 } 
}

Output

*****MAIN MENU*****
 1. PUSH
 2. POP 
 3. DISPLAY
 4. EXIT

 Enter your option : 1
 Enter the number to be pushed on stack : 500= 0

Application of Stacks

In this section we will discuss typical problems where stacks can be easily applied for a simple and efficient solution. The topics that will be discussed in this section include the following:

• Reversing a list
• Parentheses checker
• Conversion of an infix expression into a postfix expression
• Evaluation of a postfix expression
• Conversion of an infix expression into a prefix expression
• Evaluation of a prefix expression
• Recursion
• Tower of Hanoi

Multiple Stacks

While implementing a stack using an array, we had seen that the size of the array must be known in advance. If the stack is allocated less space, then frequent OVERFLOW conditions will be encountered. To deal with this problem, the code will have to be modified to reallocate more space for the array. In case we allocate a large amount of space for the stack, it may result in sheer wastage of memory. Thus, there lies a trade-off between the frequency of overflows and the space allocated. So, a better solution to deal with this problem is to have multiple stacks or to have more than one stack in the same array of sufficient size.

Points to Remember

• A stack is basically a list with insertions and deletions permitted from only one end, called the stack-top, so it is a data structure that exhibits the LIFO property.
• The operations that are permitted to manipulate a stack are push and pop.
• One of the important applications of a stack is in the implementation of recursion in the programming language.

---

Previous

Next

---