THINK FIRST·CODE LATER

← All labs

Folder sizes with a queue and with a stack

Problem

Computing the size of a folder is naturally recursive; here you do it without recursion, first with a queue, then with a stack.

The input describes a folder tree: the number of entries n, then one line per entry — D name parent for a folder, F name parent size for a file — where parent is the line number (1-based) of its parent folder; entry 1 is the root, with parent 0.

Write FolderSize:

  1. build the tree (each entry has a list of children);
  2. traverse it breadth-first with a queue: total size, number of files and folders, deepest level (the root is level 0), largest file (the first one in case of a tie), and the order of the visits;
  3. traverse it again with a stack (push the children in reverse so that the first child is visited first) and check that the total is the same.

For the input

9
D root 0
D docs 1
F todo.txt 1 120
F cv.pdf 2 5000
D photos 2
F a.jpg 5 20000
F b.jpg 5 30000
D empty 1
F notes.md 2 80

the program prints

Total size: 55200 bytes in 5 file(s) and 4 folder(s)
Deepest level: 3
Largest file: b.jpg (30000)
Queue order: root docs todo.txt empty cv.pdf photos notes.md a.jpg b.jpg
Stack order: root docs cv.pdf photos a.jpg b.jpg notes.md todo.txt empty
Same total with the stack: true

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d4-9-data-1.txt

9
D root 0
D docs 1
F todo.txt 1 120
F cv.pdf 2 5000
D photos 2
F a.jpg 5 20000
F b.jpg 5 30000
D empty 1
F notes.md 2 80
What your program must print for d4-9-data-1.txt
Total size: 55200 bytes in 5 file(s) and 4 folder(s)
Deepest level: 3
Largest file: b.jpg (30000)
Queue order: root docs todo.txt empty cv.pdf photos notes.md a.jpg b.jpg
Stack order: root docs cv.pdf photos a.jpg b.jpg notes.md todo.txt empty
Same total with the stack: true

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d4-9-data-1.txt

Windows PowerShell does not understand <:

Get-Content d4-9-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.