6.1 Stack Definition and Its Properties
Stack is an abstract data structure representing a collection of elements organized by the "last in, first out" (LIFO) principle. You can think of a stack like a stack of books: the last book added is on top and will be the first one to be removed or taken.
Stack Properties:
- LIFO (Last In, First Out): The last added element is the first to be removed.
- Limited Operations: Only push, pop, and peek operations are supported.
- One-way Access: You can only access elements from the top of the stack.
- Simple Implementation: A stack can easily be implemented using an array or linked list.
- Memory Management: Temporary data or states can be stored and retrieved in reverse order of addition.
LIFO Principle:
- Push Operation: A new element is added to the top of the stack.
- Pop Operation: The last added element is removed from the top of the stack.
- Peek Operation: Allows viewing the top element of the stack without removing it.
Elements in a stack are added and removed from one end, known as the top. Thus, the last added element is always at the top and will be the first to be removed.
6.2 Main Operations
Main operations: push, pop, peek
Push Operation: Adds a new element to the top of the stack.
Time Complexity: O(1).
Example of stack emulation in Python using a list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Output: [10, 20]
Pop Operation: Removes and returns the top element of the stack.
Time Complexity: O(1).
Example of stack emulation in Python using a list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Output: 20
print(stack) # Output: [10]
Peek Operation: Returns the top element of the stack without removing it.
Time Complexity: O(1).
Example of implementation:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Output: 10
6.3 Stack Usage Examples
Let's go over some examples of stack usage:
Function Call Management
In Python, a stack is used to track functions during program execution. Every time a function is called, its return address and local variables are pushed onto the stack. When the function finishes executing, control returns to the calling function, and data is popped from the stack.
Example of Call Stack Usage:
In this example, recursive calls to the factorial function use a call stack to store the state of each call until a base condition (n == 1) is met.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Output: 120
Undo Operations
A stack is used to implement the undo feature in text editors and other applications. When a user performs an action, it is pushed onto the stack. When an Undo operation is performed, the last action is popped from the stack and undone.
Example of using a stack for undo operations:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Usage example:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Output: "Hello World"
editor.undo()
print(editor.text) # Output: "Hello"
editor.undo()
print(editor.text) # Output: ""
GO TO FULL VERSION