Stack Data Structure Using Array and Linked List

In our day to day life, we see stacks of plates, coins, etc. All these stacks have one thing in common that a new item is added at the top of the stack and any item is also removed from the top i.e., the most recently added item is removed first.

stack

In Computer Science also, a stack is a data structure which follows the same kind of rules i.e., the most recently added item is removed first. It works on LIFO (Last In First Out) policy. It means that the item which enters at last is removed first.

stack using array and linked list

Since a stack just has to follow the LIFO policy, we can implement it using a linked list as well as with an array. However, we will restrict the linked list or the array being used to make the stack so that any element can be added at the top or can also be removed from the top only.

A stack supports few basic operations and we need to implement all these operations (either with a linked list or an array) to make a stack. These operations are:

Push → The push operation adds a new element to the stack. As stated above, any element added to the stack goes at the top, so push adds an element at the top of a stack
push in stack

Pop → The pop operation removes and also returns the top-most (or most recent element) from the stack.
pop in stack

Top → The Top operations only returns (doesn’t remove) the top-most element of a stack.
top in stack

isEmpty → This operation checks whether a stack is empty or not i.e., if there is any element present in the stack or not.
isEmpty in stack

We also handle two errors with a stack. They are stack underflow and stack overflow. When we try to pop an element from an empty stack, it is said that the stack underflowed. However, if the number of elements exceeds the stated size of a stack, the stack is said to be overflowed.

errors in stack

At many places, you might find out that a stack is referred to as an abstract data type which creates confusion in our mind about whether a stack is an abstract data type or a data structure? So, let’s discuss.

Stack - Abstract Data Type or Data Structure?

In an Abstract Data Type (or ADT), there is a set of rules or description of the operations that are allowed on data. It is based on a user point of view i.e., how a user is interacting with the data. However, we can choose to implement those set of rules differently.

A stack is definitely an ADT because it works on LIFO policy which provides operations like push, pop, etc. for the users to interact with the data. A stack can be implemented in different ways and these implementations are hidden from the user. For example, as stated above, we can implement a stack using a linked list or an array. In both the implementations, a user will be able to use the operations like push, pop, etc. without knowing the data structure used to implement those operations.

However, when we choose to implement a stack in a particular way, it organizes our data for efficient management and retrieval. So, it can be seen as a data structure also.

Till now, we know about stacks and operations involved with a stack. Let’s discuss the applications of a stack.

Applications of Stack

There are many applications of a stack. Some of them are:

Stacks are used in backtracking algorithms.
They are also used to implement undo/redo functionality in a software.
Stacks are also used in syntax parsing for many compilers.
Stacks are also used to check proper opening and closing of parenthesis.

We have already discussed a lot about stacks. So, let’s code a stack using an array as well as a linked list.

Stack Using Array

We are going to use the element at the index 1 of the array as the bottom of the stack and the last element of the stack as the top of the stack as described in the picture given below.

top and bottom of stack

Since we need to add and remove elements from the top of the stack, we are going to use a pointer which is always going to point the topmost element of the stack. It will point to the element at index 0 when the stack is empty.

top pointer for empty stack

So, let’s first write a function to check whether a stack is empty or not.

IS_EMPTY(S)
  if S.top == 0
      return TRUE
  return FALSE

We are going to consider only the elements from 1 to S.top as part of the stack. It might be possible that there are other elements also in the array but we are not going to consider them as stack.

elements in size of stack

To add an item to a stack (push), we just need to increment the top pointer by 1 and add the element there.

PUSH(S, x) → Here, S is the stack and x is the item we are going to push to the stack.

Let’s suppose that S.size is the maximum size of the stack. So, if S.top+1 exceeds S.size, then the stack is overflowed. So, we will first check for the overflowing of the stack and then accordingly add the element to it.

push in stack

PUSH(S, x)
  S.top = S.top+1
  if S.top > S.size
      Error "Stack Overflow"
  else
      S[S.top] = x

Similarly to remove an item from a stack (pop), we will first check if the stack is empty or not. If it is empty, then we will throw an error of "Stack Underflow", otherwise remove the element from the stack and return it.  

POP(S)
  if IS_EMPTY(S)
      Error “Stack Underflow”
  else
      S.top = S.top-1
      return S[S.top+1]

Let’s see the use of the above code snippets to develop a stack in C, Java and Python.

C
Python
Java

#include <stdio.h>

#define SIZE 10

int S[SIZE+1];
int top = 0;

int is_empty() {
if(top == 0)
  return 1;
return 0;
}

void push(int x) {
top = top+1;
if(top > SIZE) {
  printf("Stack Overflow\n");
}
else {
  S[top] = x;
}
}

int pop() {
if(is_empty()) {
  printf("Stack Underflow\n");
  return -1000;
}
else {
  top = top-1;
  return S[top+1];
}
}

int main() {
pop();
push(10);
push(20);
push(30);
push(40);
push(50);
push(60);
push(70);
push(80);
push(90);
push(100);
push(110);

int i;
for(i=1; i<=SIZE; i++) {
  printf("%d\n",S[i]);
}
return 0;
}

SIZE = 10
S = [0]*(SIZE+1) #to initialize the list
top = 0

def is_empty():
if top==0:
  return True
return False

def push(x):
global top
top = top+1
if top>SIZE:
  print("Stackoverflow")
else:
  S[top] = x

def pop():
global top
if is_empty():
  print("Stackunderflow")
else:
  top = top-1
  return S[top+1]

if __name__ == '__main__':
pop()
push(10)
push(20)
push(30)
push(40)
push(50)
push(60)
push(70)
push(80)
push(90)
push(100)
push(110)

print(S[1:SIZE+1])

class Stack {
public static int SIZE = 10;
public static int top = 0;

public static int[] S = new int[SIZE+1];

public static boolean isEmpty() {
  if(top == 0)
    return true;
  return false;
}

public static void push(int x) {
  top = top+1;
  if(top > SIZE)
    System.out.println("Stackoverflow");
  else
    S[top] = x;
}

public static int pop() {
  if(isEmpty()) {
    System.out.println("Stackunderflow");
    return -1000;
  }
  else {
    top = top-1;
    return S[top+1];
  }
}

public static void main(String[] args) {
  pop();
  push(10);
  push(20);
  push(30);
  push(40);
  push(50);
  push(60);
  push(70);
  push(80);
  push(90);
  push(100);
  push(110);

  for(int i=1; i<=SIZE; i++) {
    System.out.println(S[i]);
  }
}
}

Stack Using Linked List

A stack using a linked list is just a simple linked list with just restrictions that any element will be added and removed using push and pop respectively. In addition to that, we also keep top pointer to represent the top of the stack. This is described in the picture given below.

stack using linked list

A stack will be empty if the linked list won’t have any node i.e., when the top pointer of the linked list will be null. So, let’s start by making a function to check whether a stack is empty or not.

IS_EMPTY(S)
  if S.top == null
      return TRUE
  return FALSE

Now, to push any node to the stack (S) - PUSH(S, n), we will first check if the stack is empty or not. If the stack is empty, we will make the new node head of the linked list and also point the top pointer to it.

push in empty stack using linked list

PUSH(S, n)
    if IS_EMPTY(S) //stack is empty
        S.head = n //new node is the head of the linked list
        S.top = n //new node is the also the top

If the stack is not empty, we will add the new node at the last of the stack. For that, we will point next of the top to the new node - (S.top.next = n) and the make the new node top of the stack - (S.top = n).

push in stack using linked list

PUSH(S, n)
    if IS_EMPTY(S) //stack is empty
        ...
    else
        S.top.next = n
        S.top = n

PUSH(S, n)
  if IS_EMPTY(S) //stack is empty
      S.head = n //new node is the head of the linked list
      S.top = n //new node is the also the top
  else
      S.top.next = n
      S.top = n

Similarly, to remove a node (pop), we will first check if the stack is empty or not as we did in the implementation with array.


POP(S)

    if IS_EMPTY(S)

        Error “Stack Underflow”

In the case when the stack is not empty, we will first store the value in top node in a temporary variable because we need to return it after deleting the node.

POP(S)
    if IS_EMPTY(S)
        ...
    else
        x = S.top.data

Now if the stack has only one node (top and head are same), we will just make both top and head null.

pop in stack with one element

POP(S)
    if IS_EMPTY(S)
        ...
    else
        ...
        if S.top == S.head //only one node
            S.top = NULL
            S.head = NULL

If the stack has more than one node, we will move to the node previous to the top node and make the next of point it to null and also point the top to it.

pop in stack using linked list

POP(S)
    ...
        ...
        if S.top == S.head //only one node
            ...
        else
            tmp = S.head
            while tmp.next != S.top //iterating to the node previous to top
                tmp = tmp.next
            tmp.next = NULL //making the next of the node null
            S.top = tmp //changing the top pointer

We first iterated to the node previous to the top node and then we marked its next to null - tmp.next = NULL. After this, we pointed the top pointer to it - S.top = tmp.

At last, we will return the data stored in the temporary variable - return x.

POP(S)
  if IS_EMPTY(S)
      Error "Stack Underflow"
  else
      x = S.top.data
      if S.top == S.head //only one node
          S.top = NULL
          S.head = NULL
      else
          tmp = S.head
          while tmp.next != S.top //iterating to the node previous to top
              tmp = tmp.next
          tmp.next = NULL //making the next of the node null
          S.top = tmp //changing the top pointer
      return x

C
Python
Java

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
int data;
struct node *next;
}node;

typedef struct linked_list {
struct node *head;
struct node *top;
}stack;

//to make new node
node* new_node(int data) {
node *z;
z = malloc(sizeof(struct node));
z->data = data;
z->next = NULL;

return z;
}

//to make a new stack
stack* new_stack() {
stack *s = malloc(sizeof(stack));
s->head = NULL;
s->top = NULL;

return s;
}

void traversal(stack *s) {
node *temp = s->head; //temporary pointer to point to head

while(temp != NULL) { //iterating over stack
  printf("%d\t", temp->data);
  temp = temp->next;
}

printf("\n");
}

int is_empty(stack *s) {
if(s->top == NULL)
  return 1;
return 0;
}

void push(stack *s, node *n) {
if(is_empty(s)) { //empty
  s->head = n;
  s->top = n;
}
else {
  s->top->next = n;
  s->top = n;
}
}

//function to delete
int pop(stack *s) {
if(is_empty(s)) {
  printf("Stack Underflow\n");
  return -1000;
}
else {
  int x = s->top->data;
  if(s->top == s->head) {// only one node
    free(s->top);
    s->top = NULL;
    s->head = NULL;
  }
  else {
    node *temp = s->head;
    while(temp->next != s->top) // iterating to the last element
      temp = temp->next;
    temp->next = NULL;
    free(s->top);
    s->top = temp;
  }
  return x;
}
}

int main() {
stack *s = new_stack();

node *a, *b, *c;
a = new_node(10);
b = new_node(20);
c = new_node(30);

pop(s);
push(s, a);
push(s, b);
push(s, c);

traversal(s);
pop(s);
traversal(s);


return 0;
}

class Node():
def __init__(self, data):
  self.data = data
  self.next = None

class Stack():
def __init__(self):
  self.head = None
  self.top = None

def traversal(s):
temp = s.head #temporary pointer to point to head

a = ''
while temp != None: #iterating over stack
  a = a+str(temp.data)+'\t'
  temp = temp.next

print(a)

def is_empty(s):
if s.top == None:
  return True
return False

def push(s, n):
if is_empty(s): #empty
  s.head = n
  s.top = n
else:
  s.top.next = n
  s.top = n

def pop(s):
if is_empty(s):
  print("Stack Underflow")
  return -1000
else:
  x = s.top.data
  if s.top == s.head: # only one node
    s.top = None
    s.head = None
  else:
    temp = s.head
    while temp.next != s.top: #iterating to the last element
      temp = temp.next
    temp.next = None
    del s.top
    s.top = temp
  return x

if __name__ == '__main__':
s = Stack()

a = Node(10)
b = Node(20)
c = Node(30)

pop(s)
push(s, a)
push(s, b)
push(s, c)

traversal(s)
pop(s)
traversal(s)

class Node {
public int data;
public Node next;

public Node(int data) {
  this.data = data;
  next = null;
}
}

class Stack {
public Node head;
public Node top;

public Stack() {
  head = null;
  top = null;
}

public void traversal() {
  Node temp = this.head; //temporary pointer to point to head

  while(temp != null) { //iterating over stack
    System.out.print(temp.data+"\t");
    temp = temp.next;
  }

  System.out.println("");
}

public boolean isEmpty() {
  if(this.top == null)
    return true;
  return false;
}

public void push(Node n) {
  if(this.isEmpty()) {
    this.head = n;
    this.top = n;
  }
  else {
    this.top.next = n;
    this.top = n;
  }
}

public int pop() {
  if(this.isEmpty()) {
    System.out.println("Stack Underflow\n");
    return -1000;
  }
  else {
    int x = this.top.data;
    if(this.head == this.top) {// only one node
      this.top = null;
      this.head = null;
    }
    else {
      Node temp = this.head;
      while(temp.next != this.top) // iterating to the last element
        temp = temp.next;
      temp.next = null;
      this.top = temp;
    }
    return x;
  }
}
}

class StackMain {
public static void main(String[] args) {
  Stack s = new Stack();

  Node a, b, c;
  a = new Node(10);
  b = new Node(20);
  c = new Node(30);

  s.pop();
  s.push(a);
  s.push(b);
  s.push(c);

  s.traversal();
  s.pop();
  s.traversal();
}
}

In the next chapter, we are going to study about queues and implement it also using an array and a linked list.

Success is a science; if you have the conditions, you get the result.

- Oscar Wilde

Stack Data Structures

Stack - Abstract Data Type or Data Structure?

Applications of Stack

Stack Using Array

Stack Using Linked List