Data Structures — Stacks

Algorithms and Data Structures From Zero to Hero

Similar to a stack of plates, adding or removing is only possible at the top.
Image generated using DALL-E

In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations:

Basically, a stack is an ordered list in which insertion and deletion are done at one end, where the end is generally call the top. Last In, First Out (LIFO) or First In, Last Out (FILO).

Analogy

Imagine you work in a restaurant cleaning plates and you have plates stacked on top of each other in the canteen. The plate that is on top is the first to be removed, i.e. the plate that has been placed in the lowest position remains in the stack for the longest time. Therefore, it can simply be seen that the LIFO (Last In First Out) / FILO (First In Last Out) order is followed.

Time complexity:

  • push(): O(1)
  • pop(): O(1)
  • peek(): O(1)

Implementation:

You can implement a Stack using an Array or Linked List there are some pros and cons to choosing one or the other.

Pros:

  • Stack using Linked: Is more secure, reliable as they do not get corrupted easily and clean the objects automatically.
  • Stack using Array: Easy to implement and memory saved pointer are not involved as we have random access.

Cons:

  • Stack using Linked: Extra memory is required, total size have to be defined before and if the stack fall outside the memory can lead anormal termination.
  • Stack using Array: The main disadvantage is that doesn’t grow and shrink depending on needs at runtime.

Summary

A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first.

⬅️ Arrays and Linked List | Table of content | Data Structures — Queues ➡️

--

--

Sometimes I write about technical topics and sometimes about what I feel like.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kemil Beltre

Sometimes I write about technical topics and sometimes about what I feel like.