How to use and Implement a Stack ?

Publish Date: 2022-10-04

---

A stack represents a sequence of objects or elements in a linear data structure format and is based on the principle of Last In First Out (LIFO).

It is commonly used as an abstract data type with two major operations namely push and pop, which are carried out on the topmost element recently added to the stack. The push operation adds an element to the stack while the pop operation removes an element from the top position. A pointer to the top position of the stack is also known as the stack pointer.

A stack may be fixed in size or may be dynamic, so trying to add an element to an already full stack causes a stack overflow exception. Similarly, a condition where a pop operation tries to remove an element from an already empty stack is known as underflow.

A stack allow a limited number of operations, and besides the push and pop, certain implementations may allow for advanced operations such as:

• Peek — View the topmost item in the stack.
• Duplicate — Copy the top item’s value into a variable and push it back into the stack.
• Swap — Swap the two topmost items in the stack.
• Rotate — Move the topmost elements in the stack as specified by a number or move in a rotating fashion.

1. Python implementation:

there is various ways that we can use to implement a stack in python, and for our case we are going to use modules from python library. We choose 3 built in structures to do that using either a list, a Collections.deque or a queue.LifoQueue.

1.1 Implement Stack Using List

list in python known in other languages as arrays, therefore the items in the list are stored next to each other in memory, which means fast access and delete of elements.

The list implementation for stack provides append() instead of push() to add elements to the top of the stack , while pop() is available to remove the latest added element on top:

letters = []
letters.append("a")
letters.append("b")
letters.append("c")
letters
['a', 'b', 'c']
letters.pop()
'c'
letters.pop()
'b'
letters
['a']

 
// to clear and empty the stack:
letters.clear()
letters
[]

List is familiar to use and provide speed when accessing element because they are stored next each other, but the problem with list implementation is when the stack is full ( stack overflow exception), then memory reallocation is needed and that can cause performance issue where some append() calls might take much longer than other ones.

1.2 Implement Stack using collections.deque

Deque is pronounced “deck” and stands for “double-ended queue”, and it is a class from the collections' module. it is built upon a doubly linked list structure (which known as list in other languages) , each entry is stored in its own memory block and has a reference to the next and previous entry in the list.

You can use the same methods on deque as you saw above for list .append() and .pop():

 from collections import deque
 letters = deque()
 letters.append("a")
 letters.append("b")
 letters.append("c")
 letters
deque(['a', 'b', 'c'])
 letters.pop()
'c'
 letters.pop()
'b'
 letters
deque(['a'])
 letters.clear()
 letters
deque([])

Deque is preferred over the list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity compared to list which provides O(n) time complexity.

1.3 Implement Stack using queue.LifoQueue

if your program has threads, then List is not thread-safe. and for deque, you will be thread safe only if you restrict yourself to using just .append() and .pop() methods, because those operations are atomic and won’t be interrupted by a different thread.

To get around this limitation in multi thread programs, we use LifoQueue which uses .put() and .get() to add and remove elements from the stack:

Unlike deque, LifoQueue is designed to be fully thread-safe , but with a cost. because LifoQueue has to do additional work in each operation, and as a result, it takes little longer.

If you discover some performance issues, switching to a deque might be worth doing.

2. Scala Implementation

A stack in Scala is no different from python language , it is available in immutable based on list and from mutable collection class based on array, and it is ready to use.

2.1 Use Stack from mutable collections

You can create a mutable Stack with different types, and you can even use a case class as type for a stack:

import scala.collection.mutable.Stack
val numbers = Stack[Int]()
val numbers: scala.collection.mutable.Stack[Int] = Stack()
val countries = Stack[String]()
val countries: scala.collection.mutable.Stack[String] = Stack()

case class Person(val name: String)
// defined case class Person

val people = Stack[Person]()
val people: scala.collection.mutable.Stack[Person] = Stack()

You can also populate a stack with initial elements when you create it:

val numbers = Stack(1, 2, 3, 4)
val numbers: scala.collection.mutable.Stack[Int] = Stack(1, 2, 3, 4)

after you create the stack, you can add element on top of the stack using a push method:

countries.push("china")
val res0: scala.collection.mutable.Stack[String] = Stack(china)
countries.push("Brazil")
val res1: scala.collection.mutable.Stack[String] = Stack(Brazil, china)
countries.push("France")
val res2: scala.collection.mutable.Stack[String] = Stack(France, Brazil, china)

you can also push multiples element at once :

countries.pushAll(List("Zambia","Japan"))
val res3: scala.collection.mutable.Stack[String] = Stack(Japan, Zambia, France, Brazil, china)

to take elements off the top of the stack, use the pop method:

countries.pop()
val res4: String = Japan

You can peek at the next element on the stack without removing it, using top:

countries.top
val res5: String = Zambia

Stack extends from Seq, so you can inspect it with the usual methods:

 
countries.isEmpty
val res6: Boolean = false
countries.size
val res7: Int = 4

you can pop multiples elements as well:

 
countries.popAll()
val res8: scala.collection.Seq[String] = List(china, Brazil, France, Zambia)

You can empty a mutable stack with clear method:

 
countries.isEmpty
val res9: Boolean = true
countries.clear
countries.empty
val res10: scala.collection.mutable.Stack[String] = Stack()

Note: before Scala version 2.13.0, ArrayStack from mutable collection was used to implement a Stack, but now it is Deprecated, so Use Stack (which is array-based ) instead of ArrayStack.

2.2 Implement Stack Using immutable List

we can implement a Stack using immutable class object called List ( linked lists), that representing ordered collections of elements. we can push element in that case by preppend them in the front of list, and pop elements with head and tail methods.

Because we are dealing with immutable objects and functional style , we will not touch the original list. Instead, we will create a list every time we push or pop an element. Lets see an example:

 
val numbers:List[Int] = List(1,2,3,4)
val numbers: List[Int] = List(1, 2, 3, 4)
val numbersPush0 = numbers.prepended(0)
val numbersPush0: List[Int] = List(0, 1, 2, 3, 4)
scala> val numbersPushMany = numbersPush0.prependedAll(List(-2,-1))
val numbersPushMany: List[Int] = List(-2, -1, 0, 1, 2, 3, 4)

to test if our list is empty:

 
val stack = numbersPushMany
val stack: List[Int] = List(-2, -1, 0, 1, 2, 3, 4)
stack.isEmpty
val res0: Boolean = false

we can use head method to access first element from left side, and tail for the rest of element to the right side:

 
val top = stack.head
val top: Int = -2
val rest = stack.tail
val rest: List[Int] = List(-1, 0, 1, 2, 3, 4)

then to access element from the rest element, you can use the same way again

 
val top2 = rest.head
val top2: Int = -1
val rest2 = rest.tail
val rest2: List[Int] = List(0, 1, 2, 3, 4)
rest2.size
val res4: Int = 5
rest2.empty                      
val res5: List[Int] = List()     

it seems a little complicated to deal with Stack list using variables, but you gain a lot when dealing with immutable collections in some cases.

Java implementation

Stack Implementation in Java extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.

here is the output:

pop the first element: Potatoes
the top element: Cucumbers
is the stack empty: false
search for 'Potatoes' in stack: -1
pop the rest of elements:
Cucumbers
Carrots
Tomatoes
is the stack empty: true

Process finished with exit code 0

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to Stack class. The same example using Deque is presented in the next snippet:

here is the output:

pop the first element: Potatoes
the top element: Cucumbers
is the stack empty: false
pop the rest of elements:
Cucumbers
Carrots
Tomatoes
is the stack empty: true

Process finished with exit code 0

Conclusion

by now, you know that a stack is data structure based on LIFO set operations and you have seen situations where they can be used in real-life programs in 3 different programming languages.

You’ve evaluated three different options for python for implementing stacks and seen that deque is a great choice for non-threaded programs. If you’re implementing a stack in a threading environment, then it’s likely a good idea to use a LifoQueue.

For Scala, you have to use Stack from mutable class which it is array based, in preference to list implementation which is immutable and more functional oriented.

With Java implementation, you should use Stack deque interface in preference to Stack class.

Resources

---