Stack

Implemented by: Plipus Tel https://www.plipustel.com

What is Stack?

Is a linear data structure in which insertion and deletion are allowed only at the top of stack (or at the end). Stack follows LIFO (Last In First Out) rule. Just like in real world stack data structure could be the stack of books, stack of coins, stack of money, stack of discs, etc. Common operations: push(), peek(), isEmpty(), getSize(), isFull()

• pop(): O(1) complexity
• peek() O(1) complexity
• push() 0(1) complexity
• searching() 0(n) complexity
• size() 0(1) complexity

Stack is also known as an Abstract Data Type (ADT) that defines sets of operations and behavior for certain purpose.

Basic Algorithm

Stack implementation will use the array as data structure (could also linked list, etc), with the stack rules:

• 1. Define first the length of stack 'L'
• 2. Define an arrayStack with the size 'L'
• 3. Define the TopIndex < 0 which fall in -1
• 4. Operations:
  • push( element):
    a. check first if arrayStack is empty
    if not empty then
    pre-increment the TopIndex, to make sure it self increment (increment immediately)
    arrStack[++TopIndex] = Item

    OR

    arrStack[TopIndex++] = Item
    TopIndex = TopIndex + 1;

    else then
    Abort

  • pop():
    a. check first if arrayStack is empty
    if not empty then
    decrease the index
    arrStack[TopIndex--]
    else then
    Abort

  • isEmpty():
    Check if the TopIndex is equal to -1 (TopIndex == -1 ? True : False)

  • isFull():
    Check if TopIndex == ArrayStackSize - 1 ? True : False

Example Implementation of Stack:

• Nested brackets/braces expression checker
• code parsing
• folder directories path
• compiler syntax
• checking for bracket and braces
• copy paste undo
• Depth First Search (DFS) etc..

Author Website

https://www.plipustel.com