DSA

(DATA STRUCTURE)
STACK OPERATIONS
BEGINNERS

[Link]
sses?si=XkKXyJ_2a16NiK-K
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

sequence that contains 2 left parentheses and 3

STACK OPERATIONS right parentheses (in some order). The maximum
1. Process of inserting an element in stack is called number of parentheses that appear on the stack
____________ AT ANY ONE TIME during the computation?
a) Create b) Push a) 1 b) 2
c) Evaluation d) Pop c) 3 d) 4 or more
2. Process of removing an element from stack is 9. What is the value of the postfix expression 6 3 2 4
called __________ + – *?
a) Create b) Push a) 1 b) 40
c) Evaluation d) Pop c) 74 d) -18
3. In a stack, if a user tries to remove an element 10. Here is an infix expression: 4 + 3*(6*3-12). Suppose
from an empty stack it is called _________ that we are using the usual stack algorithm to
a) Underflow b) Empty collection convert the expression from infix to postfix
c) Overflow d) Garbage Collection notation. The maximum number of symbols that
will appear on the stack AT ONE TIME during the
4. Pushing an element into stack already having five
conversion of this expression?
elements and stack size of 5, then stack becomes
a) 1 b) 2
___________
c) 3 d) 4
a) Overflow b) Crash
11. The postfix form of the expression (A+ B)*(C*D-
c) Underflow d) User flow
E)*F / G is?
5. Entries in a stack are “ordered”. What is the a) AB+ CD*E – FG /**
meaning of this statement? b) AB + CD* E – F **G /
a) A collection of stacks is sortable c) AB + CD* E – *F *G /
b) Stack entries may be compared with the ‘<‘ d) AB + CDE * – * F *G /
operation 12. The data structure required to check whether an
c) The entries are stored in a linked list expression contains a balanced parenthesis is?
d) There is a Sequential entry that is one by one a) Stack b) Queue
6. Which of the following is not the application of c) Array d) Tree
stack? 13. What data structure would you most likely see in
a) A parentheses balancing program non recursive implementation of a recursive
b) Tracking of local variables at run time algorithm?
a) Linked List b) Stack
c) Compiler Syntax Analyzer
c) Queue d) Tree
d) Data Transfer between two asynchronous
14. The process of accessing data stored in a serial
process
access memory is similar to manipulating data on
7. Consider the usual algorithm for determining
a ________
whether a sequence of parentheses is balanced. a) Heap b) Binary Tree
The maximum number of parentheses that appear c) Array d) Stack
on the stack AT ANY ONE TIME when the 15. The postfix form of A*B+C/D is?
algorithm analyzes: (()(())(()))? a) *AB/CD+ b) AB*CD/+
a) 1 b) 2 c) A*BC+/D d) ABCD+/*
c) 3 d) 4 or more 16. Which data structure is needed to convert infix
8. Consider the usual algorithm for determining notation to postfix notation?
whether a sequence of parentheses is balanced. a) Branch b) Tree
Suppose that you run the algorithm on a c) Queue d) Stack

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

17. The prefix form of A-B/ (C * D ^ E) is? 25. Consider the following operation performed on a
a) -/*^ACBDE b) -ABCD*^DE stack of size 5.
c) -A/B*C^DE d) -A/BC*^DE Push(1);
18. What is the result of the following operation? Pop();
Top (Push (S, X)) Push(2);
a) X b) X+S Push(3);
c) S d) XS Pop();
19. The prefix form of an infix expression (p + q) – (r * Push(4);
t) is? Pop();
a) + pq – *rt b) – +pqr * t Pop();
c) – +pq * rt d) – + * pqrt Push(5);
20. Which data structure is used for implementing After the completion of all operation, the number
recursion? of elements present in stack is?
a) Queue b) Stack (a) 1 (b) 2
c) Array d) List (c) 3 (d) 4
21. The result of evaluating the postfix expression 5, 4, 26. Which of the following is not an inherent
6, +, *, 4, 9, 3, /, +, * is? application of stack?
(a) 600 (b) 350 (a) Reversing a string
(c) 650 (d) 588 (b) Evaluation of postfix expression
22. Convert the following infix expressions into its (c) Implementation of recursion
equivalent postfix expressions. (d) Job scheduling
(A + B ⋀D)/(E – F)+G 27. The type of expression in which operator succeeds
(a) (A B D ⋀ + E F – / G +) its operands is?
(b) (A B D +⋀ E F – / G +) (a) Infix Expression
(c) (A B D ⋀ + E F/- G +) (b) Prefix Expression
(d) (A B D E F + ⋀ / – G +) (c) Postfix Expression
23. Convert the following Infix expression to Postfix (d) Both Prefix and Postfix Expressions
form using a stack. 28. Assume that the operators +,-, x are left associative
x + y * z + (p * q + r) * s, Follow usual precedence and ^ is right associative. The order of precedence
rule and assume that the expression is legal. (from highest to lowest) is ^, x, +, -. The postfix
(a) xyz*+pq*r+s*+ expression for the infix expression a + b x c – d ^ e
(b) xyz*+pq*r+s+* ^ f is?
(c) xyz+*pq*r+s*+ (a) a b c x + d e f ^ ^ –
(d) xyzp+**qr+s*+ (b) a b c x + d e ^ f ^ –
24. Which of the following statement(s) about stack (c) a b + c x d – e ^ f ^
data structure is/are NOT correct? (d) – + a x b c ^ ^ d e f
(a) Linked List are used for implementing Stacks 29. If the elements “A”, “B”, “C” and “D” are placed in a
(b) Top of the Stack always contain the new node stack and are deleted one at a time, what is the
(c) Stack is the FIFO data structure order of removal?
(d) Null link is present in the last node at the (a) ABCD (b) DCBA
bottom of the stack (c) DCAB (d) ABDC

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

class Stack
STACK USING LINKED LIST {
1. What is the best case time complexity of deleting a Node first;
node in a Singly Linked list? int size=0;
a) O (n) b) O (n2) Stack()
c) O (nlogn) d) O (1) {
2. Which of the following statements are not correct with first=null;
respect to Singly Linked List(SLL) and Doubly Linked }
List(DLL)? }
a) Complexity of Insertion and Deletion at known a)
position is O(n) in SLL and O(1) in DLL
public Object pop()
b) SLL uses lesser memory per node than DLL
{
c) DLL has more searching power than SLL
if(size == 0)
d) Number of node fields in SLL is more than DLL
[Link]("underflow");
3. Given below is the Node class to perform basic list
operations and a Stack class with a no arg constructor. else
Select from the options the appropriate pop() {
operation that can be included in the Stack class. Also Object o = [Link]();
‘first’ is the top-of-the-stack. first = [Link]();
class Node size--;
{ return o;
protected Node next; }
protected Object ele; }
Node() b)
{ public Object pop()
this(null,null); {
}
if(size == 0)
Node(Object e,Node n)
[Link]("underflow");
{
else
ele=e;
next=n; {
} Object o = [Link]();
public void setNext(Node n) first = [Link]().getNext();
{ size--;
next=n; return o;
} }
public void setEle(Object e) }
{ c)
ele=e; public Object pop()
} {
public Node getNext() if(size == 0)
{ [Link]("underflow");
return next;
else
}
{
public Object getEle()
first = [Link]();
{
return ele; Object o = [Link]();
} size--;
} return o;
}
}

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

d) 6. What does ‘stack overflow’ refer to?

public Object pop() a) accessing item from an undefined stack
{ b) adding items to a full stack
if(size == 0) c) removing items from an empty stack
[Link]("underflow"); d) index out of bounds exception
else 7. Given below is the Node class to perform basic list
operations and a Stack class with a no arg constructor.
{
Select from the options the appropriate push()
first = [Link]().getNext();
operation that can be included in the Stack class. Also
Object o = [Link]();
‘first’ is the top-of-the-stack.
size--;
class Node
return o; {
} protected Node next;
} protected Object ele;
4. What does the following function do? Node()
public Object some_func()throws {
emptyStackException this(null,null);
{ }
if(isEmpty()) Node(Object e,Node n)
throw new {
emptyStackException("underflow"); ele=e;
return [Link](); next=n;
} }
public void setNext(Node n)
a) pop
{
b) delete the top-of-the-stack element
next=n;
c) retrieve the top-of-the-stack element
}
d) push operation public void setEle(Object e)
5. What is the functionality of the following piece of {
code? ele=e;
public void display() }
{ public Node getNext()
if(size == 0) {
[Link]("underflow"); return next;
else }
{ public Object getEle()
Node current = first; {
while(current != null) return ele;
{ }
}
[Link]([Link]());
current = [Link]();
class Stack
}
{
} Node first;
} int size=0;
a) reverse the list Stack()
b) display the list {
c) display the list excluding top-of-the-stack-element first=null;
d) reverse the list excluding top-of-the-stack- }
element }

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

a) 10. Minimum number of queues to implement stack is

public void push(Object item) ___________
{ a) 3 b) 4
Node temp = new Node(item,first); c) 1 d) 2
first = temp;
size++; STACK USING ARRAY
}
1. Which of the following real world scenarios would you
b)
associate with a stack data structure?
public void push(Object item)
{ a) piling up of chairs one above the other
Node temp = new Node(item,first); b) people standing in a line to be serviced at a
first = [Link](); counter
size++; c) offer services based on the priority of the
} customer
c) d) tatkal Ticket Booking in IRCTC
public void push(Object item) 2. What does the following function check for? (all
{ necessary headers to be included and function is
Node temp = new Node(); called from main)
first = [Link](); #define MAX 10
[Link](item);
size++;
typedef struct stack
}
{
d)
public void push(Object item) int top;
{ int item[MAX];
Node temp = new Node(); }stack;
first = [Link]();
[Link](item); int function(stack *s)
size++; {
} if(s->top == -1)
8. Consider these functions: return 1;
push() : push an element into the stack else return 0;
pop() : pop the top-of-the-stack element }
top() : returns the item stored in top-of-the-stack- a) full stack
node
b) invalid index
What will be the output after performing these
c) empty stack
sequence of operations
d) infinite stack
push(20);
push(4); 3. What does ‘stack underflow’ refer to?
top(); a) accessing item from an undefined stack
pop(); b) adding items to a full stack
pop(); c) removing items from an empty stack
push(5); d) index out of bounds exception
top(); 4. What is the output of the following program?
a) 20 b) 4 public class Stack
c) stack underflow d) 5 {
9. Which of the following data structures can be used for protected static final int CAPACITY = 100;
parentheses matching? protected int size,top = -1;
a) n-ary tree b) queue
protected Object stk[];
c) priority queue d) stack

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

public Stack() 5. What is the time complexity of pop() operation when

{ the stack is implemented using an array?
stk = new Object[CAPACITY]; a) O(1) b) O(n)
} c) O(logn) d) O(nlogn)
6. Which of the following array position will be occupied
public void push(Object item) by a new element being pushed for a stack of size N
{ elements(capacity of stack > N)?
if(size_of_stack==size) a) S[N-1] b) S[N]
{ c) S[1] d) S[0]
7. What happens when you pop from an empty stack
[Link]("Stack
while implementing using the Stack ADT in Java?
overflow");
a) Undefined error
return;
b) Compiler displays a warning
}
c) EmptyStackException is thrown
else
d) NoStackException is thrown
{ 8. What is the functionality of the following piece of Java
top++; code?
stk[top]=item; 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
public Object pop() have normal meaning.
{ public void some_function(int[] a)
if(top<0) {
{ Stack S=new Stack([Link]);
return -999; int[] b=new int[[Link]];
} for(int i=0;i<[Link];i++)
else {
{ [Link](a[i]);
Object ele=stk[top]; }
top--; for(int i=0;i<[Link];i++)
size_of_stack--; {
b[i]=(int)([Link]());
return ele;
}
}
[Link]("output :");
}
for(int i=0;i<[Link];i++)
}
{
[Link](b[i]);
public class StackDemo }
{ }
public static void main(String args[]) a) print alternate elements of array
{ b) duplicate the given array
Stack myStack = new Stack(); c) parentheses matching
[Link](10); d) reverse the array
Object element1 = [Link](); 9. Array implementation of Stack is not dynamic, which
Object element2 = [Link](); of the following statements supports this argument?
[Link](element2); a) space allocation for array is fixed and cannot be
} changed during run-time
} b) user unable to give the input for stack operations
a) stack is full b) 20 c) a runtime exception halts execution
c) 0 d) -999 d) improper program compilation

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

10. Which of the following array element will return the {

top-of-the-stack-element for a stack of size N if(empty())
elements(capacity of stack > N)? {
a) S[N-1] b) S[N] [Link](x);
c) S[N-2] d) S[N+1] }
else
STACK USING QUEUES {
1. To implement a stack using queue(with only if([Link]()>0)
enqueue and dequeue operations), how many {
queues will you need? [Link](x);
a) 1 b) 2 int size = [Link]();
c) 3 d) 4 while(size>0)
2. Making the push operation costly, select the code {
snippet which implements the same.(let q1 and q2 [Link]([Link]());
be two queues) size--;
a) }
public void push(int x) }
{ else if([Link]()>0)
if(empty()) {
{ [Link](x);
[Link](x); int size = [Link]();
} while(size>0)
else{ {
if([Link]()>0) [Link]([Link]());
{ size--;
[Link](x); }
int size = [Link](); }
while(size>0) }
{
}
[Link]([Link]());
c)
size--;
public void push(int x)
}
{
}
if(empty())
else if([Link]()>0)
{
{
[Link](x);
[Link](x);
}
int size = [Link]();
else
while(size>0)
{ {
[Link]([Link]()); if([Link]()>0)
size--; {
[Link](x);
}
int size = [Link]();
}
while(size>0)
}
{
}
[Link]([Link]());
b)
size--;
public void push(int x)

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

} 3. Making the push operation costly, select the code

} snippet which implements the pop operation.
else if([Link]()>0) a)
{ public void pop()
[Link](x); {
int size = [Link](); if([Link]()>0)
while(size>0) {
{ [Link]();
[Link]([Link]()); }
size--; else if([Link]()>0)
} {
} [Link]();
} }
} }
d)
b)
public void push(int x)
public void pop()
{
{
if(empty())
if([Link]()>0)
{
{
[Link](x);
[Link]();
}
}
else
else if([Link]()>0)
{
{
if([Link]()>0)
[Link]();
{
}
[Link](x);
}
int size = [Link]();
while(size>0) c)
{ public void pop()
[Link]([Link]()); {
size--; [Link]();
} [Link]();
} }
else if([Link]()>0) d)
{ public void pop()
[Link](x); {
int size = [Link](); if([Link]()>0)
while(size>0) {
{ [Link]();
[Link]([Link]()); }
size--; else
} {
} [Link]();
} }
} }

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

4. Select the code snippet which returns the top of {

the stack. return [Link]();
a) }
public int top()
return 0;
{
}
if([Link]()>0)
{ 5. Select the code snippet which return true if the
return [Link](); stack is empty, false otherwise.
} a)
else if([Link]()>0) public boolean empty()
{ {
return [Link]();
return [Link]();
}
return 0; }
} b)
b) public boolean empty()
public int top() {
{ return [Link]() || [Link]();
if([Link]()==0)
}
{
c)
return [Link]();
} public boolean empty()
else if([Link]()==0) {
{ return [Link]();
return [Link](); }
} d)
return 0;
public boolean empty()
}
{
c)
public int top() return [Link]() & [Link]();
{ }
if([Link]()>0) 6. Making the pop operation costly, select the code
{ snippet which implements the same.
return [Link](); a)
}
public int pop()
else if([Link]()>0)
{ {
return [Link](); int res=-999,count=0;
} if([Link]()>0)
return 0; {
} count = [Link]();
d)
while(count>0)
public int top()
[Link]([Link]());
{
if([Link]()>0) res = [Link]();
{ }
return [Link](); if([Link]()>0)
} {
else if([Link]()>0) count = [Link]();

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

while(count>0) d)
[Link]([Link]()); public int pop()
res = [Link](); {
} int res=-999,count=0;
return res; if([Link]()>0)
} {
b)
count = [Link]();
public int pop()
while(count>1)
{
[Link]([Link]());
int res=-999,count=0;
res = [Link]();
if([Link]()>0)
{ }
count = [Link](); if([Link]()>0)
while(count>1) {
[Link]([Link]()); count = [Link]();
res = [Link](); while(count>1)
} [Link]([Link]());
if([Link]()>0) res = [Link]();
{ }
count = [Link](); return res;
while(count>1) }
[Link]([Link]()); 7. What is the functionality of the following piece of
res = [Link]();
code?
}
public void fun(int x)
return res;
{
}
[Link](x);
c)
public int pop() }
{ a) Perform push() with push as the costlier
int res=-999,count=0; operation
if([Link]()>0) b) Perform push() with pop as the costlier
{ operation
count = [Link](); c) Perform pop() with push as the costlier
while(count>1) operation
[Link]([Link]()); d) Perform pop() with pop as the costlier
res = [Link](); operation
}
if([Link]()>0)
{
count = [Link]();
while(count>1)
[Link]([Link]());
res = [Link]();
}
return res;
}

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576
MAARULA CLASSES
DSA
(STACK OPERATIONS)
DPP-#01
TARGET- NIMCET / [Link] By: Amit Katiyar (MCA-JNU)
Scan the QR & Download Our App Now.

ANSWER KEY
STACK OPERATIONS
1. 2. 3. 4. 5.
b d a a d
6. 7. 8. 9. 10.
d c b d d
11. 12. 13. 14. 15.
c a b d b
16. 17. 18. 19. 20.
d c a c b
21. 22. 23. 24. 25.
b a a c a
26. 27. 28. 29.
d c a b
STACK USING LINKED LIST
1. 2. 3. 4. 5.
d d a c b
6. 7. 8. 9. 10.
b a d d c
STACK USING ARRAY
1. 2. 3. 4. 5.
a c c d a
6. 7. 8. 9. 10.
b c d a a
STACK USING QUEUES
1. 2. 3. 4. 5.
b a b c b
6. 7.
c b

ADDRESS: 117/466, O Block, Geeta Nagar, Sharda Nagar, NEAR: ANURAG HOSPITAL Kanpur, Uttar Pradesh 208025
website: [Link] 0512-3163515 9935985550 9554548576