Stacks:
A stack is a linear data structure that follows a particular order in which operations are performed. The order is Last In, First Out (LIFO), meaning the last element added to the stack will be the first one to be removed.
Key Operations
1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.
3. Peek (or Top): Returns the top element without removing it from the stack.
4. isEmpty: Checks if the stack is empty.
5. Size: Returns the number of elements in the stack.
Stack Representation:
A stack can be represented in two ways:
1. Using Arrays (Static Implementation):
An array is used to store stack elements.
A variable is used to keep track of the index of the top element.
Limitation: Fixed size.
2. Using Linked List (Dynamic Implementation):
Each node contains data and a reference to the next node.
The top pointer points to the last inserted node.
No size limitation, grows dynamically as needed.
Push Operation
• Array-Based Stack: Add the element at the index pointed by top and increment the top.
• Linked List-Based Stack: Create a new node, set its next to the current top node, and update the top pointer to the new node.
Pop Operation
• Array-Based Stack: Return the element at top and decrement the top.
• Linked List-Based Stack: Return the data of the top node, update the top pointer to the next node, and delete the current top node.
Time Complexity
• Push: O(1) – Inserting at the top of the stack.
• Pop: O(1) – Removing the top element.
• Peek: O(1) – Accessing the top element.
• sEmpty: O(1) – Checking if the stack is empty.
Advantages • Simple and easy to implement.
• Efficient for LIFO operations. Disadvantages
• Array-Based: Fixed size can cause overflow.
• Linked List-Based: Requires extra memory for pointer storage.
Disadvantages
• Array-Based: Fixed size can cause overflow.
• Linked List-Based: Requires extra memory for pointer storage.
Application:
Applications of Stack
1. Expression Evaluation: Used to evaluate postfix expressions or convert infix to postfix/prefix.
2. Backtracking: For example, to implement the undo functionality in text editors or for navigating browsers' back button.
3. Recursion: The system stack is used to keep track of function calls.
4. Balancing Symbols: Used to check for balanced parentheses in expressions.
5. Depth First Search (DFS): In graph traversal, a stack is used to explore nodes.
Array Representation:
In the array representation of a stack, an array is used to store the stack's elements, and an integer variable (typically named top) keeps track of the index of the top element in the stack. This approach is often called a static implementation because the size of the array is fixed once it is defined.
Structure
• Array: The array is used to hold the stack elements.
• Top: A pointer or index that points to the top of the stack, representing the last inserted element.
Important Concepts
1. Initial State: o When the stack is empty, top is initialized to -1 (indicating no elements are present in the stack).
2. Push Operation:
When an element is pushed onto the stack, the top index is incremented by 1, and the element is inserted at the new top position in the array.
3. Pop Operation: o When an element is popped from the stack, the element at the position indicated by top is removed, and the top index is decremented by 1.
4. Overflow Condition:
If top is equal to max_size - 1 (where max_size is the size of the array), the stack is full and cannot accommodate any more elements, leading to a stack overflow.
5. Underflow Condition: o If top is -1, the stack is empty, and attempting to pop an element will result in stack underflow.
Advantages of Array-Based Stack:
• Simple and efficient for small stacks.
• Fast access to elements using indexing.
Disadvantages of Array-Based Stack:
• Fixed size: If the maximum size is reached, no more elements can be pushed unless the array is resized.
• Wasted space: If the stack is not full, the array may have unused space.
Linked Representation:
In a linked list representation of a stack, a linked list is used to store the elements of the stack. This approach is also called a dynamic implementation because the size of the stack is not fixed, and it can grow or shrink dynamically as elements are pushed or popped.
Structure
• Node: Each element in the stack is represented by a node in the linked list. A node contains two parts:
1. Data: The value stored in the node.
2. Next: A pointer (or reference) to the next node in the stack (linked list).
• Top: A pointer (or reference) that points to the top node in the stack (the last inserted node).
Important Concepts
1. Initial State:
When the stack is empty, top is initialized to None, indicating that there are no elements in the stack.
2. Push Operation:
A new node is created with the given value.
The next pointer of the new node is set to the current top.
The top pointer is updated to point to the new node.
3. Pop Operation:
The top node is removed by updating the top pointer to point to the next node in the list.
The data in the removed node is returned.
4. Overflow Condition:
In a linked list-based stack, there is no overflow unless the system runs out of memory.
5. Underflow Condition:
If the top is None, the stack is empty, and popping an element will result in a stack underflow.
Key Operations
1. Push Operation:
Create a new node, set its next to the current top, and update the top pointer to point to the new node.
2. Pop Operation:
Set the top pointer to the next node (the one below the current top) and remove the current top node.
3. Peek Operation:
Return the value of the top node without modifying the stack.
Advantages of Linked List-Based Stack:
1. Dynamic Size: The stack can grow and shrink dynamically, unlike array-based stacks, which have a fixed size.
2. No Overflow: There’s no stack overflow as long as the system has enough memory, unlike array-based stacks where you can run into overflow issues if the array is full.
3. Efficient Memory Utilization: Memory is allocated dynamically for each node, so there’s no wasted space.
Disadvantages of Linked List-Based Stack:
1. Memory Overhead: Each node requires additional memory for the pointer (next) to the next node.
2. Pointer Operations: Managing pointers requires slightly more complex operations compared to array indexing.
Time Complexity:
• Push: O(1) (constant time) – Inserting a node at the beginning of the list.
• Pop: O(1) (constant time) – Removing a node from the beginning of the list.
• Peek: O(1) (constant time) – Accessing the top node.
• isEmpty: O(1) (constant time) – Checking if the top is None.