Стек. Структуры данных.

Определение стека

Стек – линейная структура данных, в нем действует принцип LIFO(Last In First Out – последним – пришёл, первым – вышел) или же FILO(First In Last Out – первым – вошел и последним – вышел).

Другими словами, это какой-то набор данных, для которых определено как мы добавляем элементы и каким образом мы оттуда их берем. Давайте поскорее перейдем к примеру, что бы не оперировать сухими терминами в которые надо вчитываться.

Давайте представим стек как набор тарелок лежащих одна на другой в стопке.

Условимся, что мы не можем положить новую тарелку куда-то в середину. Так же не можем достать откуда попало. Для этого нам прийдется сделать больше усилий. Здесь мы с легкостью можем класть новые тарелки сверху и брать их оттуда же. Эта операция для нас будет очень легкой, нам не прийдется искать их где-то в стопке, поднимать часть, переворачивать, разбивать. Похожий аналог мы можем увидеть в программировании. Для решения определенного класса задач очень удобно использовать стек, так как он экономит наши вычислительные ресурсы. Сложность операции положить/взять очень низка. Просто взял и положил сверху. Жаль что не все так просто в нашей жизни. Это и есть примитивный пример стека.

Стек. Базовые операции.

Давайте определим что мы можем делать с нашим стеком. Как мы уже рассмотрели выше, можем сделать такой базовый список операций со стеком

• Push – добавить элемент в стек. Если стек полон, то результат этой операции будет говорить о переполнении стека, как название всеми известного сайта
• Pop – положив что-то, мы когда-то захочет взять. Данная операция берет один элемент из стека. Элементы берутся в обратном порядке от добавления. Элемент, что был положен ранее будет взят позже. Тарелка в самом низу будет взята последней.
• Peek/Top – чтение верхнего элемента. Данная операция возвращает верхний элемент стека.

Сложность операций в стеке

Основная причина использования тех или иных структур данных заключается в сложности работы с ними. Сколько усилий потребуется что бы достать верхнюю тарелку, положить новую или поменять порядок на реверсивный? Сложность алгоритмов претендует на отдельную статью, возможно я когда-то ее напишу. Если вы знакомы с этим понятием – давайте разберем сложность рассмотренных. операций. Если же нет – то просто прочитайте для общего развития и подпишитесь на обновления блога что бы нервно каждый день ждать статьи по сложности алгоритмов.

Сложность любой из рассмотренных операций Push, Pop, Peek является O(1). Это очень хорошо. Текущая сложность очень низка и позволяет без проблем оперировать элементами стека. Например, если бы нам пришлось проходится по всему массиву элементов, что бы найти элемент, – то сложность бы составила O(n).

Реализация стека (Java)

Давайте рассмотрим пример реализации стека на языке Java. Пусть максимальное число элементов в стеке будет 500. Укажем в конструкторе что в начальном положении стек пуст. Так же добавим метод isEmpty который будет проверять пуст ли наш стек. Далее реализуем основные методы: push, pop и peek. Реализация этих методов не должна вызвать большие затруднения. Попробуйте, для начала, сами написать их. Ниже приведен код реализации стека.

class Stack { 
	static final int MAX = 500; 

	int top; 

	int a[] = new int[MAX]; // Maximum size of Stack 

	Stack() 
	{ 
		top = -1; 
	} 

	boolean isEmpty() 
	{ 
		return (top < 0); 
	}

	boolean push(int x) 
	{ 
		if (top >= (MAX - 1)) { 
			System.out.println("Stack Overflow :(");

			return false; 
		}
		a[++top] = x; 
		System.out.println(x + " pushed into stack"); 

		return true; 
	} 

	int pop() 
	{ 
		if (top < 0) { 
			System.out.println("Stack Underflow :("); 

			return 0; 
		} 
		int x = a[top--];

		return x;
	} 

	int peek() 
	{ 
		if (top < 0) { 
			System.out.println("Stack Underflow :("); 

			return 0; 
		}
		int x = a[top]; 

		return x;
	} 
} 

class Main { 
	public static void main(String args[]) 
	{ 
		Stack s = new Stack(); 

		s.push(3); 
		s.push(50); 
		s.push(22); 

		System.out.println(s.pop()); 
	} 
}