Jump To Question
What is a Stack in DSA?
A stack is a linear data structure in Data Structures and Algorithms (DSA) that follows the Last In, First Out (LIFO) principle. This means the element added last to the stack is the first one to be removed. It is analogous to a stack of plates where the plate placed last is on the top and is the first to be removed.
Why is There a Need for a Stack?
Stacks are essential in DSA for several applications, especially for managing function calls, expression evaluation, and syntax parsing. They are useful in situations where data needs to be stored and accessed in a particular order. Stacks help efficiently manage data that has to follow the LIFO principle, which is common in programming.
Advantages of Stack
- Efficient for Reversing: Stacks allow reversing data structures easily as they use the LIFO principle.
- Helps in Function Call Management: Stacks help manage nested and recursive function calls.
- Simple to Implement: Stacks have a straightforward implementation process with basic operations like push and pop.
Disadvantages of Stack
- Limited Access: Only the top element can be accessed directly, which limits flexibility.
- Overflow: Stacks have a limited size, so they can overflow if too many elements are added.
- Underflow: Attempting to remove an element from an empty stack leads to underflow.
1. Convert the infix expression (a-b/c)*(a/c-d) to prefix expression.
Answer:
To convert the infix expression to prefix, we first convert it to postfix and then reverse it. The given infix expression is:
(a-b/c)*(a/c-d).
- Step 1: Apply operator precedence and associativity rules.
- Step 2: The postfix expression is: abc/-ac/d-*.
- Step 3: Reverse the postfix to get the prefix expression: *-a/bc-/acd.
Thus, the prefix expression is *-a/bc-/acd .
2. Evaluate the postfix expression "5 6 2 + * 12 4 / -".
Answer:
To evaluate a postfix expression, we scan from left to right and apply operators to operands.
- Step 1: Push 5, 6, and 2 onto the stack.
- Step 2: Pop 6 and 2, add them (6+2=8), and push the result (8).
- Step 3: Pop 5 and 8, multiply them (5*8=40), and push the result (40).
- Step 4: Push 12 and 4, divide them (12/4=3), and push the result (3).
- Step 5: Pop 40 and 3, subtract them (40-3=37).
Final result is 37.
3. Convert the prefix expression +A*BCD to infix.
Answer:
To convert prefix to infix, we process from right to left.
- Step 1: Start with D (operand).
- Step 2: Move to the next operator, *, and form the expression (B*C).
- Step 3: Move to +, and add A, so the expression becomes (A+(B*C)).
Thus, the infix expression is (A+(B*C)).
4. What is the result of pushing the elements 3, 5, and 7 into a stack and then popping two elements?
Answer:
When elements 3, 5, and 7 are pushed into the stack, the stack looks
like this:
Top -> 7, 5, 3.
If we pop two elements, 7 and 5 will be removed, leaving 3 at the top.
So, the final state of the stack is:
Top -> 3.
5. Convert the infix expression A*(B+C)/D to postfix expression.
Answer:
The given infix expression is A*(B+C)/D.
- Step 1: Process the innermost expression (B+C), which gives BC+.
- Step 2: Apply *, so the expression becomes ABC+*.
- Step 3: Apply / with D, so the final expression is ABC+*D/.
Thus, the postfix expression is ABC+*D/.
6. Implement a stack using arrays in C.
Answer:
In C, a stack can be implemented using arrays as follows:
#define MAX 100
int stack[MAX], top = -1;
void push(int x) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = x;
}
}
int pop() {
if (top == -1) {
printf("Stack Underflow\n");
return -1;
} else {
return stack[top--];
}
}
This code defines a stack with push and pop operations using arrays.
7. What are the time complexities of push and pop operations in a stack?
Answer:
Both the push and pop operations in a stack take constant time because inserting or deleting an element from the top of the stack does not depend on the number of elements in the stack.
- Time complexity of push: O(1)
- Time complexity of pop: O(1)
8. Convert the postfix expression "AB+C*D-" to infix.
Answer:
To convert a postfix expression to infix, we process from left to right.
- Step 1: Take the operands A and B, and apply + to get (A+B).
- Step 2: Apply * with C, so the expression becomes ((A+B)*C).
- Step 3: Apply - with D, so the final expression is (((A+B)*C)-D).
Thus, the infix expression is (((A+B)*C)-D).
9. Explain how to check for balanced parentheses using a stack.
Answer:
To check for balanced parentheses, we use a stack:
- Step 1: Traverse the expression.
- Step 2: Push opening parentheses '(', '{', '[' onto the stack.
- Step 3: When a closing parenthesis ')', '}', ']' is encountered, check if it matches the top element of the stack. If yes, pop the top element.
- Step 4: If the stack is empty at the end, the parentheses are balanced.
10. Convert the prefix expression "*+AB-CD" to infix.
Answer:
To convert prefix to infix, we process from right to left.
- Step 1: Start with D (operand).
- Step 2: Apply -, so the expression becomes (C-D).
- Step 3: Apply + with A and B, so the expression becomes (A+B).
- Step 4: Apply * with both parts, so the final expression is ((A+B)*(C-D)).
Thus, the infix expression is ((A+B)*(C-D)).
11. How can a stack be used to reverse a string?
Answer:
To reverse a string using a stack:
- Step 1: Push each character of the string onto the stack.
- Step 2: Pop each character from the stack and append it to a new string.
Since the stack is LIFO (Last In First Out), the order of characters will be reversed.
12. Convert the infix expression "A/B+C*(D-E)" to postfix.
Answer:
The given infix expression is A/B+C*(D-E).
To convert to postfix:
- Step 1: Process the innermost expression (D-E), which gives DE-.
- Step 2: Apply * with C, so the expression becomes CDE-*.
- Step 3: Apply / with A and B, giving AB/.
- Step 4: Combine everything, so the final expression is AB/CDE-*+.
Thus, the postfix expression is AB/CDE-*+.
13. What is the main difference between stack and queue?
Answer:
The main difference between a stack and a queue lies in how elements are removed:
- Stack: Follows the LIFO (Last In First Out) principle, where the last element added is the first one removed.
- Queue: Follows the FIFO (First In First Out) principle, where the first element added is the first one removed.
14. Convert the postfix expression "ABC/-AK/L-*" to infix.
Answer:
To convert postfix to infix, process from left to right.
- Step 1: Apply / with B and C, so the expression becomes (B/C).
- Step 2: Apply - with A, giving (A-(B/C)).
- Step 3: Apply / with A and K, so the expression becomes (A/K).
- Step 4: Apply - with L, giving ((A/K)-L).
- Step 5: Apply * to both parts, resulting in ((A-(B/C))*((A/K)-L)).
Thus, the infix expression is ((A-(B/C))*((A/K)-L)).
15. Explain stack overflow and how it occurs.
Answer:
A stack overflow occurs when there is an attempt to push an element onto a stack that is already full. Since a stack has a finite size, trying to add more elements than it can hold causes an overflow, which can result in program crashes or unexpected behavior.
16. Convert the prefix expression "-*+ABC/DE" to infix.
Answer:
To convert prefix to infix, process from right to left.
- Step 1: Apply / to D and E, giving (D/E).
- Step 2: Apply + to A, B, and C, resulting in (A+B*C).
- Step 3: Apply * to both parts, giving ((A+B*C)*(D/E)).
- Step 4: Apply - to complete the expression, resulting in ((A+B*C)-(D/E)).
Thus, the infix expression is ((A+B*C)-(D/E)).
17. Write a program to check for balanced parentheses using a stack in C.
Answer:
The following C program checks for balanced parentheses using a stack:
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) {
stack[++top] = c;
}
char pop() {
return stack[top--];
}
int is_balanced(char* expr) {
for (int i = 0; i < strlen(expr); i++) {
if (expr[i] == '(') {
push('(');
} else if (expr[i] == ')') {
if (top == -1) return 0;
pop();
}
}
return (top == -1);
}
int main() {
char expr[] = "(A+B)*(C-D)";
if (is_balanced(expr)) {
printf("Balanced\n");
} else {
printf("Not Balanced\n");
}
return 0;
}
18. How can a stack be used in function recursion?
Answer:
In function recursion, each function call is pushed onto a call stack. When the function returns, its call is popped from the stack. This enables the program to track where it left off and resume from that point when the recursion unwinds.
19. Convert the postfix expression "AB+CD+*" to infix.
Answer:
To convert postfix to infix, process from left to right.
- Step 1: Apply + to A and B, resulting in (A+B).
- Step 2: Apply + to C and D, resulting in (C+D).
- Step 3: Apply * to both parts, resulting in (A+B)*(C+D).
Thus, the infix expression is (A+B)*(C+D).
20. Describe how to implement a queue using two stacks.
Answer:
To implement a queue using two stacks:
- Step 1: Push elements onto the first stack during enqueue.
- Step 2: For dequeue, pop all elements from the first stack and push them onto the second stack, then pop from the second stack.
- Step 3: This simulates the FIFO behavior of a queue using the LIFO behavior of stacks.