Stack Data Structure
A Stack is a linear data structure that follows the Last In First Out (LIFO) principle. It means that the last item added to the stack will be the first item to be removed. A stack is like a pile of books. When you add a new book to the pile, it becomes the top of the stack. When you remove a book from the pile, you remove the top one first.
A stack is a collection of elements that supports two operations: push and pop. The push operation adds an element to the top of the stack, and the pop operation removes the top element from the stack. In this tutorial, we'll explore the stack data structure, covering its definition, operations, implementation, and best practices.
Representation of Stack
A stack can be represented using an array or a linked list.
Array Representation of Stack
In the array representation of a stack, we use an array to store the elements of the stack. We also need a variable to keep track of the top of the stack. The top of the stack is the index of the last element added to the stack.
Linked List Representation of Stack
In the linked list representation of a stack, we use a linked list to store the elements of the stack. Each node in the linked list represents an element of the stack, and the top of the stack is the head of the linked list.
Uses of Stack Data Structure
- Function call stack: When a function is called, its return address and parameters are pushed onto the stack. When the function returns, these values are popped off the stack.
- Expression evaluation: In computer science, expressions are usually evaluated using a stack. For example, to evaluate the expression 2 * (3 + 4), we push 2 onto the stack, then push 3 and 4 onto the stack, then pop 3 and 4 off the stack and add them together, then multiply the result by 2.
- Backtracking: Stacks can be used to implement backtracking algorithms. In a backtracking algorithm, we keep track of the choices we have made so far on the stack. If we reach a dead end, we pop the choices off the stack until we find a choice that leads to a solution.
- Undo/Redo operations: Stacks can be used to implement undo and redo operations in software applications. Each operation is pushed onto the stack, and undoing an operation involves popping it off the stack.
- Parsing and Syntax Checking: Stacks assist in parsing and checking the syntax of expressions or languages, ensuring proper opening and closing of brackets, parentheses, etc.
Advantages and Disadvantages of Stack
Advantages of Stack Data Structure
- They are easy to implement and use.
- They have a simple and intuitive interface.
- They are efficient for adding and removing elements from the top of the stack.
Disadvantages of Stack Data Structure
- They have limited functionality, as they only support push and pop operations.
- They can only be used to access elements in LIFO order.
Common Stack Operations
- Push: Push operation inserts an element onto the top of the stack. It takes a single parameter, the value to be pushed onto the stack, and increases the stack pointer to accommodate the new element.
- Pop: Pop operation removes the top element from the stack. It returns the value of the element that was popped and decreases the stack pointer.
- Peek: Peek operation returns the value of the top element from the stack without removing it.
- isEmpty: isEmpty operation returns a Boolean value indicating whether the stack is empty or not.
- isFull: isFull operation returns a Boolean value indicating whether the stack is full or not.
- Size: Size operation returns the number of elements currently in the stack.
Stack Data Structure Implementation Program
Here's a simple implementation of the stack data structure in C.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
int stack[MAX_SIZE];
int top = -1;
void push(int value) {
if (top == MAX_SIZE - 1) {
printf("Stack overflow\n");
return;
}
stack[++top] = value;
}
int pop() {
if (top == -1) {
printf("Stack underflow\n");
return -1;
}
return stack[top--];
}
int peek() {
if (top == -1) {
printf("Stack is empty\n");
return -1;
}
return stack[top];
}
int isEmpty() {
return top == -1;
}
int isFull() {
return top == MAX_SIZE - 1;
}
int size() {
return top + 1;
}
int main() {
push(1);
push(2);
push(3);
printf("Stack size is %d\n", size());
printf("Top element is %d\n", peek());
printf("Popped element is %d\n", pop());
printf("Top element is %d\n", peek());
printf("Stack is%s empty\n", isEmpty() ? "" : " not");
printf("Stack is%s full\n", isFull() ? "" : " not");
return 0;
}
Output
Stack size is 3 Top element is 3 Popped element is 3 Top element is 2 Stack is not empty Stack is not full
In this program, we define an array stack and an integer variable top to keep track of the top element of the stack. The push function adds an element to the top of the stack, while pop removes the top element from the stack. The peek function returns the value of the top element without removing it. The isEmpty function checks if the stack is empty and returns a Boolean value, and the isFull function checks if the stack is full and returns a Boolean value. Finally, the size function returns the number of elements currently in the stack.
We then demonstrate the use of these operations in the main function by pushing three elements onto the stack, printing the stack size, the value of the top element, and then popping an element from the stack. We print the value of the top element again and check if the stack is empty or not.
Best Practices of Using Stack Data Structures
- Choose the Right Implementation : Consider the application's requirements when choosing between array-based and linked list-based implementations. Arrays offer constant-time access but may require resizing, while linked lists provide dynamic resizing but involve more overhead.
- Check for Underflow and Overflow : Always check for underflow (popping from an empty stack) and overflow (pushing to a full stack) conditions to prevent runtime errors.
- Use Exception Handling : Implement exception handling to gracefully manage errors such as stack underflow or overflow, providing informative error messages.
- Clear Unused References : If using a linked list-based implementation, ensure that unused references are properly cleared to avoid memory leaks.
- Document Assumptions and Constraints : Clearly document any assumptions or constraints related to stack usage, such as expected data types or potential modifications.
Conclusion
The stack data structure, with its simple yet powerful principles of Last In, First Out (LIFO), plays a crucial role in algorithm design and various applications. By understanding its definition, basic operations, implementation techniques, and best practices, developers can harness the full potential of stacks in their programming endeavors. Whether managing function calls, parsing expressions, or implementing undo functionality, the stack proves to be a versatile and indispensable tool in the world of computer science and software development.