Задача взята с сайта e-olymp.com.
Условие
Реализуйте структуру данных «очередь«. Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из очереди первый элемент. Программа должна вывести его значение.
front
Программа должна вывести значение первого элемента, не удаляя его из очереди.
size
Программа должна вывести количество элементов в очереди.
clear
Программа должна очистить очередь и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.
Входные данные
Описаны в условии. См. также пример входных данных.
Выходные данные
Описаны в условии. См. также пример выходных данных.
Тесты:
| № | Входные данные | Выходные данные: |
| 1 | push 1 front exit |
ok 1 bye |
| 2 | size push 1 size push 2 size push 3 size exit |
0 ok 1 ok 2 ok 3 bye |
Код на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static class Node { public int value; public Node next; public Node() { value = 0; next = null; } public Node(int newValue, Node newNext) { value = newValue; next = newNext; } } public static class Queue { private int size; private Node first; private Node last; public Queue() { size = 0; first = null; last = null; } public void push(int v) { Node newNode = new Node(v, null); if (size == 0) { first = last = newNode; } else { last.next = newNode; last = newNode; } size++; } public boolean pop() { boolean ret = false; if (size > 0) { int val = first.value; first = first.next; size--; System.out.println(val); ret = true; } return ret; } public boolean front() { boolean ret = false; if (size > 0) { System.out.println(first.value); ret = true; } return ret; } public int getSize() { return size; } public void clear() { first = null; last = null; size = 0; } } public static void main(String[] args) { Queue q = new Queue(); String s; int n; Scanner scan = new Scanner(System.in); while ((s = scan.next()) != null) { switch(s) { case "size": System.out.println(q.getSize()); break; case "push": n = scan.nextInt(); q.push(n); System.out.println("ok"); break; case "pop": if (q.pop() == false) { System.out.println("error"); } break; case "front": if (q.front() == false) { System.out.println("error"); } break; case "clear": q.clear(); System.out.println("ok"); break; case "exit": System.out.println("bye"); return; default: break; } } } } |
Алгоритм:
Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Для этого соответствующие методы делаем логическими.
Ссылки:
Рабочий код для тестирования на Ideone.com: Ideone.com