1. Which of the following real world scenarios would you associate with a stack data structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a counter
c) offer services based on the priority of the customer
d) tatkal Ticket Booking in IRCTC
Answer: a
Explanation: A stack follows the Last In First Out (LIFO) policy, meaning the last element added to the stack is the first one to be removed. This is similar to piling up chairs one on top of the other — the last chair placed on top is the first one to be taken off. On the other hand, a queue follows the First In First Out (FIFO) policy, such as people standing in a line, where the first person in line is the first to be served. A priority queue is used when services are provided based on priority, rather than order of arrival. For example, the Tatkal ticket booking system follows FIFO, where the person who clicks “book now” first will be served first.
2. What does the following function check for? (all necessary headers to be included and function is called from main)
#define MAX 10
typedef struct stack
{
int top;
int item[MAX];
}stack;
int function(stack *s)
{
if(s->top == -1)
return 1;
else return 0;
}
a) full stack
b) invalid index
c) empty stack
d) infinite stack
Answer: c
Explanation: In a stack data structure, an empty stack is typically represented by setting the top pointer (or index) to -1. This indicates that there are no elements in the stack. When the first element is pushed onto the stack, the top pointer is set to 0, and it increments as new elements are added. If top is -1, it means the stack is empty and no elements are present.
3. What does ‘stack underflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
Answer: c
Explanation: Stack underflow occurs when an attempt is made to remove an item from an empty stack. Since there are no elements in the stack to pop, this operation is invalid and results in an underflow condition. In contrast, stack overflow happens when the stack exceeds its maximum capacity, usually when trying to push an item onto a full stack. Stack underflow is a condition that indicates that the stack is empty and cannot perform a pop operation.
4. What is the output of the following program?
public class Stack
{
protected static final int CAPACITY = 100;
protected int size,top = -1;
protected Object stk[];
public Stack()
{
stk = new Object[CAPACITY];
}
public void push(Object item)
{
if(size_of_stack==size)
{
System.out.println("Stack overflow");
return;
}
else
{
top++;
stk[top]=item;
}
}
public Object pop()
{
if(top<0)
{
return -999;
}
else
{
Object ele=stk[top];
top--;
size_of_stack--;
return ele;
}
}
}
public class StackDemo
{
public static void main(String args[])
{
Stack myStack = new Stack();
myStack.push(10);
Object element1 = myStack.pop();
Object element2 = myStack.pop();
System.out.println(element2);
}
}
a) stack is full
b) 20
c) 0
d) -999
Answer: d
Explanation: When performing a pop() operation on a stack, the first call to pop() will successfully remove and return the top item from the stack, which in this case is 10. However, if the stack is empty after the first pop(), the second call to pop() will result in a stack underflow. This condition occurs because there are no items left in the stack to remove, so the program returns an error value such as -999 to indicate the underflow situation.
5. What is the time complexity of pop() operation when the stack is implemented using an array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer: a
Explanation: The pop() operation in a stack is performed on only one end, the top of the stack. Since it only involves accessing and removing the top element without needing to traverse the entire structure, it operates in constant time O(1)O(1). Regardless of the size of the stack, the time required to perform a pop() operation remains the same. This efficiency is one of the key characteristics of stack data structures.
6. Which of the following array position will be occupied by a new element being pushed for a stack of size N elements(capacity of stack > N)?
a) S[N-1]
b) S[N]
c) S[1]
d) S[0]
Answer: b
Explanation: In a stack, elements are added (pushed) to the top, and the time complexity of the push() operation is O(1) because it involves placing the element at the top without needing to move any other elements. However, if we are discussing an operation that involves traversing or manipulating all elements in the stack (such as checking each element or rearranging), the time complexity could be O(n) where n is the number of elements in the stack. This happens if you perform operations that require iterating through the entire stack. In this case, if you’re referring to a specific operation that accesses or manipulates all elements at once, the time complexity would be O(n).
7. What happens when you pop from an empty stack while implementing using the Stack ADT in Java?
a) Undefined error
b) Compiler displays a warning
c) EmptyStackException is thrown
d) NoStackException is thrown
Answer: c
Explanation: In the Stack Abstract Data Type (ADT), if a pop() operation is attempted on an empty stack, it typically throws an EmptyStackException. This exception indicates that there are no elements in the stack to remove, as the stack is empty. The purpose of this exception is to prevent operations on an invalid stack state and to provide an error signal to the program, helping to handle such scenarios properly.
8. What is the functionality of the following piece of Java code?
Assume: ‘a’ is a non empty array of integers, the Stack class creates an array of specified size and provides a top pointer indicating TOS(top of stack), push and pop have normal meaning.
public void some_function(int[] a)
{
Stack S=new Stack(a.length);
int[] b=new int[a.length];
for(int i=0;i<a.length;i++)
{
S.push(a[i]);
}
for(int i=0;i<a.length;i++)
{
b[i]=(int)(S.pop());
}
System.out.println("output :");
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}
a) print alternate elements of array
b) duplicate the given array
c) parentheses matching
d) reverse the array
Answer: d
Explanation: In this scenario, every element from the given array a is pushed onto the stack. Since a stack operates on a Last In, First Out (LIFO) principle, the elements are stored in the reverse order of their original positions in the array. When the elements are then popped from the stack, they are retrieved in the reverse order, and pushed into the array b. As a result, the array b will contain the elements of array a in reverse order. This is a classic use case of a stack to reverse the elements of an array.
9. Array implementation of Stack is not dynamic, which of the following statements supports this argument?
a) space allocation for array is fixed and cannot be changed during run-time
b) user unable to give the input for stack operations
c) a runtime exception halts execution
d) improper program compilation
Answer: a
Explanation: In a static array, the size is fixed at the time of memory allocation and cannot be changed during runtime. This leads to potential issues. If fewer elements are added than the allocated size, memory space is wasted. Conversely, if more elements need to be added than the predefined size, it will cause a stack overflow or out of bounds error, as the array has no room to accommodate extra elements. This makes the static array inefficient for dynamic data storage, as the size cannot be adjusted after initialization.
10. Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack > N)?
a) S[N-1]
b) S[N]
c) S[N-2]
d) S[N+1]
Answer: a
Explanation: In an array, indexing starts from 0. Therefore, for an array of size N, the first element is at index 0 and the last element is at index N-1. This is because the index of the last element is always one less than the size of the array. So, if the array has N elements, the index of the last element is N-1.