Data Structures and Algorithms - Stack

Stack is a data structure which is also known as a Last In First Out (LIFO) data strucutre.

Important Elements of a stack

TOP: Top in stack denotes the element at the top / last inserted element of the stack. By default the value of top is -1, denoting an empty stack.

push(x) Push is a function in stack which handles element insertion in stack. The element is inserted after / on top of the top element.

pop() Pop function is stack removes an element in stack by reducing the top by 1. This also returns the element being popped

peek() Peek is a function in stack showing us the top element.

stack overflow: Overflow is a situation where there is no more space to insert elements in a stack. There are two ways we can handle this scenario - either by allocating more memory to the stack or by not letting the user insert any more elements.

stack underflow: Underflow is a situation where there are no elements in the stack. This is achieved when we are trying to pop an element from stack but there are no elements.

Algorithms for each of the functions of stack using array

push()

- if top + 1 > limit_of_stack:
  - print "stack overflow"
- else:
  - top = top + 1
  - stack[top] = element_to_insert

pop()

- if top == -1:
  - print "stack underflow"
- else:
  - element_deleted = stack[top]
  - top = top - 1
  - return element_deleted

As you can see the deleted element still remains in the stack unless overwritten by another push.

push & resize (dynamic memnory allocation) (possible in C only)

resize:

- resize(pointer_to_array):
    - pointer_to_array = (int *) realloc (sizeof(int) * 2 * size_of_current_array)
    - if pointer_to_array == NULL:
        - print "memory allocation failed"
        - return

Updated push:

- if top + 1 > limit_of_stack:
  - resize()
- else:
  - top = top + 1
  - stack[top] = element_to_insert

Time complexity of functions in stack

function name	time
push()	O(1)
pop()	O(1)