# What is a Stack?

** Stack** is a linear, or sequential, collection of data that are, as the name says —

**, or put on top of each other.**

*stacked***is one of the most fundamental and earliest-developed**

*Stack**concepts*in

**. The idea of**

*Computer Science***is pretty straightforward, yet it has been very efficient and essential in many algorithms and applications.**

*Stack*** Stack** provide two main operations —

**and**

*push()***The operation —**

*pop().***adds a new item to the top of a collection and**

*push()***removes the last added item. The order in which items are added and removed gives another alternative name to**

*pop()***—**

*Stack*

*FILO***or**

*(First In, Last Out)*

*LIFO***.**

*(Last in, First Out)*Since ** stack** is structured sequentially, its inner storage can be implemented using

**,**

*Array*

*Dynamic***or**

*Array***. It is more efficient to use**

*LinkedList***as the inner storage since the operations of**

*LinkedList***and**

*adding***are executed for —**

*removing***. Time complexities of operations of**

*O(1)***are as follows:**

*Stack*

Push — O(1)

Pop — (1)

Peek — (1)

In the next sections, we will discuss all the following operations in detail and how they are implemented.

Pushing an item — ** push(item)** is implemented in a pretty straightforward way. To put it simply, pushing is just an alternative name to adding items, however, items can be added only into one position —

*to the top of the*

**. It is necessary to keep the right order of the elements. The inner storage can be implemented using**

*stack***,**

*Arrays*

*Dynamic***or**

*Arrays***. However, it is preferable to use**

*LinkedLists***for its efficacy of add() and remove() operations.**

*LinkedLists*As mentioned before, items are pushed only ** to the top of the stack**. The top of the

**in terms of inner storage can be either the beginning or end of the stack. Hence, when items are pushed, they are always pushed either to the beginning or end of the storage. Time complexity of**

*stack*

*push(item) — O(1)**Popping* — ** pop() **is a similar operation to deleting an item with a small difference. Deletion is executed only in one direction, that is

*backwards*. The most recently added item is removed. Here is where

**takes its origin —**

*LIFO***. The implementation of**

*Last in, First Out***may vary depending on the inner storage used, may it be a LinkedList-based or Array-based. Executing**

*pop()***when the stack is empty returns**

*pop()***, or no value.**

*null*Time complexity of

**.**

*pop() — O(1)*** Stack** provides one more useful operation —

**.**

*peek()***allows to check what item is currently on the top of the stack. Compared to other operations,**

*Peek()***is idempotent, i.e. it does not change the structure of the**

*peek()***no matter how many times it is executed. In other words,**

*stack***is equal to**

*peek()***. To put it simply,**

*pop() + push()***is similar to delete the most recently added item, to check it and then to push it again. Executing**

*peek()***when the stack is empty returns**

*peek()***, or no value. Time complexity of**

*null***.**

*peek() — O(1)*To shed more light on real-world applications based on ** stack**, it is good to cite the computer operations —

**. While using some application, we may want to rollback after completing some operations, and there is always a possibility of rolling back. That is a nice example where the**

*do / undo***is used. It pushes all the completed operations and returns to the initial state in case of undesired outcome.**

*stack*The concept of ** stack** has come essential in many algorithms, such as

*depth-first search*,

*backtracking*, etc. To have better understanding of

*stack**application*, I will upload some common problems requiring stack to solve.

The next topic awaiting is ** Queue**, a data structure very similar to

**.**

*Stack*If you are curious to dive deeper and play around with the ** Stack**, I recommend to implement the discussed operations by yourself and test.

The following are the links for: