Реалізація стеку в Java

Шановні читачі ресурсу Codeguida! Давайте розглянемо разом з вами найважливіші структури даних, які, як відомо, є основою програмування. Одразу відповімо на головне питання будь-якого студента: «Навіщо мені потрібно це знати?». По-перше, програмісту обов'язково потрібна база, без міцного фундаменту, немає міцної будівлі. По-друге, будь-яка ІТ-компанія вимагає від людини, яка намагається влаштуватися на стажування/роботу, розуміння основ, і це ще один переконливий чинник для їх вивчення. Тож давайте розпочинати!

Сьогодні ж ми розглянемо таку просту, але потрібну структуру, як Стек (Stack). Ця структура даних має декілька реалізацій (найпростіші - реалізація на базі одновимірного масиву та однозв'язному списку). Зупинимося на першому варіанті.

Але для початку потрібно ознайомитися з невеликою теоретичною базою. Під час використання стеку, ми маємо доступ лише до останнього доданого елементу. Видаливши цей елемент, користувач отримує доступ до передостаннього елементу і тд. Таким чином ця структура даних реалізує принцип LIFO(Last In First Out). Для зручності можна провести аналогію зі стопкою тарілок або пістолетним магазином (останній заряджений набій, буде досланний у патронник першим). Багато мікропроцесорів мають стекову архітектуру. Коли відбувається виклик метода, адреса повернення та аргументи заносяться в стек, а при виході вилучаються з нього. Приклад стеку, з вершиною 5 (назвемо останній елемент – top).

Таким чином, щоб дістати зі стеку елемент «3», для початку нам потрібно видалити «5» та «4». На цьому наша невелика теоретична частина закінчується. Додам, що елемент TOP, інколи ще називають «головою» (head).

Отже, я пропоную реалізувати наступні методи для нашого стеку:

1. addElementToStack – метод , який забезпечить додавання елементу (до top позиції)

2. deleteElementFromStack - метод, яких забезпечить видалення елементу (з top позиції)

3. readTop – метод, який поверне значення елементу, який знаходиться в позиції top

4. isEmpty – метод, який перевірятиме, чи не порожній наш стек

5. isFull – метод, який перевірятиме, чи не переповнений наш масив, у якому ми зберігаємо стек

Для початку створимо у нашому проекті, клас Stack, оголосимо потрібні нам поля, там ініціалізуємо їх у конструкторі.

class Stack {
	private int maxSize;
	private int[] stackArray;
	private int top;

	public Stack(int max) {
		this.maxSize = max;
		stackArray = new int[maxSize];
		top = -1;
	}

Конструктор має параметр max, він дозволить користувачу ввести максимальний розмір стеку з клавіатури. Також, необхідно розуміти різницю між синтаксисом top++ та ++top. У першому випадку, спочатку виконується певна дія, а потім інкрементується(збільшується) лічильник. У другому, спочатку інкрементується лічильник, а потім виконується дія.

Реалізуємо вище згадані методи взаємодії зі стеком.

1. addElementToStack

public void addElementToStack(int element) {
		stackArray[++top] = element;
	}

Збільшуємо індекс масиву, та додаємо на вказану позицію переданий елемент.

2. deleteElementFromStack

public int deleteElementFromStack() {
		return stackArray[top--];
	}

Для видалення існуючого top елементу , достатньо зменшити індекс масиву. Таким чином нашою вершиною стеку стане передостанній елемент, а останній елемент буде видалений за допомогою Garbidge Collector (вбудований алгоритм менеджеру Java машини, для видалення певних елементів).

Графічна ілюстрація процесу видалення:

3. readTop

public int readTop() {
		return stackArray[top];
	}

Метод повертає користувачу елемент, який знаходиться на вершині стеку.

4. isEmpty

public boolean isEmpty() {
		return (top == -1);
	}

Повертає значення true (якщо масив даних порожній, індекс елементу top = 1, саме для цього ми задавали у конструкторі таке початкове значення для данної змінної).

5. isFull

public boolean isFull() {
		return (top == maxSize - 1);
	}

Метод повертає значення true (в тій ситуації, коли наш масив даних повністю заповнений і немає змоги додати ще один елемент). До речі може виникнути запитання, чому саме maxSize-1? Якщо ми задаємо максимальну кількість елементів масиву, як 10, то максимальний індекс буде 9 (індекси йдуть від 0 до 9).

У методі main реалізуємо введення чотирьох елементів, видалення одного з них і подальший вивід стеку на екран.

public class ClassicStack {

	public static void main(String[] args) {
		Stack theStack = new Stack(10);

		theStack.addElementToStack(89);
		theStack.addElementToStack(69);
		theStack.addElementToStack(45);
		theStack.addElementToStack(34);

		theStack.deleteElementFromStack();

		System.out.print("Наш стек: ");
		while (!theStack.isEmpty()) {
			int value = theStack.deleteElementFromStack();
			System.out.print(value);
			System.out.print(" ");
		}
			System.out.println("");
	}

Зверніть увагу, що стек видає елементи у порядку, оберненому до вводу. Тобто якщо ми вводили у стек 89, 69, 45, 34, то він поверне нам 34, 45, 69, 89. Саме тому цю структуру даних зручно застосовувати для вирішення задачі реверсу букв у слові або формування префіксного запису алгебраїчних виражень (Reverse Polish Notation). Одну із вище вказаних задач ми обов'язково розглянемо у наступному уроці.

Лістинг програми:

// autor BinaryUA

class Stack {
	private int maxSize;
	private int[] stackArray;
	private int top;

	public Stack(int max) {
		this.maxSize = max;
		stackArray = new int[maxSize];
		top = -1;
	}

	public void addElementToStack(int element) {
		stackArray[++top] = element;
	}

	public int deleteElementFromStack() {
		return stackArray[top--];
	}

	public int readTop() {
		return stackArray[top];

	}

	public boolean isEmpty() {
		return (top == -1);
	}

	public boolean isFull() {
		return (top == maxSize - 1);
	}
}

public class ClassicStack {

	public static void main(String[] args) {
		Stack theStack = new Stack(10);

		theStack.addElementToStack(89);
		theStack.addElementToStack(69);
		theStack.addElementToStack(45);
		theStack.addElementToStack(34);

		theStack.deleteElementFromStack();

		System.out.print("Наш стек: ");
		while (!theStack.isEmpty()) {
			int value = theStack.deleteElementFromStack();
			System.out.print(value);
			System.out.print(" ");
		}
			System.out.println("");
	}
}