Q: What is a stack?
A: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where elements are inserted and removed from the same end called the top.
Q: What are the basic operations of a stack?
A: Basic stack operations include:
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the top element of the stack.
- Peek (or Top): Returns the top element of the stack without removing it.
- isEmpty: Checks if the stack is empty.
- Size: Returns the number of elements in the stack.
Q: How are stack operations implemented?
A: Stack operations can be implemented using arrays or linked lists. Arrays offer constant-time access but may require resizing if the stack grows beyond its initial capacity. Linked lists provide dynamic memory allocation but may have slightly higher overhead due to pointer manipulation.
Q: Can you provide an example of stack implementation using arrays in Python?
A: Here is the code.
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
return None
def peek(self):
return self.stack[-1] if not self.is_empty() else None
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
print("Stack peek:", stack.peek())
print("Stack size:", stack.size())
print("Popped item:", stack.pop())
Q: What are some applications of stacks?
A: Stacks are used in various applications, including:
- Expression evaluation (e.g., infix to postfix conversion)
- Function call management (e.g., maintaining function call stack in recursion)
- Undo mechanisms in text editors
- Backtracking algorithms
- Parsing and syntax analysis in compilers
Q: How can I implement stack operations using a linked list in C++?
A: Here is the code.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Stack {
private:
Node* top;
public:
Stack() : top(nullptr) {}
void push(int item) {
Node* newNode = new Node();
newNode->data = item;
newNode->next = top;
top = newNode;
}
int pop() {
if (isEmpty()) {
cout << "Stack underflow\n";
return -1; // or throw an exception
}
int item = top->data;
Node* temp = top;
top = top->next;
delete temp;
return item;
}
int peek() {
if (isEmpty()) {
cout << "Stack is empty\n";
return -1; // or throw an exception
}
return top->data;
}
bool isEmpty() {
return top == nullptr;
}
};
// Example usage
int main() {
Stack stack;
stack.push(1);
stack.push(2);
cout << "Stack peek: " << stack.peek() << endl;
cout << "Popped item: " << stack.pop() << endl;
return 0;
}
Q: Are there any stack libraries available in programming languages?
A: Yes, many programming languages provide built-in stack data structures or libraries for stack operations. For instance, in Java, you can use the java.util.Stack class, and in C++, the Standard Template Library (STL) provides std::stack.
Important Interview Questions and Answers on Different Types of Stack Operations
Q: What is a stack?
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. It means that the element inserted last is the first one to be removed.
Q: How can you implement a stack?
A stack can be implemented using arrays or linked lists.
Q: Explain push and pop operations in a stack.
- push(item): This operation adds an item to the top of the stack.
- pop(): This operation removes and returns the item at the top of the stack.
Q: Write code for a stack using an array (in Python).
Here is the code.
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
return None
def is_empty(self):
return len(self.stack) == 0
def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
return None
def size(self):
return len(self.stack)
Q: Explain peek operation in a stack.
The peek operation returns the top element of the stack without removing it.
Q: Write code to reverse a string using a stack.
Here is the code.
def reverse_string(string):
stack = Stack()
for char in string:
stack.push(char)
reversed_string = ""
while not stack.is_empty():
reversed_string += stack.pop()
return reversed_string
# Example usage:
string = "hello"
print(reverse_string(string)) # Output: "olleh"
Q: Explain the application of stacks.
Stacks are used in applications such as expression evaluation, function call management (call stack), undo mechanisms in text editors, backtracking algorithms, and parsing algorithms.
Q: Write code to check if parentheses in a string are balanced using a stack.
Here is the code.
def is_balanced(expression):
stack = Stack()
opening_brackets = "([{"
closing_brackets = ")]}"
for char in expression:
if char in opening_brackets:
stack.push(char)
elif char in closing_brackets:
if stack.is_empty():
return False
top = stack.pop()
if opening_brackets.index(top) != closing_brackets.index(char):
return False
return stack.is_empty()
# Example usage:
expression = "{[()]}"
print(is_balanced(expression)) # Output: True
