Skip to content

Commit e858d14

Browse files
bhaskar16Bhaskar-Dastidar-E3295
bhaskar16
and
Bhaskar-Dastidar-E3295
authored
[JAVA-6029] reversing a stack (eugenp#13122)
* [JAVA-6029] reversing a stack * [JAVA-6029] un-necessary file changes removed Co-authored-by: Bhaskar <[email protected]>
1 parent 061c30a commit e858d14

3 files changed

Lines changed: 135 additions & 0 deletions

File tree

‎core-java-modules/core-java-collections-4/src/main/java/com/baeldung/collections/stackreversal/ReverseStackUsingQueue.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.baeldung.collections.stackreversal;
2+
3+
import com.baeldung.collections.sorting.Employee;
4+
5+
import java.util.LinkedList;
6+
import java.util.Queue;
7+
import java.util.Stack;
8+
9+
public class ReverseStackUsingQueue {
10+
public Stack reverseIntegerStack(Stack<Integer> inputStack) {
11+
Queue<Integer> queue = new LinkedList<>();
12+
while (!inputStack.isEmpty()) {
13+
queue.add(inputStack.pop());
14+
}
15+
while (!queue.isEmpty()) {
16+
inputStack.add(queue.remove());
17+
}
18+
return inputStack;
19+
}
20+
21+
public Stack reverseStringStack(Stack<String> inputStack) {
22+
Queue<String> queue = new LinkedList<>();
23+
while (!inputStack.isEmpty()) {
24+
queue.add(inputStack.pop());
25+
}
26+
while (!queue.isEmpty()) {
27+
inputStack.add(queue.remove());
28+
}
29+
return inputStack;
30+
}
31+
32+
public Stack reverseEmployeeStack(Stack<Employee> inputStack) {
33+
Queue<Employee> employeeQ = new LinkedList<>();
34+
while (!inputStack.isEmpty()) {
35+
employeeQ.add(inputStack.pop());
36+
}
37+
while (!employeeQ.isEmpty()) {
38+
inputStack.add(employeeQ.remove());
39+
}
40+
return inputStack;
41+
}
42+
}

‎core-java-modules/core-java-collections-4/src/main/java/com/baeldung/collections/stackreversal/ReverseStackUsingRecursion.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.baeldung.collections.stackreversal;
2+
3+
import java.util.Stack;
4+
5+
public class ReverseStackUsingRecursion {
6+
public Stack<Integer> reverseIntegerStack(Stack<Integer> inputStack) {
7+
reverseStack(inputStack);
8+
return inputStack;
9+
}
10+
11+
private void reverseStack(Stack<Integer> stack) {
12+
if (stack.isEmpty()) {
13+
return;
14+
}
15+
int top = stack.pop();
16+
reverseStack(stack);
17+
insertBottom(stack, top);
18+
}
19+
20+
private void insertBottom(Stack<Integer> stack, int value) {
21+
if (stack.isEmpty()) {
22+
stack.add(value);
23+
} else {
24+
int top = stack.pop();
25+
insertBottom(stack, value);
26+
stack.add(top);
27+
}
28+
}
29+
}

‎core-java-modules/core-java-collections-4/src/test/java/com/baeldung/stackreversal/StackReversalUnitTest.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.baeldung.stackreversal;
2+
3+
import com.baeldung.collections.sorting.Employee;
4+
import com.baeldung.collections.stackreversal.ReverseStackUsingQueue;
5+
import com.baeldung.collections.stackreversal.ReverseStackUsingRecursion;
6+
import org.junit.Assert;
7+
import org.junit.Test;
8+
9+
import java.util.*;
10+
import java.util.stream.Collectors;
11+
12+
public class StackReversalUnitTest {
13+
@Test
14+
public void whenIntegerStack_thenReturnReversedIntegerStack(){
15+
ReverseStackUsingQueue reverseStack = new ReverseStackUsingQueue();
16+
Stack<Integer> originalStack = generateStackFromGivenList(Arrays.stream(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}).boxed().collect(Collectors.toList()), new Stack<Integer>());
17+
Stack<Integer> reverseList = generateStackFromGivenList(Arrays.stream(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}).boxed().collect(Collectors.toList()), new Stack<Integer>());
18+
Assert.assertEquals(reverseStack.reverseIntegerStack(originalStack), reverseList);
19+
}
20+
21+
@Test
22+
public void whenStringStack_thenReturnReversedStringStack(){
23+
ReverseStackUsingQueue stackReversal = new ReverseStackUsingQueue();
24+
List<String> listOfWords = Arrays.asList(new String[]{"Hello", "I", "am", "reversing", "a", "stack"});
25+
List<String> listOfWordsReversed = new ArrayList<>(listOfWords);
26+
Collections.reverse(listOfWordsReversed);
27+
Stack<String> originalStack = generateStackFromGivenList(listOfWords, new Stack<String>());
28+
Stack<String> reversedStack = generateStackFromGivenList(listOfWordsReversed, new Stack<String>());
29+
Assert.assertEquals(stackReversal.reverseStringStack(originalStack), reversedStack);
30+
}
31+
32+
@Test
33+
public void whenEmployeeStack_thenReturnReversedEmployeeStack(){
34+
ReverseStackUsingQueue stackReversal = new ReverseStackUsingQueue();
35+
Employee employee1 = new Employee("John Doe", new Date());
36+
Employee employee2 = new Employee("John Nash", new Date());
37+
Employee employee3 = new Employee("Ryan Howard", new Date());
38+
List<Employee> employeeList = new ArrayList<>();
39+
employeeList.add(employee1);
40+
employeeList.add(employee2);
41+
employeeList.add(employee3);
42+
List<Employee> employeeReversed = new ArrayList<>(employeeList);
43+
Collections.reverse(employeeReversed);
44+
Stack<Employee> originalStack = generateStackFromGivenList(employeeList, new Stack<Employee>());
45+
Stack<Employee> reverseStack = generateStackFromGivenList(employeeReversed, new Stack<Employee>());
46+
Assert.assertEquals(stackReversal.reverseEmployeeStack(originalStack), reverseStack);
47+
}
48+
49+
@Test
50+
public void givenIntegerStack_whenStackReversed_thenReturnReversedRecursion(){
51+
ReverseStackUsingRecursion reverseStack = new ReverseStackUsingRecursion();
52+
Stack<Integer> originalStack = generateStackFromGivenList(Arrays.stream(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}).boxed().collect(Collectors.toList()), new Stack<Integer>());
53+
Stack<Integer> reversedStack = generateStackFromGivenList(Arrays.stream(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}).boxed().collect(Collectors.toList()), new Stack<Integer>());
54+
Assert.assertEquals(reverseStack.reverseIntegerStack(originalStack), reversedStack);
55+
}
56+
57+
private Stack generateStackFromGivenList(List elements, Stack stack){
58+
int start = 0;
59+
while (start < elements.size()){
60+
stack.add(elements.get(start++));
61+
}
62+
return stack;
63+
}
64+
}

0 commit comments

Comments
 (0)