Scribd
Upload
2 views3 pages

Stack Queue Full Answers

The document presents 20 questions related to Stack and Queue data structures in Java, each accompanied by code snippets and test cases. It covers various operations such as reversing a string, checking balanced parentheses, and implementing stacks and queues using arrays and linked lists. Additionally, it includes advanced topics like postfix evaluation, sorting stacks, and generating binary numbers.

Uploaded by

akarshdubey84350
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views3 pages

Stack Queue Full Answers

The document presents 20 questions related to Stack and Queue data structures in Java, each accompanied by code snippets and test cases. It covers various operations such as reversing a string, checking balanced parentheses, and implementing stacks and queues using arrays and linked lists. Additionally, it includes advanced topics like postfix evaluation, sorting stacks, and generating binary numbers.

Uploaded by

akarshdubey84350
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Stack and Queue - 20 Questions with Answers and

Test Cases (Java)

1. Reverse a String
String reverse(String s){
Stack<Character> st=new Stack<>();
for(char c:[Link]()) [Link](c);
String res="";
while(![Link]()) res+=[Link]();
return res;
}

Test Case: Input: hello Output: olleh

2. Balanced Parentheses
boolean isValid(String s){
Stack<Character> st=new Stack<>();
for(char c:[Link]()){
if(c=='('||c=='{'||c=='[') [Link](c);
else{
if([Link]()) return false;
char t=[Link]();
if((c==')'&&t!='(')||(c=='}'&&t!='{')||(c==']'&&t!='[')) return false;
}
}
return [Link]();
}

Test Case: Input: ([{}]) Output: true

3. Stack using Array


class Stack{
int top=-1;
int[] arr=new int[5];
void push(int x){arr[++top]=x;}
int pop(){return arr[top--];}
}

Test Case: push(10), push(20), pop() → 20

4. Stack using Linked List


class Node{int data;Node next;}
class Stack{
Node top;
void push(int x){Node n=new Node();[Link]=x;[Link]=top;top=n;}
int pop(){int x=[Link];top=[Link];return x;}
}

Test Case: push(5), push(8), pop() → 8

5. Next Greater Element


// Use stack to compare elements

Test Case: Input: [4,5,2,25] Output: 4->5, 5->25


6. Postfix Evaluation
int eval(String exp){
Stack<Integer> st=new Stack<>();
for(char c:[Link]()){
if([Link](c)) [Link](c-'0');
else{
int b=[Link](),a=[Link]();
if(c=='+') [Link](a+b);
}
}
return [Link]();
}

Test Case: Input: 23+ Output: 5

7. Infix to Postfix
Concept using stack

Test Case: A+B → AB+

8. Min Stack
Use extra stack to track minimum

Test Case: push(5,2,10) → min=2

9. Two Stacks in One Array


Use two pointers from both ends

Test Case: push1, push2

10. Sort Stack


Use recursion

Test Case: [3,1,2] → [1,2,3]

11. Queue using Array


class Queue{
int[] arr=new int[5];
int front=0,rear=0;
void enqueue(int x){arr[rear++]=x;}
int dequeue(){return arr[front++];}
}

Test Case: enqueue(10,20), dequeue → 10

12. Queue using Linked List


Use front & rear pointers

Test Case: enqueue(1,2) → dequeue=1

13. Circular Queue


Use mod (%) operator

Test Case: enqueue 1..5

14. Queue using Stack


Use 2 stacks

Test Case: enqueue(1,2,3), dequeue →1

15. Reverse Queue


Use stack

Test Case: 1 2 3 → 3 2 1

16. First Non-Repeating


Queue + frequency array

Test Case: aabc → a -1 b b

17. Sliding Window Maximum


Use deque

Test Case: [1,3,-1], k=3 → 3

18. Generate Binary


Queue<String> q=new LinkedList<>();
[Link]("1");

Test Case: Input:3 → 1 10 11

19. Interleave Queue


Split & merge

Test Case: 1 2 3 4 → 1 3 2 4

20. Deque
Use ArrayDeque

Test Case: addFirst, addLast

You might also like