Basics of Stack Data Structure

Basics of Stack Data Structure

Stack is an abstract, Linear Data Structure that follows Last-In-First-Out (LIFO) principle. All data operations are done at the top of the stack which means, the last item inserted is first accessible. Insertions in stack are called “PUSH” and deletions are termed as “POP”. Other abstract data types such as Array, Structure, Pointer, or Linked List are used to implement stack.

It is most commonly used in the real-world scenarios such as a stack of books or a stack of coins.

 

 

Stack Operations:

Initialize stack and de-initialize once done. In order to support these tasks, stack has to implement these basic operations:

 

  • Push:
    lets you store an item on the stack This operation checks if the stack is full and exits. If stack is not full, add the data and increment top to point to the next empty slot.

 

 
This pseudo code represents Stack push operation:

 

 

push(item)

 

{

 

  If stack is full

 

  {

 

    exit

 

  }

 

  else

 

  {

 

    top= top +1

 

    stack[top]=item

 

  }

 

}

 

  • Pop:
    lets you access an item from the stack Pop operation checks if the stack is empty and exits for an empty stack. If the stack is not empty, we access the item at which top is pointing. The top position is decremented by 1.

 

 

Below pseudo-code shows a simple representation of pop:

 

pop(item)

 

{

 

  If stack is empty

 

  {

 

    exit

 

  }

 

  else

 

  {

 

    item=stack[top]

 

    top= top -1

 

    return item

 

  }

 

}

 

  • Peek:
    lets you read the top item of the stack without having to remove it

 

peek()

 

{

 

  return stack[top]

 

}

 

  • isFull:
    It returns a Boolean and checks whether the stack is full before push operation. Below pseudo code checks if top is at the max. If it is, that means the stack is full.

 

bool isfull()

 

{

 

  if(top == MAXSIZE)

 

  return true;

 

  else return false;

 

}

 

  • isEmpty:
    It returns a Boolean and checks if the stack is empty before pop operation.  We sometimes use an   array to implement stack and pointers to indicate top which is initialized to -1. So we check if the top is equal   to -1, that means the stack is empty.

 

bool isempty(){

 

  if(top == -1)

 

  return true;

 

  else

 

  return false;

 

}

 

  • Rotate:
    Rotates the top-most items in the stack.

 

  • Swap:
    This operation lets you exchange 2 top-most items in a swap. This is most suitable for implementing sort algorithms.

 

 

Get one step closer to your dream job!

 

Prepare for your programming interview with Data Structures & Algorithms Interview Questions You’ll Most Likely Be Asked. This book has a whopping 200 technical interview questions on lists, queues, stacks, and algorithms and 77 behavioral interview questions crafted by industry experts and interviewers from various interview panels.