Stack#
A stack (sometimes called a “push-down stack”) is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “top”. The end opposite the top is known as the “base”.
The base of the stack is significant since items stored in the stack that are closer to the base represent those that have been in the stack the longest. The most recently added item is the one that is in position to be removed first. This ordering principle is sometimes called LIFO(last-in, first-out). It provides an ordering based on length of time in the collection. Newer items are near the top, while older items are near the base.
Examples
Almost any cafeteria has a stack of trays or plates where you take the one at the top, uncovering a new tray or plate for the next customer in line.
Every web browser has a Back button. As you navigate from web page to web page, those pages are placed on a stack (actually it is the URLs that are going on the stack). The current page that you are viewing is on the top and the first page you looked at is at the base. If you click on the Back button, you begin to move in reverse order through the pages.
Stack Abstract Data Type#
The stack abstract data type is defined by the following structure and operations. A stack is structured, as described above, as an ordered collection of items where items are added to and removed from the end called the top. Stacks are ordered LIFO.
Stack Operations#
Stack()creates a new stack that is empty. It needs no parameters and returns an empty stack.push(item)adds a new item to the top of the stack. It needs the item and returns nothing.pop()removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.peek()returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.is_empty()tests to see whether the stack is empty. It needs no parameters and returns a boolean value.size()returns the number of items on the stack. It needs no parameters and returns an integer.
s = Stack() creates a stack that starts out empty, table below shows the results of a sequence of stack operations.
Stack Operation |
Stack Contents |
Return Value |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Implementing a Stack in Python#
An abstract data type (ADT) when given a physical implementation then we refer to the implementation as a data structure.
In any object-oriented programming language, the implementation of choice for an abstract data type such as a Stack is the creation of a new class. The stack operations are implemented as methods. Further, to implement a stack, which is a collection of elements, it makes sense to utilize the primitive collections provided.
Python provides List an ordered collection mechanism and a set of methods, we need only to decide which end of the list will be considered the top of the stack and which will be the base. Once that decision is made, the operations can be implemented using the list methods.
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def is_empty(self):
return self.items == []
def size(self):
return len(self.items)
# Create a new stack
s = Stack()
# Check if the stack is empty
print(s.is_empty())
# Push 4 at top of stack
s.push(4)
# Push "dog" at top of stack
s.push('dog')
# Give the top element of the stack
print(s.peek())
# Push "True" at top of stack
s.push(True)
# Give the size of the stack
print(s.size())
# Check if the stack is empty
print(s.is_empty())
# Push 8.4 at top of stack
s.push(8.4)
# Pop the top element from the stack and return it
print(s.pop())
# Pop the top element from the stack and return it
print(s.pop())
# Give the size of the stack
print(s.size())
True
dog
3
False
8.4
True
2
Practical usage in python#
list and collections.deque module provides an implementation of the stack data structure, you can find more information about the interface and api from list and deque docs.
Practice Problems#
Write a function reverse_string(mystr) that reverses the characters in a string.#
def reverse_string(mystr):
s = Stack()
for ch in mystr:
s.push(ch)
reverse_string = ""
while not s.is_empty():
reverse_string += s.pop()
return reverse_string
print(reverse_string('0123456789'))
print(reverse_string('apple'))
print(reverse_string('Take me down to the paradise city ...'))
9876543210
elppa
... ytic esidarap eht ot nwod em ekaT
Write a function parentheses_checker(expression) that tells if the expression has balanced parentheses.#
def parentheses_checker(expression):
opening_parentheses = ["(", "[", "{"]
closing_parentheses = [")", "]", "}"]
s = Stack()
balanced = True
for ch in expression:
if ch in opening_parentheses:
s.push(ch)
else:
if s.is_empty():
balanced = False
else:
top_parentheses = s.pop()
if opening_parentheses.index(top_parentheses) != closing_parentheses.index(ch):
balanced = False
return balanced and s.is_empty()
print(parentheses_checker('((()))'))
print(parentheses_checker('(()'))
print(parentheses_checker('{({([][])}())}'))
print(parentheses_checker('[{()]'))
True
False
True
False
Write a function base_convert(number, base) that converts decimal integers to integer in another base system (upto 16).#
def base_convert(number, base):
digits = "0123456789ABCDEF"
remainders = Stack()
while number:
remainders.push(number % base)
number = number // base
converted_number = ""
while not remainders.is_empty():
digit = digits[remainders.pop()]
converted_number += digit
return converted_number
# Convert 42 from decimal to different base number systems
print(base_convert(42, 2))
print(base_convert(42, 4))
print(base_convert(42, 8))
print(base_convert(42, 16))
# Convert 1995 from decimal to different base number systems
print(base_convert(1995, 2))
print(base_convert(1995, 4))
print(base_convert(1995, 8))
print(base_convert(1995, 16))
101010
222
52
2A
11111001011
133023
3713
7CB
Write a function infix_to_postfix(expression) that converts an expresion from infix notation to postfix notation.#
Create an empty stack called opstack for keeping operators. Create an empty list for output.
Convert the input infix string to a list by using the string method split.
Scan the token list from left to right.
If the token is an operand, append it to the end of the output list.
If the token is a left parenthesis, push it on the opstack.
If the token is a right parenthesis, pop the opstack until the corresponding left parenthesis is removed. Append each operator to the end of the output list.
If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.
When the input expression has been completely processed, check the opstack. Any operators still on the stack can be removed and appended to the end of the output list.
def infix_to_postfix(expression):
precedence = {
"^": 4,
"*": 3,
"/": 3,
"+": 2,
"-": 2,
"(": 1
}
postfix_list = []
op_stack = Stack()
token_list = expression.split()
for token in token_list:
if token.isdigit() or token.isalpha():
postfix_list.append(token)
elif token == "(":
op_stack.push(token)
elif token == ")":
while op_stack.peek() != "(":
postfix_list.append(op_stack.pop())
op_stack.pop()
else:
while not op_stack.is_empty() and precedence[op_stack.peek()] >= precedence[token]:
postfix_list.append(op_stack.pop())
op_stack.push(token)
while not op_stack.is_empty():
postfix_list.append(op_stack.pop())
return " ".join(postfix_list)
print(infix_to_postfix("A * B + C * D"))
print(infix_to_postfix("( A + B ) * C - ( D - E ) * ( F + G )"))
print(infix_to_postfix("( 1 + 2 ) - 3 * 4 / 5"))
print(infix_to_postfix("10 + 3 * 5 / ( 16 - 4 )"))
print(infix_to_postfix("5 * 3 ^ ( 4 - 2 )"))
A B * C D * +
A B + C * D E - F G + * -
1 2 + 3 4 * 5 / -
10 3 5 * 16 4 - / +
5 3 4 2 - ^ *
Write a function evaluate_postfix(expression) that evaluates an expresion in postfix notation.#
Assume the postfix expression is a string of tokens delimited by spaces. The operators are *, /, +, and - and the operands are assumed to be single-digit integer values. The output will be an integer result.
Create an empty stack called operandStack.
Convert the string to a list by using the string method split.
Scan the token list from left to right.
If the token is an operand, convert it from a string to an integer and push the value onto the operandStack.
If the token is an operator, *, /, +, or -, it will need two operands. Pop the operandStack twice. The first pop is the second operand and the second pop is the first operand. Perform the arithmetic operation. Push the result back on the operandStack.
When the input expression has been completely processed, the result is on the stack. Pop the operandStack and return the value.
from operator import add, sub, mul, truediv, mod, pow
def evaluate_postfix(expression):
operators = {
"+": add,
"-": sub,
"*": mul,
"/": truediv,
"^": pow,
}
operands = Stack()
token_list = expression.split()
for token in token_list:
if token.isdigit():
operands.push(int(token))
else:
operand_2 = operands.pop()
operand_1 = operands.pop()
exp = operators[token](operand_1, operand_2)
operands.push(exp)
return operands.pop()
print(evaluate_postfix('7 8 + 3 2 + /'))
print(evaluate_postfix('17 8 + 3 2 + /'))
3.0
5.0