Stacks in Data Structure
Using the Last-In, First-Out (LIFO) principle, Stacks in Data Structure are a basic linear data structure. This implies that the first item to be deleted is the one that was inserted most recently. A spring-loaded cafeteria plate dispenser or a PEZ® candy dispenser, in which plates or candies are added to the top and taken out of the top, are frequently used as analogies to explain Stacks in Data Structure .
Core Concepts and Operations
An Abstract Data Type (ADT) that usually supports a particular set of operations is called a stack.
Push (S.push(e)): An element e is added to the top of the stack by using the push function (S.push(e)). An “Overflow” condition may result if the stack is full.
Pop (S.pop()): Takes the top element out of the stack and returns it. In the opposite sequence as they were pushed, the elements are popped. When attempting to pop from an empty stack, a “Underflow” condition is encountered.
Top / Peek (peek()): Returns a reference to the top element of the stack without deleting it when you use Top (S.top()) / Peek (peek()).
isEmpty: A basic accessor operation used in many different data structures to determine whether they contain any members is isEmpty (or is empty()). If the data structure is empty, this method returns True; if not, it returns False.
len(S): One popular built-in function in Python for figuring out how many elements are in a sequence or collection S is len(S). A wide range of data structures, including as strings, lists, tuples, sets, dictionaries, stacks, queues, deques, priority queues, and trees, can be used with this flexible function. For example, len(string) yields the string’s length, len(data) yields the list’s element count, and len(P) yields the priority queue item count.
A newly constructed stack is typically regarded as empty, and its capacity is unbounded, allowing components of any kind.
Applications of Stacks
Stacks in Data StructureStacks in data structure are essential for many types of computer applications. Here are a few typical examples:
Web browsers: Web browsers are modern software tools that let you access information on the Internet and interact with it. Python’s mobility makes it ideal for designing huge programs that must adapt to changing contexts.
Text editors:Text editors handle and manipulate textual documents, which are generally character sequences. Positional insertion and deletion, where actions are conducted relative to a cursor indicating the text’s present position, is central to their design.
Compilers and syntax parsers: Verifying that delimiters (such as brackets []), braces, and brackets () are opened and closed correctly in HTML tags or arithmetic expressions.
Function Calls/Recursion Management: When a new function is called, the Python interpreter pushes an activation record, and when a function terminates, it pops it. This “call stack” keeps track of all active function invocations. Recursion can also be avoided by using stacks to manually manage the recursive structure.
Expression Evaluation:Python interpreters process variables, constants, and operators to evaluate expressions. Before binding the result to the left variable, this method evaluates the right-hand expression of an assignment. The ‘+’ operator adds numbers but concatenates texts.
Stack Implementation using Python List
A Python list can be used as the underlying storage for a stack with ease. The end of the Python list and the top of the stack are inherently aligned.
- push(e): Immediately responds to the append(e) method of the list.
- pop(): Identifies the pop() method of the list, which returns and eliminates the final entry.
- top()/peek(): Uses L[-1] to access the final element.
- Len(L) == 0 is checked using is_empty().
- len(S): Len(L) is returned.
Creating a specific ArrayStack class enables the strict stack ADT behaviour and terminology to be maintained, even when using a Python list directly works. When pop() or top() are invoked on an empty stack, an Empty exception can be defined.
Efficiency: Because of the dynamic resizing of the Python list, push() and pop() operations for an array-based stack employing the list have an amortised O(1) running time. The worst-case time for the top(), is_empty(), and len() functions is O(1). O(n), where n is the number of items, is the space utilisation.
Example:
class Empty(Exception):
"""Error attempting to access an element from an empty container."""
pass
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def _init_(self):
"""Create an empty stack."""
self._data = [] # nonpublic list instance
def _len_(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
def push(self, e):
"""Add element e to the top of the stack."""
self._data.append(e) # new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1] # the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty('Stack is empty')
return self._data.pop() # remove last item from list
# Demonstration of ArrayStack
if _name_ == "__main_":
my_stack = ArrayStack()
print(f"Is stack empty initially? {my_stack.is_empty()}")
print(f"Current stack size: {len(my_stack)}")
print("\nPushing elements: 10, 20, 30")
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)
print(f"Is stack empty after pushes? {my_stack.is_empty()}")
print(f"Current stack size: {len(my_stack)}")
print(f"Top element: {my_stack.top()}")
print("\nPopping an element...")
popped_item = my_stack.pop()
print(f"Popped: {popped_item}")
print(f"Current stack size: {len(my_stack)}")
print(f"Top element: {my_stack.top()}")
print("\nPopping another element...")
popped_item = my_stack.pop()
print(f"Popped: {popped_item}")
print(f"Current stack size: {len(my_stack)}")
print(f"Top element: {my_stack.top()}")
print("\nPopping the last element...")
popped_item = my_stack.pop()
print(f"Popped: {popped_item}")
print(f"Current stack size: {len(my_stack)}")
print(f"Is stack empty now? {my_stack.is_empty()}")
print("\nAttempting to top an empty stack (should raise Empty exception):")
try:
my_stack.top()
except Empty as e:
print(f"Caught exception: {e}")
print("\nAttempting to pop from an empty stack (should raise Empty exception):")
try:
my_stack.pop()
except Empty as e:
print(f"Caught exception: {e}")Output:
Is stack empty initially? True
Current stack size: 0
Pushing elements: 10, 20, 30
Is stack empty after pushes? False
Current stack size: 3
Top element: 30
Popping an element
Popped: 30
Current stack size: 2
Top element: 20
Popping another element
Popped: 20
Current stack size: 1
Top element: 10
Popping the last element
Popped: 10
Current stack size: 0
Is stack empty now? True
Attempting to top an empty stack (should raise Empty exception):
Caught exception: Stack is empty
Attempting to pop from an empty stack (should raise Empty exception):
Caught exception: Stack is empty