Stack Data Structure

Explore the important linear data structure…

Stack is a linear and logical data structure, that works on the Last-in First-out (LIFO) or First-in last-out (FILO) principle. it means here elements are inserted and deleted only using a single location, in a stack that is known as TOP, so insertion and deletion can be done on TOP.

Below is the figure where you can see how a stack data structure works, a container that acts as a stack itself and a ball that is a data or element, that is to be inserted in a stack.

stack data structure

A stack can be implemented by two physical data structures Arrays and Linked list.

ADT of Stack

Abstract data type contains the representation of data and the operations on stacks.

Data

• Space for storing elements.
• Top pointer

Operations

Below are the primary operations we perform on stack data structure

• push(x), to insert an element into the stack.
• pop(), to delete/ remove an element from the stack.
• peek(index), used to look at some value.
• stackTop(), used to check the top value.
• isEmpty(), checking if the stack is empty or not.
• isFull(), checking if stack is full or not.

Stack Using Array

To create a stack using an Array we need to define a few things.

• Size of Array
• Top pointer
• pointer to Array

Here we will use a Structure named stack, to create a stack, the structure Stack contains size, Top, and a pointer to the array (*arr), which we will create dynamically in the heap. Remember that when TOP == -1, it means that the stack is empty, and if TOP == size -1, the stack is full.

struct Stack
{
  int size;
  int Top;
  int *arr;
};

int main()
{
  Stack st;
  cout<<"Enter the size of Stack :"<<endl;
  cin>>st.size;

  st.arr = new int[st.size];
  st.Top = -1;

  return 0;
}

Stack Using Linked List

Here top is a pointer pointing to the first node in the linked list, and a new element is inserted from the top where ever top is pointing which will be the top element in the stack.

struct Node
{
  int data;
  Node *next;
};
 
Node *top = NULL;

int main()
{
  Node *t = new Node;
  t-> data = x;
  t-> next = top;
  top = t;

  return 0;
}

Stack linked list implementation

Note!

Get Owais Ahmad’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In the Array implementation of stack, we use a formula to determine the position of a desired element from the top of the stack, the formula is index = Top - position + 1, why we use this formula because as we know that array stores elements contiguously using the indexes starting from 0, and the last element in the stack is always at top which is index > than 0.

The formula Top — position + 1 is used in a scenario where you want to:

• Access the relative position of an element from the top of the stack.
• Convert a 1-based position into an actual array index in a stack implementation using Array.

Happy Learning! 😊