STACK DATA STRUCTURE: COMPLETE STUDY NOTES
1. Introduction to Data Structures and Stacks
In computer science, a data structure is a specialized mechanism for organizing, storing, and accessing data efficiently. Data structures are categorized based on how elements are arranged. A linear data structure is one where elements are organized in a sequence. While you are familiar with sequences like Strings and Lists in Python, the Stack is a specific type of linear data structure that is fundamental to many computing processes.
1.1 The LIFO Principle
A stack is an arrangement of elements in a linear order where additions and removals occur from the same end, commonly referred to as the TOP. This arrangement follows the Last-In-First-Out (LIFO) principle.
To understand this, consider real-life analogies provided in the sources:
A Stack of Plates: You always place a new plate on the top of the pile. To take a plate, you remove the one from the top first.
A Pile of Books: It is physically difficult to remove a book from the bottom of a large pile without disturbing the rest; thus, you interact only with the top.
Other Examples: Bangles on a wrist, a pile of chairs, or clothes in an almirah.
In all these cases, the element inserted last is the first one to be taken out.
2. Applications of Stack
Stacks are not just theoretical; they are used extensively in programming and system architecture:
String Reversal: By pushing characters of a string onto a stack and then popping them off, the string is naturally reversed.
Undo/Redo Operations: Text and image editors use stacks to track changes. The most recent edit is pushed onto a stack; clicking "Undo" pops that change to revert to the previous state.
Browser History: When you browse web pages (P1 → P2 → P3), the browser maintains this history in a stack. Clicking the "Back" button pops the current page (P3) to reveal the previous one (P2).
4. Function Calls: Compilers and interpreters use a stack (the "Call Stack") to keep track of function calls and return addresses.
5. Parentheses Matching: When evaluating arithmetic expressions, compilers use stacks to ensure every opening parenthesis has a corresponding and properly nested closing parenthesis.
3. Fundamental Stack Operations
There are two primary operations performed on a stack: PUSH and POP.
3.1 The PUSH Operation
Definition: PUSH is an insertion operation that adds a new element to the TOP of the stack.
Exception (Overflow): A stack is "full" when it reaches its maximum capacity. Attempting to PUSH an element onto a full stack results in an exception called Overflow.
3.2 The POP Operation
Definition: POP is a deletion operation used to remove the topmost element from the stack.
Exception (Underflow): If a stack is empty (contains no elements) and you attempt to remove an element, the system triggers an exception called Underflow.
3.3 Supporting Operations
Peek/Top: This allows you to read the value of the topmost element without actually removing it.
isEmpty: A boolean check to determine if the stack contains any elements, used primarily to avoid Underflow during a POP operation.
Size: Returns the total number of elements currently in the stack.
4. Python Implementation (List-Based)
In Python, the simplest way to implement a stack is using the built-in List data type. Because Python lists are dynamic and can grow or shrink in size, we do not usually encounter the "Overflow" condition unless the system runs out of physical memory.
4.1 Mapping Stack Logic to Python Lists
To implement a stack, we fix one end of the list as the TOP. In practice, we use the rightmost end (the end of the list) as the TOP because Python's built-in list methods are optimized for this:
• append() is used for PUSH because it adds an element to the end of the list.
• pop() is used for POP because it removes the element from the end of the list.
4.2 Implementation Code Functions
Here is the modular implementation of a stack in Python as described in the sources:
# Function to check if the stack is empty
def isEmpty(stk):
if len(stk) == 0:
return True
else:
return False
# Function to PUSH an element
def opPush(stk, element):
stk.append(element) # Always adds to the end (TOP)
# Function to POP an element
def opPop(stk):
if isEmpty(stk):
print('Underflow') # Error handling for empty stack
return None
else:
return stk.pop() # Removes and returns the last element
# Function to PEEK (read TOP element)
def top(stk):
if isEmpty(stk):
print('Stack is empty')
return None
else:
return stk[-1] # Returns the last element without removing it
# Function to get current SIZE
def size(stk):
return len(stk)
# Function to DISPLAY stack contents
def display(stk):
if isEmpty(stk):
print("Stack is empty")
else:
print("Current elements (TOP to BOTTOM):")
# Traverse backward to show TOP first
for i in range(len(stk)-1, -1, -1):
print(stk[i])
5. Arithmetic Expression Notations
Arithmetic expressions are typically written with operators between operands (e.g., x+y). This is known as Infix notation. However, for computers to evaluate complex expressions without parentheses, other notations are used.
5.1 Infix Notation
Structure: Operators are placed in between operands (e.g., 3∗(4+5)).
Evaluation: Requires the BODMAS rule and parentheses to handle operator precedence.
5.2 Prefix (Polish) Notation
Structure: Operators are placed before the corresponding operands (e.g., +xy).
History: Introduced by Jan Lukasiewicz in the 1920s.
Benefit: Parentheses are unnecessary because the order of operations is determined by the position.
5.3 Postfix (Reverse Polish) Notation
Structure: Operators are placed after the corresponding operands (e.g., xy+).
Benefit: Like Prefix, a single left-to-right traversal is sufficient for a computer to evaluate the result without needing to check for precedence rules or parentheses.
6. Conversion: Infix to Postfix
To pass the "knowledge" of operator precedence to a computer, we convert Infix to Postfix using a stack.
6.1 The Conversion Algorithm
Initialize: Create an empty stack for operators and an empty string (postExp) for the result.
Scan: Process the Infix expression from left to right.
Operands: If the character is an operand (like x,y, or a number), append it to postExp.
Left Parenthesis (: PUSH it onto the stack.
Right Parenthesis ): POP elements from the stack and append them to postExp until a left parenthesis is reached. Discard both parentheses.
6. Operators:
If the stack is empty or contains a (, PUSH the operator.
If the current operator has lower precedence than the operator at the TOP of the stack, POP the stack and append to postExp until an operator with lower precedence is found, then PUSH the current operator.
Otherwise, PUSH the operator.
7. Finalize: Once the Infix expression is fully scanned, POP all remaining operators from the stack and append to postExp.
-----------------------------------------------------------------------
6.2 Example Walkthrough
Converting (x + y) / (z * 8):
• Scan (: PUSH ( to stack.
• Scan x: postExp = x.
• Scan +: PUSH + to stack.
• Scan y: postExp = xy.
• Scan ): POP + and append. postExp = xy+. Stack is now empty.
• Scan /: PUSH / to stack.
• Scan (: PUSH ( to stack.
• Scan z: postExp = xy+z.
• Scan : PUSH to stack.
• Scan 8: postExp = xy+z8.
• Scan ): POP and append. postExp = xy+z8.
• End of input: POP remaining /.
• Final Postfix: xy + z 8 * /.
7. Evaluation of Postfix Expressions
Once an expression is in Postfix, the computer uses a stack to find the numerical result.
7.1 The Evaluation Algorithm
1. Initialize: Create an empty stack.
2. Scan: Process the Postfix expression from left to right.
3. Operands: If the character is an operand (a number), PUSH it onto the stack.
4. Operators:
◦ POP two elements from the stack.
◦ Apply the operator to these two elements (the first POP is the second operand; the second POP is the first operand).
◦ PUSH the result back onto the stack.
5. Result: When the scan is complete, the stack will have exactly one element, which is the final output.
7.2 Example Walkthrough
Evaluating 7 8 2 * 4 / +:
1. Scan 7: Stack =
2. Scan 8: Stack =
3. Scan 2: Stack =
4. Scan *: POP 2, POP 8. Calculate 8∗2=16. PUSH 16. Stack = .
5. Scan 4: Stack =
6. Scan /: POP 4, POP 16. Calculate 16/4=4. PUSH 4. Stack = .
7. Scan +: POP 4, POP 7. Calculate 7+4=11. PUSH 11.
8. Final Result: 11.
8. Summary Table: Stack Features
Feature | Description |
Arrangement | Linear Data Structure |
Logic | Last-In-First-Out (LIFO) |
Access Point | TOP (All operations occur here) |
Insertion | PUSH Operation |
Deletion | POP Operation |
Python Tool | List (with append and pop) |
Conversion Use | Tracking operators/parentheses |
Evaluation Use | Tracking operands/results |