Java очереди стеки деки

Коллекции: очередь и стек

Ранее мы рассматривали наиболее популярные Коллекции: list, set, map. В данной статье рассмотрим чуть более специфичные коллекции. Все рассмотренные ниже коллекции реализуют один из двух алгоритмов манипулирования данными: «First In – First Out» (FIFO) и «Last In – First Out» (LIFO).

Очередь

Очередь реализует принцип «first in – first out», т.е. «первым пришёл – первым ушёл». Базовым интерфейсом всех очередей Java является Queue. Добавление элементов в очередь делается методом add(), удаление – poll(), получение первого элемента без его удаления – peek().

Две самые простые реализации очереди – это LinkedList и PriorityQueue. Рассмотрим их на примере.

Queue queue = new LinkedList<>();
queue.add( «банан» );
queue.add( «яблоко» );
queue.add( «ананас» );
while (queue.peek() != null ) < // или !queue.isEmpty()
System.out.println(queue.poll());
>

Здесь мы добавляем в очередь LinkedList некоторые строки, затем в цикле извлекаем их из очереди и одновременно выводим на экран. Наличие элементов в очереди проверяем через метод peek(), который возвращает null в случае, если элементов не осталось. Это сделано лишь для наглядности. Логичнее наличие элементов проверять через метод isEmpty(). В результате увидим, что элементы извлекаются в том же порядке, в котором были добавлены:

Обратите внимание, что LinkedList также реализует интерфейс List, который мы рассматривали в предыдущей статье.

Теперь проделаем то же самое с очередью PriorityQueue.

Queue queue = new PriorityQueue<>();
queue.add( «банан» );
queue.add( «яблоко» );
queue.add( «ананас» );
while (!queue.isEmpty()) System.out.println(queue.poll());
>

На экране увидим следующее:

То есть вопреки порядку добавления, элементы извлекаются в алфавитном порядке. Таким образом, можно сделать вывод, что PriorityQueue сортирует элементы в порядке возрастания (или алфавитный порядок для строк).

Стек

Стек реализует принцип «last in – first out», т.е. «последним пришёл – первым вышел». Аналогия из реального мира – это стопка книг на столе (сначала берём верхнюю). В Java есть одноимённый класс Stack. Добавление элементов осуществляется методом push(), а удаление методом pop(). Рассмотрим пример:

Stack stack = new Stack<>();
stack.push( 1 );
stack.push( 2 );
stack.push( 3 );
while (!stack.empty()) System.out.println(stack.pop());
>

То есть элементы извлекаются в обратном порядке, начиная с последнего. Класс Stack является расширением класса Vector. Оба этих класса появились ещё в Java 1.0. Ныне они считаются устаревшими и их не рекомендуется применять в новых проектах.

Дек

Интерфейс Deque позиционируется как современная альтернатива классу Stack. Deque – это сокращение от «double ended queue» (двусторонняя очередь). Технически Deque является расширением интерфейса очереди Queue.

Интерфейс Deque реализуют всё тот же LinkedList, а также ArrayDeque.

Пример работы с деком в качестве стека:

Deque stack = new ArrayDeque<>();
stack.push( 1 );
stack.push( 2 );
stack.push( 3 );
while (!stack.isEmpty()) System.out.println(stack.pop());
>

Выводы

На основании рассмотренных нами интерфейсов и реализаций можно сделать вывод, что для самой простой реализации очереди Queue следует выбрать LinkedList. Eсли требуется как-то сортировать элементы внутри очереди, то подойдёт PriorityQueue. Если же нам нужна функциональность стека, то надо использовать интерфейс Deque и одну из его реализаций: LinkedList или ArrayDeque.

Источник

Data structures 101: How to use stacks and queues in Java

Mastering data structures is non-negotiable. Efficient data structures help execute effective programs. Today, many programming roles require great knowledge of data structures. They are also a fundamental part of coding interviews.

Stacks and queues are linear data structures that follow a particular order to add or remove entities. In this article, you will be introduced to stacks and queues. We will highlight their uses, functionalities, and show you how to implement these data structures in Java.

Today, we will cover:

Master data structures for coding interviews with hands-on practice

Learn data structures with practical, real-world problems from coding interviews.

Data Structures for Coding Interviews in Java

What is a Stack?

In programming, a stack is an abstract, linear data type with a predefined capacity (or boundary). It follows a particular order for adding or removing elements. Linear data structures organize their components in a straight line, so if we add or remove an element, they will grow or shrink respectively.

Let us conceptualize stacks using a stack of plates placed in a box. The first plate placed in the stack (the plate at the bottom of the stack) will be the last one to be removed, and the plate added last would be the first to be removed.

This is called the Last In First Out (LIFO) or First In Last Out (FILO) ordering.

Stacks are used in a variety of ways when we code. We use stacks to implement functions, parsers, expression evaluation, and some algorithms. Stacks are great for processing nested structures, so they are important for understanding recursion.

A simple real-world application of a stack is reversing a string letter by letter. Another good example of a data stack is the undo and redo function on a computer or text editor. Undo removes your most recent change, and redo builds upon already existing changes.

How do Stacks work?

The implementation of stacks is relatively easy. The functionality depends on the pop and push method, as you can see from the illustration above. The pop method removes or deletes elements from the stack, while the push method adds items to the stack.

When an element is inserted into a stack, it takes the top position and the variable storing this position points to the number below it. The top variable should be updated anytime an element is inserted or removed from it.

Note: What’s important to remember is that insertion and deletion happen on the same end of a Stack.

Later in this article, we will learn how to manually implementing the Stack data structure in Java.

What is a Queue?

A queue is a lot like a stack. A Queue is also a linear structure that follows a First In First Out (FIFO) order, but they differ in how elements are removed. Queues are open from both ends: one end for inserting data ( enqueue ), and the other end for removing data ( dequeue ). A stack is only open from one end.

Simplied: for a stack we remove the most recently added element, but for a queue, we remove the “oldest” element.

Источник

Стек, очередь и куча

На рисунке вы можете видеть обобщенную модель организации памяти компьютера.

Стек — это область памяти, которую вы, как программист, не контролируете никоим образом. В неё записываются переменные и информация, которые создаются в результате вызова любых функций. Когда функция заканчивает работу, то вся информация о ее вызов и ее переменные удаляются из стека автоматически.

Но важнее даже не это, а то, что стек — это структура данных, которая работает по принципу «последним пришел — первым ушел» (last in first out, LIFO). На лекции Дэвид предложил представление стека, как стопки подносов в столовой. Поднос, который попал в стопку последним, новый клиент столовой возьмет в первую очередь.

Над стеком можно осуществлять две операции: push (занесение данных) и pop (изъятие данных).

Пример реализации стека языке С приведен ниже. В этом примере, стек — это просто массив строк, имеет определенную емкость (CAPACITY), и текущий размер (size):

Чтобы реализовать операцию push , необходимо сделать проверку, не превышает текущий размер емкость стека, после чего — вставить элемент на позицию size и увеличить size на единицу.

Для реализации операции pop, необходимо проверить, не пустой стек, уменьшить текущий размер на единицу и вернуть элемент.

Очередь

Очередь (queue) — это структура данных, которая напоминает обычную очередь. То есть, в отличие от стека, она работает по принципу «первым пришел — первым ушел» (first in first out, FIFO).

Для очереди определены две операции: добавление элемента в конец очереди (enqueue) и изъятие элемента с начала очереди (dequeue).

В примере объявлена очередь, которая, по сути, представляет собой массив строк:

Чтобы реализовать операцию enqueue, необходимо убедиться, что очередь, не переполнена, добавить элемент в конец очереди и увеличить текущий размер на единицу.

Чтобы реализовать операцию dequeue, надо убедиться, что очередь не пуста, увеличить head на единицу, уменьшить текущий размер и вернуть первый элемент очереди.

Куча и переполнение буфера

Куча (heap) — область памяти, которую контролируют непосредственно программисты. Над которой вы, как программисты, получаете непосредственный контроль. Память здесь выделяется в результате вызова функции malloc.

Более глубокие знания о стеке и куче вам пока не понадобятся. Вы их получите позже, если захотите изучать программирование и компьютерные науки глубже.

Буфер — это массив определенной длины, расположенный в памяти. Переполнение буфера (buffer overflow) возникает, если мы пытаемся записать в него больше данных, чем предусмотрено размером этого массива. С помощью переполнения буфера злоумышленник может записать опасный код в память компьютера.

Источник