---
slideOptions:
theme: white
---
# Chapter 13 - Stacks
###### tags: `Data Structure and Algorithms`
---
## Learning objectives
By the end of this chapter, you should be able to:
1. Define stack in programming
2. Explain the basic operations of a stack, i.e. _push_ and _pop_
3. Describe the application of stacks in computer science
## Basic Concept
A _stack_ is a _restricted linear list_ in which all additions and deletions are restricted to one end, called the _top_. This is known as the _**last in-first out (LIFO)**_ data structure.
In a stack, all data must be input and output through the top.
### Node
To create a stack, we need to define the nodes and the head structure, like the linked list.
The variable `count` in `Stack` refers to the top of the stack.
### Basic Operations
There are two basic operations of stacks, namely _push_ and _pop_.
#### Push
_Push_ adds an item at the top of the stack. After the push, the new item becomes the top. It is similar to the _insertion_ of the last node of a linear linked list. Below shows an example.
##### Stack overflow
If there is not enough room to push the node, then the stack is an _overflow_ state and the object cannot be added.
#### Pop
_Pop_ removes the top node from the stack. It is similar to the _deletion_ of the first node of a linear linked list. Below shows an example.
##### Stack underflow
If pop is called when the stack is empty, then it is in an _underflow_ state.
## Array implementation
When implementing a stack in an array, the base is found at the first stack element, index 0 in Python. The top then moves up and down the array as data is inserted and deleted. The structure for the array implementation with a maximum size of 5 elements is shown below.
A more complex form can also be implemented, as shown below.
For an easier understanding, we can use the following code to create a list with 4 spaces and some useful variables first. Notice that the count needs to be a list so that it can be worked as a pointer.
```python=
count = [0]
stack = [None, None, None, None]
```
We can read the stack directly by the print function.
```python!
print(stack)
```
Output:
```
[None, None, None, None]
```
### Basic operations
#### Push
Below shows the algorithm of _push_ in the array implementation.
```
Algorithm push (stack, head, data)
Insert (push) one item into the stack.
Pre stack passed by reference
head is the pointer to the top
data contain data to be pushed into stack
1 store data in new node
2 increment stack count (head)
end push
```
After _push_, the new item should be pushed on the _top_ of the stack. THe operation is the same as the _insertion_ of the first item of an array-implemented linked list.
The following shows the _push_ operation diagramatically.
With the above pseudocode, we can implement the above algorithm in Python as follows.
```python!
def push(list, head, data):
"""
This function used to push data into the
specific stack
Args:
list: the pointer to the stack
top: the pointer to the top of the stack
data: data to be inserted
"""
list[head[0]] = data
head[0] = head[0] + 1
```
Now, print out the list and see the result.
```python!
print(stack)
push(stack, count, 3)
print("head =", count)
print(stack)
```
Output:
```
[None, None, None, None]
head = [1]
[3, None, None, None]
```
#### Pop
_Pop_ removes the top item from the stack. It is similar to the _deletion_ of the last item of an array-implemented linear linked list. Below shows the pseudocode of the _pop_ algorithm.
```
Algorithm pop (list, head)
Insert (push) one item into the stack.
Pre stack passed by reference
data contain data to be pushed into stack
Post data pop from the stack
1 decrement stack count (head)
2 store new data from the top node
3 remove the data from the top node
4 return data
end push
```
Below shows the above algorithm diagramatically.
Suppose we have a stack as shown below.
With the above pseudocode, we can implement the above algorithm in Python as follows.
```python!
def pop(list, head):
"""
This function used to pop data from the
specific stack
Args:
list: the pointer to the stack
head: the pointer to the top of the stack
Returns:
data pop from the stack
"""
head[0] = head[0] - 1
data = list[head[0]]
list[head[0]] = None
return data
```
Now, print out the list and see the result.
```python!
push(stack, count, 3)
push(stach, count, 6)
print(stack)
print(pop(stack, count))
print("head =", count)
print(stack)
```
Output:
```
[3, 6, None, None]
6
head = [1]
[3, None, None, None]
```
## Linked list implementation
### Node
To create a stack, we need to define the nodes and the head structure. Below shows an example.
### Display the stack
It is almost the same to display the stack as the linked list. The algorithm is shown below.
```
Algorithm display ()
Display the stack on the screen.
1 set node to start
2 while the next node is not None
display the node data
set node to the next node
3 print out the last node data
```
The Python implementation is shown below.
```python!
def display(self):
"""
This function used to display the stack,
concatenate with " -> "
"""
node = self.top
while node.next != None:
print(node.data, end=" -> ")
node = node.next
print(node.data)
```
### Basic operations
#### Push
_Push_ adds an item at the top of the stack. After push, the new item becomes the top. The pseudocode is shown below.
```
Algorithm push (data)
Insert (push) one item into the stack.
Pre data contain data to be pushed into stack
1 store data in new node
2 make the current top node the second node
3 make new node the top
4 increment stack count
end push
```
The algorithm can be presented as the following diagrams.
The following shows the Python implementation of the push operation. Notice that this is one of the methods of the Stack class, but not a global function.
```python!
def push(self, data):
"""
This function used to push data into the
specific stack
Args:
data: data to be inserted
"""
node = Node(data)
node.next = self.top
self.top = node
self.count = self.count + 1
```
We can check the algorithm as shown below.
```python!
stack = Stack()
stack.push(3)
stack.push(6)
stack.push(9)
stack.display()
```
Output:
```
9 -> 6 -> 3
```
#### Pop
_Pop_ removes the top node from the stack. It is similar to the _deletion_ of the first node of a linear linked list. Below shows the pseudocode of the _pop_ algorithm.
```
Algorithm pop ()
This algorithm pops the item on the top of the stack and returns it to the user
Return the pop data
1 point to the top node
2 extract from the top node data
3 set the second top node as the top node
4 decrement the stack count
5 return the data extracted
end pop
```
The algorithm can be presented as the following diagrams.
The following shows the Python implementation of the push operation. Notice that this is one of the methods of the Stack class, but not a global function.
```python!
def pop(self):
"""
This function used to pop data from the
specific stack
Returns:
data pop from the stack
"""
node = self.top
data = node.data
self.top = node.next
self.count = self.count - 1
return data
```
We can check the algorithm as shown below.
```python!
stack.display()
print("Pop value:", stack.pop())
stack.display()
```
Output:
```
9 -> 6 -> 3
Value pop: 9
6 -> 3
```
## Application in Computer Science
There are four common stack applications in Computer Science, namely _reversing data_, _parsing_, _postponing_, and _backtracking_.
### Reversing data
To reverse a list, it is simply to _push_ the list to the stack and then _pop_ them out. Below shows an example.
### Parsing
Another application of stack is _parsing_. _Parsing_ is any logic that brbreaksata into independent pieces for further processing.
Below shows an example on checking the parenthesis.
### Postponing
When we used a stack to reverse a list, the entire list was read before we began outputting the result. Often the logic of an application requires that the usage of data be deferred until some later point.
#### Infix to Postfix Transformation
The compiler of some high-level language transforms the infix notation (e.g. a+b) into postfix notation (e.g. ab+) by using a stack, which helps to operate the operations by the computer.
Several rules are required to be set for the transformation.
1. Setting priority levels for each operator, as shown below.
a. Priority 3 (highest) : (
b. Priority 2: \*/
c. Priority 1 (lowest): +-
2. Scan through an expression, getting one token at a time.
3. If the token is an operand, do not stack it; pass it to the output.
4. If the token is an operator or parenthesis, do the following,
a. _Pop_ the stack until you find a symbol of _lower_ priority number than the current one
b. An incoming _left parenthesis_ will be considered to have higher priority than any other symbol. A left parenthesis on the stack will not be removed unless an incoming right parenthesis is found.
c. The popped stack elements will be written to output.
d. _Stack_ the current symbol.
e. If a _right parenthesis_ is the current symbol, pop the stack down to (and including) the first left parenthesis.
f. Write all the symbols except the left parenthesis to the output (i.e. write the operators to the output).
g. After the _last token_ is read, _pop the remainder_ of the stack and write any symbol (except left parenthesis) to output.
By using the above rules, we can transform the following expression.
```!
A + B \* C - D / E converts to A B C \* + D E / -
```
The transformation of this expression is shown in the following diagram
#### Postfix Expression Evaluation
The computer can evaluate the postfix expression with the stack, as follows.
### Backtracking
_Backtracking_ is another stack use found in applications such as computer gaming, decision analysis and expert systems.
Sign in with Wallet
Connect another wallet