Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

Characteristics

  • LIFO (Last In First Out)
  • Think “Stack of Plates”

Applications

  • Stacks associated with Recursion, Function Stacks
  • Re-do, Un-do
  • Back, Forward in Web Browser
  • Music Playlists
  • Infix to Postfix conversion
  • Balancing of Symbols
  • Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
  • Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver
  • In Graph Algorithms like Topological Sorting and Strongly Connected Components

Structure

stack.peek() -> Element?

Returns the Element of the top of the stack without removing it. Returns nil if there is nothing in the stack.

stack.push(_ element: Element)

Pushes the given Element onto the stack. Returns void.

stack.pop() -> Element?

Removes the Element at the top of the stack. Returns the Element of the top of the stack. Returns nil if there is nothing in the stack.

stack.isEmpty

Sets var to true if the stack is empty. Sets to false if the stack has elements.

stack.count

Sets var to number of elements in the stack.

Stack with Array Implementation

Advantages

  • Easy to implement.
  • Saves memory because no need to use pointers.

Disadvantages

  • Memory for stack is not dynamically created at runtime.

Code


Stack with Linked List Implementation

Advantages

  • Size is dynamic. Can grow and shrink with little cost.

Disadvantages

  • Requires more space because each node stores pointer(s).

Code


References

Leave a Reply

Come See Me

San Francisco, CA
hello@ingax.com

See My Work