Implementing Stack in Go
This article discusses the stack data structure in computer science: what the stack data structure is, the stack operations, an example of a stack implementation on a slice.
Defining Stack as Abstract Data Type
In computer science, a stack is an abstract data type that serves a collection of elements that are inserted and removed according to the LIFO (last-in, first-out) principle. Which means the last element you put in the stack is the first you take out.
An analogy to help you understand the stack is to imagine a stack of plates in a spring-loaded plate dispenser. When you need a new plate from the dispenser you pop it and when you add a new plate, you push it.
An underlying data structure for the stack could be an array, a linked list or any other collection. It is important to note that the implementation and performance of a linked list and array are different. For example, an array supports random access which means you can access an element directly (array[1]). Meanwhile, a linked list supports sequential access which means you sequentially traverse the list to get the required element.
However, regardless of an underlying data structure, the functionality must be the same.
Declare Type Stack
We declare the stack as the struct with the items and mutex fields inside.
items is a slice of elements that we use as an underlying collection for our stack.
mutex is used to avoid a race condition. A race condition arises when two or more threads are accessing the same resources concurrently, and at least one of the threads is writing. It is safe when multiple threads read the same resources as long as they do not change.
The Lock method locks the mutex to exclude the situation in which two or more threads have access to overwrite the stack. The Unlock method unlocks the mutex in order for the stack being accessible for writing after the previous thread has finished.
Operations
The classic stack definition includes two fundamental operations: Push() and Pop(). IsEmpty, Reset, Dump and Peek() are non-essential.
stack.Push(item Item)
Inserts the new item at the top of the stack.
The method calls the built-in function append() which inserts the item at the end of the slice.
By introducing the defer statement we ensure that the stack is always unlocked after processing an operation. However, in terms of performance using defer is more expensive than unlocking the stack before a return statement.
stack.Pop() Item
Removes the top item from the stack.
First, we need to check the length of the stack. If we remove an item from an empty stack, the method must return nil.
If the stack is non-empty, we copy the last item from the stack into a new variable:
Then, the method re-slices the stack with the following code:
In other words, we cut the last item from the slice.
The method returns the removed item on line #12.
stack.IsEmpty() bool
Checks whether the stack is empty or not.
The method executes the len() built-in function which returns the number of elements in the slice. If the number is zero — the stack is empty and the return value is true. If the number is greater than zero — the stack is not empty and the return value is false.
stack.Reset()
Removes all the items from the stack.
The method assigns a zero value (nil) to the slice.
stack.Dump() []Item
Returns all the items in the stack.
The method makes and returns a copy of the original slice. It is recommended to return a copy to avoid modifying the original slice.
stack.Peek() Item
Returns the top item in the stack.
The Peek() method is similar to the Pop() method except for one thing — Peek() does not remove an item.
main()
We implement the preceding operations in the main() function. Initialize the object of the type Stack. Use the method Dump() to see the content of the stack. The stack must be empty.
Then, push some items in the stack. Each item is declared of the type interface{}, so you can push in the stack a value of any type such as string, integer, float etc. Check the content with the Dump() method again. The stack must be filled with the inserted items. If you call the method IsEmpty(), it must return false because the stack is not empty.
Use Peek() to see the last item in the stack.
Try to remove the top item with the Pop() method. You see a message ”Last removed item:” plus the removed item.
Try to reset the stack. Check the result with Dump() to ensure that the stack is empty.
Call the Peek() method to see the last item in the stack. We already emptied our stack, so the result is nil.
Output:
GitHub
The full code you can see on GitHub.
