Progress

Stack Data Structure Push & Pop using Array and Linked List

Stack Data Structure Push & Pop using Array and Linked List

The Stack is one of the most important data structure which has many uses. Several fundamental programming concepts such as recursion, backtracking, the function calls and many others use Stack.

What is Stack Data Structure?

The stack is an abstract data type and data structure which is based on LIFO (last in first out).

It means the element that we insert at last (top of stack) will be the first one to be taken out.

Stack data structures
Stack

We use Stack in our daily life. Here are some examples which describe the working of Stack.

  • Stack of Plates
  • Stack of bread

The plate that we put on top is the first one that we take out.

Stack of plates

There are two ways to create a stack in programming, first using an Array and second using a Linked list. Both are useful in specific situations.

The insert operation in Stack is called PUSH and delete operation POP.

PUSH Operation in Stack Data Structure

The PUSH operation is used to insert a new element in the Stack. PUSH operation inserts a new element at the top of the stack.

Push operation in stack data structure
Stack Push Operation

It is important to check overflow condition before push operation when using an array representation of Stack.

If we try to insert a new element in full stack (array has limited size), a stack overflow condition occurs. It means that we cannot add more elements to the stack.

To avoid this situation we can use a linked list instead of the array because the linked list has dynamic size, we just need to add one more node with the data.

The push operation in Stack structure takes only O(1) constant time. The reason is that we only add one element on top of the Stack.

POP Operation in Stack Data Structure

The POP operation is to remove an element from the top of the stack. The element deleted is the recently inserted element in the Stack.

It means that we delete element from the top of the stack.

Pop operation in Stack data structure
Stack Pop Operation

In POP operation we need to check Stack underflow condition.

Stack underflow condition occurs when the Stack is already empty and we try POP operation (we cannot remove an element from empty Stack).

The POP operation also takes only O(1) constant time because we remove only one element from the top of the stack.

Representation of Stack

There are two ways to implement Stack, the first one is using array and the other one is using a Linked list.

Array Representation of Stack

This is the general representation of Stack.

We initialize an empty array of size nin which we perform PUSH and POP operations.

The array Stack contains the element from starting index up to the top pointer which represents the last element of the stack.

Stack data structures using array
Stack using Array

When the topPointer = -1, it means the stack is empty and when the topPointer = n it means the stack is full.

It can be very helpful to check overflow and underflow condition.

Here is the pseudo code for Stack using array arr of size n.

check_Overflow
    if(top==n)
        return True
    else
        return False

check_UnderFlow
    if(top==-1)
      return True
    else
        return False

PUSH_OPERATION(data)
    if(check Overflow)
        print("Stack Over flow, No more space left")
        return
    else
        top = top+1
        arr[top] = data

POP_OPERATION
    if(check Underflow)
        print("Stack Underflow, No more elements left")
        return
    else
        top = top-1
        return arr[top+1]

This is the pseudo code to create stack using an array. You can create a class in any language and implement these methods.

It is necessary to implement methods to check overflow and underflow condition because it is a common error.

Linked List Representation of Stack

Before moving to this part you must know about linked list and the difference between array and linked list.

A linked list has some advantages and disadvantages over an array which make it more suitable for some specific tasks.

They have dynamic length, it means there is no limit on the number of elements we can add. It is convenient to use a linked list in place of an array when the number of elements is unknown.

Stack using linked list
Stack using Linked list

Here are some quick facts about Stack using linked lists which will be helpful to make a decision.

PUSH and POP operations in the linked list take O(1) constant time because a pointer is at the end of the linked list which manage insertion and deletion.

We only need to check the underflow condition here. If top pointer refers to null then the Stack is already empty.

Applications of Stack Data Structure

As we already see that insertion and deletion take constant time which is performance efficient.

Here are some common application of Stack data structures.

  • Back buttons in browsers
  • Undo mechanism
  • Evaluate prefix and postfix notation
  • Backtracking
  • Recursion
  • Track Nested Function calls

Summary

Now, you know how important the Stack is, here is a quick summary of all the above points.

  • The stack is based on LIFO (last in first out). The last element inserted is popped out first.
  • We call insert operation as Push and delete operation as Pop in Stack.
  • We can implement stack using an array or a linked list.
  • Use array when you want fixed size Stack and linked list for dynamic size.
  • Properly check Stack overflow and underflow conditions to avoid bugs.
Share the Post ;)

Related Posts