Stack using array

Category: Data Structures
Tags: #datastructures#stack

In this tutorial, we will implement a stack using array by using the fixed array and dynamic array method with their time and space complexity. Basically the size of the array in case fixed array implementation is always fixed but in case of dynamic array implementation size of the array may grow if stack overflow occurs.

Implementation of stack using array

Stack is a linear data structure which works in LIFO (Last In First Out) or FILO (First In Last Out) order. In this tutorial we will implement stack using an array.

Four main operations on stack:

  • Push: Adds new item on the top of stack.
  • Pop: Removes an item from the top of stack.
  • Peek: Returns top element of stack.
  • is_empty: Check if stack is empty or not.

Implementation of stack using array

There are two ways to implement stack using arrays i.e.,

  1. Fixed array implementation
  2. Dynamic array implementation

Fixed array implementation

In case of fixed array implementation of stack, the size of array is always fixed that's why when we try to push an element on stack if already the stack is full then Stack overflow exception will be raised and if we try to pop an element if stack is already empty then Stack underflow exception will be raised.

Python
class Stack:
  def __init__(self, size=10):
      self._stack = []
      self._size = size

  def is_empty(self):
      return len(self._stack) <= 0

  def push(self, data):
      if len(self._stack) >= self._size:
          raise Exception('Stack overflow')
      else:
          self._stack.append(data)

  def pop(self):
      if len(self._stack) <= 0:
          raise Exception('Stack underflow')
      else:
          return self._stack.pop()

  def peek(self):
      if len(self._stack) <= 0:
          raise Exception('Stack underflow')
      else:
          return self._stack[-1]

  def length(self):
      return len(self._stack)


stack = Stack(5)
stack.push(5)
stack.push(2)
stack.push(3)
stack.push(9)
stack.push(6)
print(stack.peek())
print(stack.pop())
print(stack.length())
print(stack.peek())
JavaScript
class Stack {
  #stack;
  #size;

  constructor(size = 10) {
      this.#stack = [];
      this.#size = size;
  }

  isEmpty() {
      return this.#stack.length <= 0;
  }

  push(data) {
      if (this.#stack.length >= this.#size)
          throw "Stack overflow";
      else
          this.#stack.push(data);
  }

  pop() {
      if (this.#stack.length <= 0)
          throw "Stack underflow";
      else
          return this.#stack.pop();
  }

  peek() {
      if (this.#stack.length <= 0)
          throw "Stack underflow";
      else
          return this.#stack[this.#stack.length - 1];
  }

  length() {
      return this.#stack.length;
  }
}

const stack = new Stack(5);
stack.push(5);
stack.push(2);
stack.push(3);
stack.push(9);
stack.push(6);
console.log(stack.peek());
console.log(stack.pop());
console.log(stack.length());
console.log(stack.peek());

Output

6
6
4
9
OperationTime complexity
Space complexity (for n push)O(n)
Time complexity of push()O(1)
Time complexity of pop()O(1)
Time complexity of length()O(1)
Time complexity of is_empty()O(1)

Dynamic array implementation

In case of dynamic array implementation of stack, the size of array is growable i.e., whenever stack reaches at the condition of overflow then the size of array will be increased that's why Stack overflow exception will never raise but Stack underflow may raise in case of stack is empty.

Python
class Stack:
  def __init__(self, size=10):
      self._stack = []
      self._size = size

  def is_empty(self):
      return len(self._size) <= 0

  def push(self, data):
      if len(self._stack) >= self._size:
          self._resize()
      self._stack.append(data)

  def pop(self):
      if len(self._stack) <= 0:
          raise Exception('Stack underflow')
      else:
          return self._stack.pop()

  def peek(self):
      if len(self._stack) <= 0:
          raise Exception('Stack underflow')
      else:
          return self._stack[-1]

  def length(self):
      return len(self._size)

  def _resize(self):
      new_stack = [*self._stack]
      self._size = 2 * self._size
      self._stack = new_stack


stack = Stack(2)
stack.push(5)
stack.push(4)
stack.push(3)
stack.push(9)
print(stack.peek())
print(stack.pop())
print(stack.peek())
JavaScript
class Stack {
  #stack;
  #size;

  constructor(size = 10) {
      this.#stack = [];
      this.#size = size;
  }

  isEmpty() {
      return this.#stack.length <= 0;
  }

  push(data) {
      if (this.#stack.length >= this.#size)
          this.resize();
      this.#stack.push(data);
  }

  pop() {
      if (this.#stack.length <= 0)
          throw "Stack underflow";
      else
          return this.#stack.pop();
  }

  peek() {
      if (this.#stack.length <= 0)
          throw "Stack underflow";
      else
          return this.#stack[this.#stack.length - 1];
  }

  length() {
      return this.#stack.length;
  }

  resize() {
      const newStack = [...this.#stack];
      this.#size = 2 * this.#size;
      this.#stack = newStack;
  }
}

const stack = new Stack(2)
stack.push(5)
stack.push(4)
stack.push(3)
stack.push(9)
console.log(stack.peek())
console.log(stack.pop())
console.log(stack.peek())

Output

9
9
3
OperationTime complexity
Space complexity (for n push)O(n)
Time complexity of push()O(1)
Time complexity of pop()O(1)
Time complexity of length()O(1)
Time complexity of is_empty()O(1)

Advantages of implementing stack using array

  • Easy to implement.
  • Operations require less time.

Disadvantage of implementing stack using array

  • Space may be occupied but not used if the size of stack is small.
Author - Abhishek Kumar