Real interview questions from top companies for Stack. Includes theoretical concepts and coding problems.
What is a stack and how does it work?
A stack is a linear data structure that follows the LIFO (Last In First Out) principle, where the last element added to the stack will be the first one to be removed. A stack can be implemented using an array or a linked list, and it supports two primary operations: push and pop.
What are the basic operations that can be performed on a stack?
The basic operations that can be performed on a stack are push, pop, peek, isEmpty, and size. The push operation adds an element to the top of the stack, the pop operation removes the top element from the stack, the peek operation returns the top element without removing it, the isEmpty operation checks if the stack is empty, and the size operation returns the number of elements in the stack.
What is the difference between a stack and a queue?
A stack follows the LIFO principle, where the last element added will be the first one to be removed, whereas a queue follows the FIFO principle, where the first element added will be the first one to be removed.
How is a stack implemented in programming languages?
A stack can be implemented in programming languages using an array or a linked list. The array implementation is simpler and more efficient, but it has a fixed size limit. The linked list implementation is more flexible and can grow dynamically, but it requires more memory and is slower.
What are the advantages and disadvantages of using a stack?
The advantages of using a stack are that it is simple to implement, efficient in terms of memory usage, and fast in terms of operation time. The disadvantages are that it has a limited size, and the elements are accessed in a LIFO order, which may not be suitable for all applications.
What is the time complexity of the push and pop operations on a stack?
The time complexity of the push and pop operations on a stack is O(1), which means that the time taken to perform these operations is constant and does not depend on the size of the stack.
How is a stack used in recursive algorithms?
A stack is used in recursive algorithms to store the function calls and their parameters. When a function calls another function, the current function's state is pushed onto the stack, and when the called function returns, its state is popped from the stack.
What is the relationship between a stack and a recursive function?
A stack is used to implement recursive functions, where each recursive call is pushed onto the stack, and when the function returns, the top element is popped from the stack. This process continues until the base case is reached, at which point the recursion stops.
How does a stack handle overflow and underflow conditions?
A stack handles overflow and underflow conditions by checking if the stack is full before pushing an element and if the stack is empty before popping an element. If the stack is full, an overflow error occurs, and if the stack is empty, an underflow error occurs.
What are the common applications of a stack in computer science?
The common applications of a stack in computer science are evaluating postfix expressions, parsing syntax, implementing recursive algorithms, managing function calls, and implementing undo and redo functionality.
How does a stack differ from a heap?
A stack is a linear data structure that follows the LIFO principle, whereas a heap is a specialized tree-based data structure that satisfies the heap property. A heap is used for priority queuing, whereas a stack is used for LIFO queuing.
What is the relationship between a stack and a tree?
A stack can be used to traverse a tree, where each node is pushed onto the stack, and when a node is visited, it is popped from the stack. This process continues until all nodes are visited.
How does a stack handle concurrency and synchronization?
A stack can handle concurrency and synchronization by using locks or semaphores to protect access to the stack. This ensures that only one thread can access the stack at a time, preventing data corruption and ensuring thread safety.
What are the trade-offs between using a stack and a queue?
The trade-offs between using a stack and a queue are that a stack is simpler and more efficient, but it has a limited size and follows the LIFO principle, whereas a queue is more flexible and can grow dynamically, but it is slower and follows the FIFO principle.
How does a stack differ from a graph?
A stack is a linear data structure that follows the LIFO principle, whereas a graph is a non-linear data structure that consists of nodes and edges. A graph can be used to represent complex relationships between objects, whereas a stack is used for LIFO queuing.
What are the common pitfalls when implementing a stack?
The common pitfalls when implementing a stack are not checking for overflow and underflow conditions, not handling concurrency and synchronization, and not using a suitable data structure to implement the stack.
How does a stack relate to the concept of abstraction?
A stack is an abstract data type that provides a simple and efficient way to implement LIFO queuing. It abstracts away the underlying implementation details, providing a clean and intuitive interface for users.
What are the benefits of using a stack in programming?
The benefits of using a stack in programming are that it is simple to implement, efficient in terms of memory usage, and fast in terms of operation time. It also provides a clean and intuitive way to implement LIFO queuing, making it a fundamental data structure in computer science.
How does a stack differ from a set?
A stack is a linear data structure that follows the LIFO principle, whereas a set is an unordered collection of unique elements. A set does not follow any particular order, whereas a stack follows the LIFO principle.
What are the common use cases for a stack in software development?
The common use cases for a stack in software development are evaluating postfix expressions, parsing syntax, implementing recursive algorithms, managing function calls, and implementing undo and redo functionality.
How does a stack relate to the concept of encapsulation?
A stack is an example of encapsulation, where the underlying implementation details are hidden from the user, and only the necessary information is exposed through a clean and intuitive interface.
What are the trade-offs between using a stack and a list?
The trade-offs between using a stack and a list are that a stack is simpler and more efficient, but it has a limited size and follows the LIFO principle, whereas a list is more flexible and can grow dynamically, but it is slower and follows the FIFO principle.
How does a stack differ from a map?
A stack is a linear data structure that follows the LIFO principle, whereas a map is an unordered collection of key-value pairs. A map does not follow any particular order, whereas a stack follows the LIFO principle.
Implement a stack using an array in JavaScript
functionStack() {
this.items = [];
}
Stack.prototype.push = function (item) {
this.items.push(item);
};
Stack.prototype.pop = function () {
returnthis.items.pop();
};
Stack.prototype.peek = function () {
returnthis.items[this.items.length - 1];
};
Implement a stack using a linked list in JavaScript
functionNode(data) {
this.data = data;
this.next = null;
}
functionStack() {
this.top = null;
}
Stack.prototype.push = function (data) {
var node = newNode(data);
node.next = this.top;
this.top = node;
};
Stack.prototype.pop = function () {
if (this.top === null) {
returnnull;
}
var data = this.top.data;
this.top = this.top.next;
return data;
};
Write a function to evaluate the validity of a string of parentheses using a stack in JavaScript
functionisValid(s) {
var stack = [];
for (var i = 0; i < s.length; i++) {
if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
stack.push(s[i]);
} else {
if (stack.length === 0) {
returnfalse;
}
var top = stack.pop();
if (s[i] === ')' && top !== '(') {
returnfalse;
}
if (s[i] === '}' && top !== '{') {
returnfalse;
}
if (s[i] === ']' && top !== '[') {
returnfalse;
}
}
}
return stack.length === 0;
}
Write a function to find the maximum element in a stack in JavaScript
functionmaxElement(stack) {
var max = -Infinity;
for (var i = 0; i < stack.length; i++) {
if (stack[i] > max) {
max = stack[i];
}
}
return max;
}
Write a function to sort a stack using another stack in JavaScript
functionsortStack(stack) {
var tempStack = [];
while (stack.length > 0) {
var temp = stack.pop();
while (tempStack.length > 0 && tempStack[tempStack.length - 1] > temp) {
stack.push(tempStack.pop());
}
tempStack.push(temp);
}
return tempStack;
}
Write a function to find the minimum element in a stack in JavaScript
functionminElement(stack) {
var min = Infinity;
for (var i = 0; i < stack.length; i++) {
if (stack[i] < min) {
min = stack[i];
}
}
return min;
}
Write a function to reverse a stack using another stack in JavaScript
functionreverseStack(stack) {
var tempStack = [];
while (stack.length > 0) {
tempStack.push(stack.pop());
}
return tempStack;
}
Write a function to check if two stacks are equal in JavaScript
functionareStacksEqual(stack1, stack2) {
if (stack1.length !== stack2.length) {
returnfalse;
}
while (stack1.length > 0) {
if (stack1.pop() !== stack2.pop()) {
returnfalse;
}
}
returntrue;
}
Write a function to merge two stacks into one stack in JavaScript
functionmergeStacks(stack1, stack2) {
var mergedStack = [];
while (stack1.length > 0) {
mergedStack.push(stack1.pop());
}
while (stack2.length > 0) {
mergedStack.push(stack2.pop());
}
return mergedStack;
}
SHARE ARTICLE
Choose Interviewer type
Please review your order carefully before confirming. Once your purchase is processed, refunds will not be available.
