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.
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:
There are two ways to implement stack using arrays i.e.,
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.
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())
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
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) |
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.
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())
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
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) |
AUTHOR