Stacks

Stacks is one of the important data structure concept. It is access-limited(elements cannot be added or removed from them at any position), mutable , un-bounded sequences. Element can only be added or removed from only one end(top always). thus, follows LIFO (Last In First Out).

Methods:

There are three primary methods and two helper methods: 1. pop() - returns the top element in the stack, always the recent inserted value. 2. push(value) - inserts value at the top of the stack. 3. peek() - get the top value in the stack without altering its structure.

  • isEmpty() - To check whether any element exists in the stack.
  • getLength() - returns the length of the elements/value in the stack.

One of the real-world example for stacks is pile of plates in the kitchen. It looks something like this,

Pile of Plates

Each plate can be kept at the top and any existing plates from the set can also taken in the same order.

Advantages

  1. Since it always keeps the last inserted value at the top, retrival of the value is always O(1).

Drawbacks

  1. Lookup cost for any element is O(n) where n is the number of elements in the stack, unlike array where it is O(1).
  2. It is not a good data structure for large data sets.

Example program implemented using golang:



Regex in Golang