Печатать книгуПечатать книгу

Занятие 11. Справочник

Сайт: Информатикс
Курс: Фирма "1С". "Алгоритмы. Олимпиадное программирование на языке Java для школьников"
Книга: Занятие 11. Справочник
Напечатано:: Гость
Дата: Пятница, 18 Июль 2025, 07:59

Оглавление

Занятие 11. Справочник

Шаблонные классы в Java (generics)


Начиная с версии Java 5 в языке появился механизм обобщённого программирования — шаблоны, внешне близкие к шаблонам C++. С помощью специального синтаксиса в описании классов и методов можно указать параметры-типы, которые внутри описания могут использоваться в качестве типов полей, параметров и возвращаемых значений методов.
Для создания класса, который мы потом хотим приспособливать под работу с разными типами, в угловых скобках указывается псевдо-имя класса. А при объявлении объекта в угловых скобках указывается имя реального типа: 
// Объявление обобщённого класса
class GenericClass 
{
  T getFirst() { ... }
  void add(T obj) { ... }
}
Использование обобщённого класса в коде 

// var – объект класса GenericClass работы со строками
GenericClass  var = new GenericClass();
var1.add("qwerty");
String p = var1.getFirst();
Шаблоны конкретизируются именно классами, для примитивных типов (int, double и т.д.) их использовать нельзя!
Обратите внимание: публичный класс с функцией main должен быть объявлен первым. То есть классы MyQueue и MyStack следует размещать после основного класса.

Реализация стека на массиве (без защиты от ошибок)


Для использования следует заменить T везде в тексте на требуемый тип (например, int). 
class MyStack
{
	private int maxSize; // Размер массива
	private T[] stackArray;
	private int top; // Вершина стека

public MyStack(T s) // Конструктор
{
	maxSize = s; // Определение размера стека
	stackArray = new T[maxSize]; // Создание массива
	top = -1; // Пока нет ни одного элемента
}

public void push(T v) // Размещение элемента на вершине стека
 {
	top++;
 	stackArray[top] = v; // Увеличение top, вставка элемента
 }

public T pop() // Извлечение элемента с вершины стека
{    top--;
 	return stackArray[top+1]; // Извлечение элемента 
}
// --------------------------------------------------------------
 public long peek() // Чтение элемента с вершины стека
 {
 	return stackArray[top];
 }
// --------------------------------------------------------------
 public boolean empty() // true, если стек пуст
{
	if (top == -1) return true;
	return false;
}
public boolean full() // true, если стек полон
{
	if (top == maxSize - 1) return true;
	return false;
}
public void clear()
{
	top = -1;
}
}
Обратите внимание: публичный класс с функцией main должен быть объявлен первым. То есть классы MyQueue и MyStack следует размещать после основного класса.

Реализация очереди на массиве (без защиты от ошибок)


Для использования следует заменить T везде в тексте на требуемый тип (например, int). 
class MyQueue
{
	private int maxSize;
	private T[] queArray;
	private int front;
	private int rear;
	private int nItems; // Для простоты кода будем хранить
				    // и изменять количество элементов
	MyQueue(int s) // Конструктор
	{
		maxSize = s;
		queArray = new T[maxSize];
		front = 0;
		rear = -1;
		nItems = 0;
	}

	public void clear()
	{
		front = 0;
		rear = -1;
		nItems = 0;
	}

	public void offer(T v) // Добавить элемент в очередь
	{
		if(rear == maxSize - 1) // проверка на конец массива
			rear = -1;
		rear++;
		queArray[rear] = v; 
		nItems++; // увеличить счетчик
	}

	public T poll() // Извлечение первого элемента очереди
	{
		T temp = queArray[front]; // взять элемент
		front++;
		if(front == maxSize) // проверка на конец массива
			front = 0;
		nItems--; // уменьшить количество элементов
		return temp;
	}

	public T peek() // Чтение первого элемента очереди
	{
		return queArray[front];
	}
	public  boolean empty() // true если очередь пуста
	{
		if (nItems == 0) return true;
		return false;
	}

	public boolean isFull() // true если очередь полна
	{
		if (nItems == maxSize) return true;
		return false;
	}
}
Обратите внимание: публичный класс с функцией main должен быть объявлен первым. То есть классы MyQueue и MyStack следует размещать после основного класса.

Реализация очереди для элементов типа int на массиве шаблонным классом (без защиты от ошибок)

class MyQueue
{
	private int maxSize;
	private int[] queArray;
	private int front;
	private int rear;
	private int nItems; // Для простоты кода будем хранить
				    // и изменять количество элементов
	MyQueue(int s) // Конструктор
	{
		maxSize = s;
		queArray = new int[maxSize];
		front = 0;
		rear = -1;
		nItems = 0;
	}

	public void clear()
	{
		front = 0;
		rear = -1;
		nItems = 0;
	}

	public void offer(int v) // Добавить элемент в очередь
	{
		if(rear == maxSize - 1) // проверка на конец массива
			rear = -1;
		rear++;
		queArray[rear] = v; 
		nItems++; // увеличить счетчик
	}

	public int poll() // Извлечение первого элемента очереди
	{
		int temp = queArray[front]; // взять элемент
		front++;
		if(front == maxSize) // проверка на конец массива
			front = 0;
		nItems--; // уменьшить количество элементов
		return temp;
	}

	public int peek() // Чтение первого элемента очереди
	{
		return queArray[front];
	}
	public  boolean empty() // true если очередь пуста
	{
		if (nItems == 0) return true;
		return false;
	}

	public boolean isFull() // true если очередь полна
	{
		if (nItems == maxSize) return true;
		return false;
	}
}

Встроенный класс Stack


Для примитивных типов необходимо использовать классы обертки!
boolean empty()
Tests if this stack is empty.
E peek()
Looks at the object at the top of this stack without removing it from the stack.
E pop()
Removes the object at the top of this stack and returns that object as the value of this function.
E push(E item)
Pushes an item onto the top of this stack.
int search(Object o)
Returns the 1-based position where an object is on this stack.
Пример использования: 
Stack q = new Stack();
q.push(new Integer(1)); // оборачиваем int в Integer
q.push(new Integer(2)); // оборачиваем int в Integer

System.out.println(q.pop() + ", " + q.pop());
Программа выведет 2, 1

Встроенный интерфейс Queue


Для примитивных типов необходимо использовать классы обертки!
boolean add(E e)
Inserts the specified element into this Queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E element()
Retrieves, but does not remove, the head of this Queue.
boolean offer(E e)
Inserts the specified element into this Queue if it is possible to do so immediately without violating capacity restrictions.
E peek()
Retrieves, but does not remove, the head of this Queue, or returns null if this Queue is empty.
E poll()
Retrieves and removes the head of this Queue, or returns null if this Queue is empty.
E remove()
Retrieves and removes the head of this Queue.
Реализуется, например, классом LinkedList.
Пример использования: 
LinkedList q = new LinkedList();
q.offer("a");
q.offer("b");
System.out.println(q.poll() + ", " + q.poll());
Программа выведет a, b
Кстати, LinkedList не требует при создании указания максимального размера и расширяется по мере необходимости