A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It is an ordered collection of elements where the addition and removal of items happen only at one end called the top.
The element that is added last is the first one to be removed. Think of it as a stack of books, where you can only take or add books from/to the top.
Stack Operations
A stack typically supports three main operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the top element from the stack.
- Peek/Top: Returns the top element without removing it.
An Example
To better understand stacks, let’s consider an example where we want to reverse a word using a stack. Let’s take the word “HTML” as an example:
<html>
<body>
<script>
function reverseWord(word) {
var stack = [];
var reversedWord = "";
var length = word.length;
// Push each character onto the stack
for (var i = 0; i < length; i++) {
stack.push(word[i]);
}
// Pop each character from the stack
for (var i = 0; i < length; i++) {
reversedWord += stack.pop();
}
return reversedWord;
}
var originalWord = "HTML";
var reversed = reverseWord(originalWord);
console.log(reversed); // Output: LMTH
</script>
</body>
</html>
In this example, we create an empty stack and iterate over each character of the word “HTML”. We push each character onto the stack.
Then, we pop each character from the stack and append it to a new string called “reversedWord”. Finally, we return the reversed word.
Stack Visualization
Here’s a step-by-step visualization of how the stack is used to reverse the word:
- Original Word: H, Stack: [], Reversed Word: “”
- Original Word: HT, Stack: [H], Reversed Word: “”
- Original Word: HTM, Stack: [H, T], Reversed Word: “”
- Original Word: HTML, Stack: [H, T, M], Reversed Word: “M”
- Popping from Stack – Character Removed from Stack and Appended to Reversed Word.
- Stack After Pop – Original Word: HML, Stack: [H,T], Reversed Word:M
- Popping from Stack – Character Removed from Stack and Appended to Reversed Word.
.. Repeat until all characters are popped. .
Finally, we get the reversed word as “LMTH”.
Conclusion
A stack is a fundamental data structure in computer science. It follows the Last-In-First-Out principle and is commonly used in various algorithms and programming languages. Understanding stacks and their operations can greatly enhance your ability to solve problems efficiently.