Understanding Stacks in Programming
A stack is a fundamental data structure in computer science that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of it like a stack of plates - you add plates to the top and remove them from the top.
Basic Operations
Stacks support two primary operations:
- Push: Add an element to the top of the stack.
- Pop: Remove the top element from the stack.
Additionally, stacks often include these helper operations:
- Peek or Top: View the top element without removing it.
- isEmpty: Check if the stack is empty.
- Size: Get the number of elements in the stack.
Implementation in Java
Here's a basic implementation of a stack in Java using an ArrayList:
import java.util.ArrayList;
public class Stack<T> {
private ArrayList<T> stack;
public Stack() {
stack = new ArrayList<>();
}
public void push(T item) {
stack.add(item);
}
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack.remove(stack.size() - 1);
}
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack.get(stack.size() - 1);
}
public boolean isEmpty() {
return stack.isEmpty();
}
public int size() {
return stack.size();
}
}
Implementation in C++
Here's a similar implementation in C++ using a vector:
#include <vector>
#include <stdexcept>
template <typename T>
class Stack {
private:
std::vector<T> stack;
public:
void push(T item) {
stack.push_back(item);
}
T pop() {
if (isEmpty()) {
throw std::runtime_error("Stack is empty");
}
T item = stack.back();
stack.pop_back();
return item;
}
T peek() {
if (isEmpty()) {
throw std::runtime_error("Stack is empty");
}
return stack.back();
}
bool isEmpty() {
return stack.empty();
}
int size() {
return stack.size();
}
};
Common Interview Problems
1. Valid Parentheses
Problem: Given a string containing just the characters '(', ')', ', ', '[' and ']', determine if the input string is valid. An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Java Solution:
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return stack.isEmpty();
}
}
C++ Solution:
#include <stack>
#include <string>
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
char top = st.top();
st.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return st.empty();
}
};
Explanation: In both implementations, we use a stack to keep track of opening brackets. When we encounter a closing bracket, we check if it matches the most recent opening bracket (which should be at the top of the stack). If it doesn't match or if the stack is empty when we encounter a closing bracket, the string is invalid.
2. Implement Queue using Stacks
Problem: Implement a first in first out (FIFO) queue using only two stacks.
Java Solution:
import java.util.Stack;
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
C++ Solution:
#include <stack>
class MyQueue {
private:
std::stack<int> stack1;
std::stack<int> stack2;
public:
MyQueue() {}
void push(int x) {
stack1.push(x);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
int front = stack2.top();
stack2.pop();
return front;
}
int peek() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
return stack2.top();
}
bool empty() {
return stack1.empty() && stack2.empty();
}
};
Explanation: We use two stacks to simulate a queue. The first stack is used for pushing elements. When we need to pop or peek, we transfer all elements from the first stack to the second stack, reversing their order. This way, the second stack will have elements in the correct order for a queue (first in, first out).
3. Evaluate Reverse Polish Notation
Problem: Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN). Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Java Solution:
import java.util.Stack;
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
int b = stack.pop();
int a = stack.pop();
switch (token) {
case "+":
stack.push(a + b);
break;
case "-":
stack.push(a - b);
break;
case "*":
stack.push(a * b);
break;
case "/":
stack.push(a / b);
break;
}
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
C++ Solution:
#include <vector>
#include <stack>
#include <string>
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (const string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (token == "+") st.push(a + b);
else if (token == "-") st.push(a - b);
else if (token == "*") st.push(a * b);
else if (token == "/") st.push(a / b);
} else {
st.push(stoi(token));
}
}
return st.top();
}
};
Explanation: In both implementations, we use a stack to keep track of operands. When we encounter an operator, we pop the two most recent operands, perform the operation, and push the result back onto the stack. At the end, the stack will contain the final result.
These problems demonstrate the versatility of stacks in solving various computational problems, especially those involving parsing and managing nested structures.