очередь через массив

Задача

Реализуйте структуру данных «очередь». Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n — Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop — Удалить из очереди первый элемент. Программа должна вывести его значение.
front — Программа должна вывести значение первого элемента, не удаляя его из очереди.
size — Программа должна вывести количество элементов в очереди.
clear — Программа должна очистить очередь и вывести ok.
exit — Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Данную задачу также можно найти здесь.

Входные данные

Описаны в условии. Смотрите также тесты, расположенные ниже.

Выходные данные

Описаны в условии. Смотрите также тесты, расположенные ниже.

Тесты

№	Входные данные	Выходные данные
1	push 123 size push -5 pop exit	ok 1 ok 123 bye
2	push 1 push 2 front push 42 pop exit	ok ok 1 ok 1 bye
3	push 1 push 2 pop pop size exit	ok ok 1 2 0 bye

Код

import java.util.*;
import java.lang.*;
import java.io.*;

class MyQueue {
    int[] storage = new int[100];
    int start;
    int finish;
    MyQueue() {
        start = 0;
        finish = 0;
    }
    void push(int n) {
        storage[finish] = n;
        finish++;
    }
    int pop() {
        int a = storage[start];
        start++;
        return a;
    }
    int front() {
        return storage[start];
    }
    int size() {
        return finish - start;
    }
    String clear() {
        finish = 0;
        start = 0;
        return "ok";
    }
    String exit() {
        return "bye";
    }
}

public class Main {
	public static void main(String[] args) throws java.lang.Exception {
		String a;
		MyQueue x = new MyQueue();
		try (Scanner sc = new Scanner(System.in)) {
			while (sc.hasNextLine()){
				a = sc.next();
				if (a.equals("push")) {
					int n;
					n = sc.nextInt();
					x.push(n);
					System.out.println("ok");
				}
				if (a.equals("pop")) {
					System.out.println(x.pop());
				}
				if (a.equals("front")) {
					System.out.println(x.front());
				}
				if (a.equals("size")) {
					System.out.println(x.size());
				}
				if (a.equals("clear")) {
					System.out.println(x.clear());
				}
				if (a.equals("exit")) {
					System.out.println(x.exit());
					break;
				}
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class MyQueue {

int[] storage = new int[100];

int start;

int finish;

MyQueue() {

start = 0;

finish = 0;

}

void push(int n) {

storage[finish] = n;

finish++;

}

int pop() {

int a = storage[start];

start++;

return a;

}

int front() {

return storage[start];

}

int size() {

return finish - start;

}

String clear() {

finish = 0;

start = 0;

return "ok";

}

String exit() {

return "bye";

}

public class Main {

public static void main(String[] args) throws java.lang.Exception {

String a;

MyQueue x = new MyQueue();

try (Scanner sc = new Scanner(System.in)) {

while (sc.hasNextLine()){

a = sc.next();

if (a.equals("push")) {

int n;

n = sc.nextInt();

x.push(n);

System.out.println("ok");

}

if (a.equals("pop")) {

System.out.println(x.pop());

}

if (a.equals("front")) {

System.out.println(x.front());

}

if (a.equals("size")) {

System.out.println(x.size());

}

if (a.equals("clear")) {

System.out.println(x.clear());

}

if (a.equals("exit")) {

System.out.println(x.exit());

break;

}

Реализуем абстрактный тип данных очередь, который отвечает принципу FIFO («первый вошёл – первый вышел») с помощью массива. Очередь имеет начало и конец, на которые указывают соответственно start и finish. Изначально очередь является пустой, поэтому start = 0, finish = 0. При добавлении нового элемента в очередь записываем его в конец. finish при этом увеличиваем на единицу. Извлекаемый же элемент берём в начале очереди, после чего start++. Если необходимо получить значение начала очереди, не извлекая его, воспользуемся функцией front(), возвращающей значение первого элемента. Для получения размера очереди используем функцию size(), которая возвращает разницу между концом и началом очереди. Если очередь нужно очистить, то приравниваем finish и start к нулю.

Код на сайте ideone.com находится здесь.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: очередь через массив

e-olymp 6125. Простая очередь

Входные данные

Выходные данные

Тесты

Код