Stacks in Python
1. Introduction
In computer science, a stack is a data structure that stores a collection of elements and operates on the principle of last-in, first-out (LIFO). In a stack, elements are added to the top of the stack and removed from the top of the stack. This makes a stack an ideal data structure for many programming tasks, such as parsing expressions, evaluating postfix expressions, and implementing undo and redo operations.
2. Basics of Stacks
A stack is a linear data structure that stores a collection of elements in a specific order. It operates on the LIFO principle, which means that the last element added to the stack will be the first element removed from the stack. This is in contrast to a queue, which operates on the FIFO (first-in, first-out) principle.
A stack can be thought of as a physical stack of items, such as a stack of plates in a restaurant. When a new plate is added to the stack, it is placed on top of the existing plates. When a plate is removed from the stack, it is taken from the top of the stack.
The two basic operations performed on a stack are push and pop. The push operation adds an element to the top of the stack, while the pop operation removes the element from the top of the stack. Additionally, a stack may provide other operations, such as peek, which returns the top element of the stack without removing it, and isEmpty, which checks whether the stack is empty or not.
3. Implementing a Stack in Python
In Python, a stack can be implemented using the built-in list data type. The append()
method can be used to add an element to the top of the stack, and the pop()
method can be used to remove the element from the top of the stack. The following code demonstrates how to implement a stack in Python:
stack = []
# push operation
stack.append(1)
stack.append(2)
stack.append(3)
# pop operation
x = stack.pop()
print(x)
# Output: 3
In this example, we create an empty stack using a Python list. We then add three elements to the stack using the append()
method. Finally, we remove the top element from the stack using the pop()
method and assign it to the variable x.
The peek operation, which returns the top element of the stack without removing it, can be implemented using indexing:
stack = [1, 2, 3]
# peek operation
x = stack[-1]
print(x)
# Output: 3
This code creates a stack with three elements and retrieves the top element using indexing.
4. Applications of Stacks in Python
Stacks are widely used in computer science and software development. Here are some practical applications of stacks in Python programming:
4.1. Parentheses Matching
Stacks can be used to check whether a sequence of parentheses is balanced or not. This is a common problem in programming, where it is important to ensure that opening parentheses are matched with closing parentheses.
def is_balanced(expression):
stack = []
for char in expression:
if char == '(':
stack.append(char)
elif char == ')':
if len(stack) == 0:
return False
stack.pop()
return len(stack) == 0
# Example usage
print(is_balanced('((()))')) # Output: True
print(is_balanced('(()))')) # Output: False
In this example, we define a function is_balanced()
that checks whether a given expression has balanced parentheses. The function uses a stack to keep track of opening parentheses and remove them when closing parentheses are encountered. If there are any opening parentheses left in the stack after processing the expression, the function returns False, indicating that the parentheses are not balanced.
4.2. Infix to Postfix Conversion
Stacks can be used to convert an infix expression to postfix notation, which is a more suitable form for evaluating mathematical expressions. In postfix notation, the operators come after the operands, making it easier to evaluate the expression using a stack.
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
output = ''
for char in expression:
if char.isdigit():
output += char
elif char in precedence:
while len(stack) > 0 and stack[-1] != '(' and precedence[char] <= precedence[stack[-1]]:
output += stack.pop()
stack.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while len(stack) > 0 and stack[-1] != '(':
output += stack.pop()
stack.pop()
while len(stack) > 0:
output += stack.pop()
return output
# Example usage
print(infix_to_postfix('2+3*4')) # Output: '234*+'
In this example, we define a function infix_to_postfix()
that converts an infix expression to a postfix notation. The function uses a stack to keep track of operators and operands as they are processed. Operators are added to the stack if they have higher precedence than the previous operator, and they are popped from the stack and added to the output if they have lower precedence.
4.3. Function Call Stack
Stacks are used by programming languages to keep track of function calls. When a function is called, its state is pushed onto the call stack, including its parameters and local variables. When the function returns, its state is popped from the call stack, and the program continues executing from where it left off.
def foo(x):
y = x * 2
bar(y)
return y
def bar(x):
z = x + 1
return z
# Example usage
print(foo(3)) # Output: 7
In this example, we define two functions, foo()
and bar()
, that call each other. When foo() is called with an argument of 3, its state is pushed onto the call stack. It then calls bar()
with an argument of 6, which pushes its state onto the call stack. When bar()
returns a value of 7, its state is popped from the call stack and foo()
continues executing with a return value of 7.
5. Conclusion
In this blog, we discussed the basics of stacks, how to implement a stack in Python using lists, and some practical applications of stacks in Python programming. Stacks are fundamental data structures that are widely used in computer science and software development. They provide a simple and efficient way to store and retrieve elements in a specific order and can be used for a variety of tasks, such as parsing expressions, converting infix to postfix notation, and implementing function call stacks.