Data Structure and Algorithms – Stack

The Stack Data Structure is an abstract data type with a bounded(predefined) capacity.

Stack Data Structure is a simple data structure that allows adding and removing elements in a particular order.
Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.

Basic features of Stack

1. The stack is an ordered list of the similar data type.
2. The stack is a LIFO structure. (Last in First out).
3. push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.
4. The stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

Applications of Stack

The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.

There are other uses also like Parsing, Expression Conversion(Infix to Postfix, Postfix to Prefix etc) and much more.

Implementation of Stack

The stack can be easily implemented using an Array or a Linked List. Arrays are quick but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using an array.

/*  Below program is written in C++ language  */
 
Class Stack
{
  int top;
  public:
  int a[10];    //Maximum size of Stack
  Stack()
  {
    top = -1;
  }
};
 
void Stack::push(int x)
{
  if( top >= 10)
  {
    cout << "Stack Overflow";
  }
  else
  {
    a[++top] = x;
    cout << "Element Inserted";
  }
}
 
int Stack::pop()
{
  if(top < 0)
  {
    cout << "Stack Underflow";
    return 0;
  }
  else
  {
    int d = a[top--];
    return d;
  }
}
 
void Stack::isEmpty()
{
  if(top < 0)
  {
    cout << "Stack is empty";
  }
  else
  {
    cout << "Stack is not empty";
  }
}

Position of Top	Status of Stack
-1	Stack is Empty
0	Only one element in Stack
N-1	Stack is Full
N	Overflow state of Stack

Analysis of Stacks

Below mentioned are the time complexities of various operations that can be performed on the Stack data structure.

• Push Operation: O(1)
• Pop Operation: O(1)
• Top Operation: O(1)
• Search Operation: O(n)

Implementation of Push Operation

The process of putting a new data element onto the stack is known as a Push Operation. Push operation involves a series of steps −

• Step 1 − Checks if the stack is full.
• Step 2 − If the stack is full, produces an error and exit.
• Step 3 − If the stack is not full, increments top to the point next empty space.
• Step 4 − Adds data element to the stack location, where the top is pointing.
• Step 5 − Returns success.

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;  
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Implementation of Push Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.

A Pop operation may involve the following steps −

• Step 1 − Checks if the stack is empty.
• Step 2 − If the stack is empty, produces an error and exit.
• Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
• Step 4 − Decreases the value of top by 1.
• Step 5 − Returns success.

Example

int pop(int data) {
 
   if(!isempty()) {
      data = stack[top];
      top = top - 1;  
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

For a complete stack program in C programming language, please click here.

Ask your questions and clarify your/others doubts on Stack Data Structure by commenting on Forum. Documentation