Define stack and various operations on stack?
Stack: Definition
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. Imagine a stack of plates: the plate placed last on the top is the first one to be removed.
Basic Properties of a Stack
LIFO Principle: Last element inserted is the first one to be removed.
Single Pointer Access: Operations are performed only at one end, called the top of the stack.
Common Operations on a Stack
Push
Adds an element to the top of the stack.
Algorithm:
Check if the stack is full (overflow condition).
Increment the top pointer.
Insert the new element at the position indicated by the top pointer.
Pop
Removes the topmost element from the stack.
Algorithm:
Check if the stack is empty (underflow condition).
Retrieve the element at the top position.
Decrement the top pointer.
Peek (or Top)
Retrieves the element at the top of the stack without removing it.
Algorithm:
Check if the stack is empty.
Return the element at the top pointer.
isEmpty
Checks if the stack contains any elements.
Algorithm:
If the top pointer is -1, return true (empty); otherwise, return false.
isFull
Checks if the stack is at its maximum capacity.
Algorithm:
If the top pointer equals maxSize – 1, return true (full); otherwise, return false.
Illustration of Stack Operations
Initial State:
Stack is empty (top = -1).
Stack
Index 0 1 2 3
After Push(10), Push(20), Push(30):
Adding elements to the stack.
Stack 30 20 10
Index 2 1 0
After Pop():
Removing the top element (30).
Stack 20 10
Index 1 0
Stack Implementation
Using Arrays
Static implementation with fixed size.
Using Linked Lists
Dynamic implementation with flexible size.
Applications of Stacks
Expression Evaluation: Infix to postfix conversion, expression parsing.
Undo Operations: In text editors.
Backtracking: Solving mazes, puzzles.
Function Call Management: In recursion.
Web Navigation: Back and forward navigation in browsers.
Stacks are integral to many computer science applications and algorithms, emphasizing their versatility and importance in programming.