Stacks and Last In First Out

What Is a Stack?

A stack holds a collection of objects that are treated in a ‘last in – first out’ (LIFO) fashion. This means that the last object to be added is the first to be removed. This behaves in much the same way as a pile of plates at a buffet. The kitchen cleans the plates and places them on the pile, customers can then pick up the plates from the top of the stack.

Adding and removing from a stack The process of removing something from the top of the stack is sometimes referred to as ‘pop’, as in popping something off the top. The process of adding to can be called ‘push’.

Where Are Stacks Used?

There are many real world applications of the stack data structure, here are some of them:

Storing Web-Browser History

Web browsers may make use of stacks to implement the web history feature. This makes it quick and easy to implement a ‘back’ button. When you press the back button on your browser the previous item will be popped off the stack and loaded. Every time the user visits a new page, the details will be pushed onto the data structure.

Photography Software

Similar to web browsers, photography and editing software will store user actions in a stack structure, thus allowing the user to undo an action if they make a mistake or wish to go back. Every time the user makes an action it will be pushed to the stack and every time they wish for it to be undone, it will be popped off the top.

Operations

There are a few methods that should be implemented by this data structure.

Pop

This operation pops the most recent item off the top of the stack. The implementation for this method can be found below:

Code

public void Pop() { if (freeSpaceIndex == -1) { Console.WriteLine("Stack is empty"); Console.ReadLine(); } else { Stack[freeSpaceIndex] = null; freeSpaceIndex--; } }

This code first checks to see if there are any items in the stack using the freeSpaceIndex variable, if there are any elements, then it will assign the most recent to null. If there are not any elements, it will warn the user.

Push

This operation pushes an item to the top of the stack. The implementation for this method can be found below:

Code

public void Push(int target){ if (freeSpaceIndex == Stack.MaxLength){ Console.WriteLine("There are too many elements in the stack already"); Console.ReadLine(); } else { freeSpaceIndex++; Stack[freeSpaceIndex] = target; } } This method takes an integer and looks to see if the stack is full, if it is not full then it will push the integer to the most recent position.

Time Complexity

Due to the stack’s simplistic nature, the majority of operations linked with the stack data structure run in a constant time.

Operation Time Complexity pop() O(1) push (T) O(1) This means that no matter how many items are in the stack, it will always take the same amount of time to complete an operation.

Tips and Tricks

Reversing Other Structures

Due to the LIFO nature of the data structure, it can be used to easily reverse the order of other data structures. For example, if we were to loop through the chars found in a string and push them onto the stack, popping them back off would give us the same string in the reverse order.