Stack is a linear, or sequential, collection of data that are, as the name says — stacked, or put on top of each other. Stack is one of the most fundamental and earliest-developed concepts in Computer Science. The idea of Stack is pretty straightforward, yet it has been very efficient and essential in many algorithms and applications.
Stack provide two main operations — push() and pop(). The operation — push() adds a new item to the top of a collection and pop() removes the last added item. The order in which items are added and removed gives another alternative name to Stack — FILO (First In, Last Out) or LIFO (Last in, First Out).
Since stack is structured sequentially, its inner storage can be implemented using Array, Dynamic Array or LinkedList. It is more efficient to use LinkedList as the inner storage since the operations of adding and removing are executed for — O(1). Time complexities of operations of Stack are as follows:
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 stack. It is necessary to keep the right order of the elements. The inner storage can be implemented using Arrays, Dynamic Arrays or LinkedLists. However, it is preferable to use LinkedLists for its efficacy of add() and remove() operations.
As mentioned before, items are pushed only to the top of the stack. The top of the stack 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 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 LIFO takes its origin — Last in, First Out. The implementation of pop() 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 null, or no value.
Time complexity of pop() — O(1).
Stack provides one more useful operation — peek(). 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 stack no matter how many times it is executed. In other words, peek() is equal to
pop() + push(). To put it simply, peek() 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 null, or no value. Time complexity of peek() — O(1).
To shed more light on real-world applications based on stack, it is good to cite the computer operations — do / undo. 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 stack is used. It pushes all the completed operations and returns to the initial state in case of undesired outcome.
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:
