JetBrains Academy: Queue and Stack - Kamil-Jankowski/Learning-JAVA GitHub Wiki
Creating queue:
Create ArrayDeque named queue and push the following four numbers 2, 0, 1, 7.
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(2);
queue.offer(0);
queue.offer(1);
queue.offer(7);
System.out.println(queue);
}
}Working with queue:
There is a queue with four elements. Put in it the number 5, and then take two items out of the queue.
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new ArrayDeque<>(Arrays.asList(1, 2, 3, 4));
queue.offer(5);
queue.poll();
queue.poll();
System.out.println(queue);
}
}The LIFO principle in action:
Write a program that reads the input elements and outputs them in the reverse order.
The first string contains the number of elements. Each line followed the first one contains an element.
import java.util.*;
class Main {
public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
int elements = Integer.parseInt(scanner.nextLine());
Deque<String> stack = new ArrayDeque<>();
for (int i = 0; i < elements; i++){
stack.offerFirst(scanner.nextLine());
}
for (int i = 0; i < elements; i++){
System.out.println(stack.pollFirst());
}
}
}Even numbers go first:
Write a program that reads numbers and stores them to a deque. Any even number should be added as the first element, an odd number as the last. After it, the program must output all elements from the first to the last.
It is important, that the first line contains the number of elements. Each line followed the first one contains an element.
import java.util.*;
class Main {
public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < size; i++){
int number = scanner.nextInt();
if(number % 2 == 0){
deque.offerFirst(number);
} else {
deque.offerLast(number);
}
}
deque.forEach(num -> System.out.println(deque.pollFirst()));
}
}Which brackets are balanced:
Given a string consisting of brackets, write a program to examine whether the pairs and the orders of "{", "}", "(", ")", "[", "]" are correct (balanced). For example, the program should print true for the string [()]{}{[()()]()} and false for ()[]}.
The classic algorithm for solving this problem relies on using a stack.
1. create an instance of a stack;
2. traverse the input string;
-
if the current character is a starting bracket "(" or "{" or "[" then push it to the stack;
- if the current is a closing bracket ")" or "}" or "]" then remove (pop) the top element from the stack; if the popped bracket is the matching starting bracket then fine else parenthesis are not balanced;
3. after completing traversal, if there are some starting brackets left in the stack, then the parenthesis are not balanced.
import java.util.*;
class Main {
public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
char[] line = scanner.nextLine().toCharArray();
Deque<Character> stack1 = new ArrayDeque<>();
Deque<Character> stack2 = new ArrayDeque<>();
Deque<Character> stack3 = new ArrayDeque<>();
boolean flag1 = true;
boolean flag2 = true;
boolean flag3 = true;
for (char bracket : line){
if (bracket == '('){
stack1.offerFirst(bracket);
} else if (bracket == '['){
stack2.offerFirst(bracket);
} else if (bracket == '{'){
stack3.offerFirst(bracket);
} else if (bracket == ')'){
if (stack1.size() > 0){
stack1.pollFirst();
} else {
flag1 = false;
}
} else if (bracket == ']'){
if (stack2.size() > 0){
stack2.pollFirst();
} else {
flag2 = false;
}
} else if (bracket == '}'){
if (stack3.size() > 0){
stack3.pollFirst();
} else {
flag3 = false;
}
}
}
if (flag1 && flag2 && flag3){
System.out.println(stack1.size() + stack2.size() + stack3.size() == 0);
} else {
System.out.println(false);
}
}
}Greedy load balance:
Write a program that implements a simple load balancer.
The program must read tasks from the standard input and distribute them between two queues. Tasks will be processed by a system (in future). Each task has a unique identifier and a number indicating the load on the system (in parrots).
The balancer should distribute tasks between queues by the following rule: the task is added to the lower-load queue (by the total load). If both queues have the same total load indicator, the task must be added to the first queue.
It's guaranteed, the input data contain at least two tasks.
Input data format:
The first line contains the number of tasks. Other lines consist of task description: an identifier and a load indicator (separated by a space).
Output data form:
The first line should contain identifiers of tasks in the first queue, the second line - in the second queue.
import java.util.*;
class Main {
public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
int tasks = scanner.nextInt();
Queue<Integer> first = new ArrayDeque<>();
int firstLoad = 0;
Queue<Integer> second = new ArrayDeque<>();
int secondLoad = 0;
for (int i = 0; i < tasks; i++){
int task = scanner.nextInt();
int load = scanner.nextInt();
if (firstLoad <= secondLoad){
first.offer(task);
firstLoad += load;
} else {
second.offer(task);
secondLoad += load;
}
}
first.forEach(num -> System.out.print(num + " "));
System.out.println();
second.forEach(num -> System.out.print(num + " "));
}
}Getting the max element of a stack:
Write a program simulating a stack that can effectively return the current max element. Your program should read a sequence of commands of different types from the standard input.
There are three types of commands:
- push v - add an element (v) to a top of the stack;
- pop - remove the top element of the stack;
- max - return the current max in the stack.
The time complexity of these operations should not depend on the stack size (constant time, O(1)).
Hint: you may use several standard stacks to write a solution.
Input data format:
The first line contains the number of commands. Next lines contain one of the following commands: push v, pop, max.
Output data format:
The program must output the current max for each command max.
import java.util.*;
class Main {
public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
int lines = Integer.parseInt(scanner.nextLine());
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> currentMax = new ArrayDeque<>();
currentMax.offerFirst(0);
int max;
for (int i = 0; i < lines; i++){
String command = scanner.next();
max = currentMax.size() > 0 ? currentMax.peekFirst() : 0;
switch (command){
case "push":
int number = Integer.parseInt(scanner.next());
stack.offerFirst(number);
if (number > max){
max = number;
}
currentMax.offerFirst(max);
break;
case "pop":
stack.pollFirst();
currentMax.pollFirst();
break;
case "max":
System.out.println(max);
break;
default:
return;
}
}
}
}Html Parser:
Today you will create your own HTML parser! You should get all the content from tags.
- For example:
<h4><br>content</br></h4> - Answer: from
<br>(content), after that from<h4>(<br>content</br>)
Note: all tags are valid.
Remember: The order of the contents on the same level of the hierarchy should be as in the input string.
import java.util.*;
class Main {
public static void main(String[] args) {
final Scanner scanner = new Scanner(System.in);
Deque<Integer> indexes = new ArrayDeque<>();
String line = scanner.nextLine();
char[] html = line.toCharArray();
boolean write = true;
for (int i = 0; i < html.length; i++){
if (html[i] == '>' && write){
indexes.offerFirst(i+1);
} else if (html[i] == '/'){
System.out.println(line.substring(indexes.pollFirst(), i-1));
write = false;
} else if (html[i] == '>' && !write){
write = true;
}
}
}
}