What Is the Stack in Data Structure?
In computer science, a stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. It can be visualized as a stack of plates, where you can only access the topmost plate.
The stack data structure is widely used in programming languages, compilers, operating systems, and various algorithms.
Stack Operations
The stack supports two primary operations:
- Push: This operation adds an element to the top of the stack.
- Pop: This operation removes and returns the element from the top of the stack.
Additionally, there are other useful operations associated with stacks:
- Peek: This operation returns the topmost element without removing it.
- IsEmpty: This operation checks if the stack is empty or not.
- Size: This operation returns the number of elements in the stack.
Implementation of a Stack
Stacks can be implemented using arrays or linked lists. Let’s take a look at both implementations:
Array-Based Stack Implementation:
<pre>
class Stack {
constructor() {
this.stack = [];
}
push(element) {
this.stack.push(element);
}
pop() {
if (!this.isEmpty()) {
return this.pop();
}
throw new Error('Stack is empty!');
}
peek() {
if (!this.stack[this.length - 1];
}
throw new Error('Stack is empty!');
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
}
const stack = new Stack();
</pre>Linked List-Based Stack Implementation:
<pre>
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
push(element) {
const newNode = new Node(element);
if (this.top === null) {
this.top = newNode;
} else {
newNode.next = this.top;
this.top = newNode;
}
this.size++;
}
pop() {
if (!this.isEmpty()) {
const removedNode = this.top;
if (this.size === 1) {
// Only one element in the stack
this.top = null;
} else {
// More than one element in the stack
this.top = removedNode.next;
}
removedNode.next = null; // Disconnect removed node from the stack
this.size--;
return removedNode.data;
}
throw new Error('Stack is empty!');
}
peek() {
if (!this.isEmpty()) {
return this.top.data;
}
throw new Error('Stack is empty!');
}
isEmpty() {
return this.size === 0;
}
size() {
return this.size;
}
}
Applications of Stacks
Stacks are used in various real-world scenarios, including:
- Function Call Stack: Stacks are used to keep track of function calls and their local variables. The order in which functions are called determines the order in which they will be executed.
- Undo/Redo Operations: Many applications provide undo and redo functionality, where stacks are used to store the state of actions performed by the user.
- Expression Evaluation: Stacks are utilized to evaluate arithmetic expressions, such as infix, postfix, and prefix notation.
- Backtracking Algorithms: Stacks play a crucial role in backtracking algorithms like depth-first search (DFS).
Understanding stacks is fundamental for every programmer. By mastering this data structure, you can solve complex problems efficiently and write more optimized code.
Now that you have a solid understanding of stacks, it's time to apply this knowledge to your own projects.