Как они работают и как собрать свои собственные
(Примечание: если вы не читали предыдущие статьи этой серии о Связанных списках и Деревьях двоичного поиска, обязательно ознакомьтесь с ними!)
Если деревья двоичного поиска - это марафон на 10 км, стеки и очереди будут 5-минутной прогулкой до парка. На самом деле они очень интуитивно понятны и отражают множество реальных жизненных ситуаций, так что давайте сразу же приступим к их изучению!
Стеки и очереди - это, по сути, динамические линейные массивы, в которых вы можете управлять вставкой и удалением записей данных только одним определенным способом.
Как следует из названия, вы можете думать о стопке как о стопке тарелок; когда вы хотите добавить тарелку в стопку, вы должны положить ее наверх стопки. Точно так же, когда вы хотите вынуть тарелку, вы можете вынуть только самую верхнюю тарелку в стопке, то есть ту, которую вы добавили последней. Следовательно, стеки - это LIFO - Last In, First Out. Таким образом, стеки выполняют две основные функции: первая, называемая push, заключается в том, что вы вставляете элементы в «верх» стека. Другой, называемый pop, возникает, когда вы удаляете самый верхний элемент в стеке и извлекаете его данные.
С другой стороны, для очереди вы можете представить ее как группу людей, выстраивающихся в очередь на просмотр фильма; человек, к которому присоединился самый новый, добавляется в конец строки, в то время как первый человек, вышедший из очереди, был первым в очереди. Следовательно, очереди - FIFO - First In First Out. Обычно для изменения очередей мы используем два метода: enqueue, который добавляет значение в конец очереди, и dequeue, который удаляет и возвращает самый передний (или самый старый) запись в очереди.
Прелесть стеков и очередей в том, что вместо того, чтобы реализовываться по отдельности, они обычно строятся поверх других структур как своего рода всеобъемлющая структура. Например, вы можете построить стек поверх связанного списка! Более того, стеки и очереди обычно используются как инструменты для выполнения определенной задачи; тогда как другие структуры, такие как связанные списки и деревья, используются для хранения реальных объектов.
Поскольку и стеки, и очереди предлагают только последовательный доступ, а не произвольный, они будут иметь эффективность O (1) - постоянное время. (Узнайте о нотации Big O здесь!)
Закодируйте очередь!
Давайте сразу приступим. Для начала давайте определим класс:
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
}
Итак, во-первых, мы определили всеобъемлющий класс Queue. Внутри очереди мы определили класс под названием Node - по сути, структуру, - которая будет содержать информацию, необходимую для каждой записи в нашей очереди. Как и узлы в связанном списке, каждый узел в очереди должен иметь как минимум два элемента; некоторые данные и указатель на следующий узел в очереди. Первая строка в классе Node, private int data, обрисовывает данные; следующий частный узел дает нам указатель; private Node (int data) - это конструктор, который упростит нам установку значений данных позже.
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node head;
private Node tail;
public boolean isEmpty() {
return head == null;
}
public int peek() {
return head.data;
}
}
Затем мы определили два элемента; голова частного узла и хвост частного узла. Помните, мы хотим иметь возможность удалять элементы из головы и добавлять элементы в хвост очереди. Поэтому, прежде чем мы это сделаем, мы на самом деле собираемся быстро создать две функции, которые помогут нам избежать каких-либо сбоев со структурой: первая, public boolean isEmpty (), уведомляет вас, когда очередь пусто / не существует. Другой, public int peek (), позволяет получать данные из заголовка очереди.
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node head;
private Node tail;
public boolean isEmpty() {
return head == null;
}
public int peek() {
return head.data;
}
public void add(int data) {
Node node = new Node(data);
if (tail != null) {
tail.next = node;
}
tail = node;
if (head == null) {
head = node;
}
}
}
Новейшим дополнением к нашему коду является функция под названием public void add (int data), которая позволяет нам добавлять новый узел в хвост очереди; также известна как функция постановки в очередь. Итак, сначала с помощью строки Узел узел = новый узел (данные) мы создаем новый узел, используя класс узла, и вставляем некоторые данные в этот новый узел. Затем с помощью if (tail! = Null) мы проверяем, существует ли хвост очереди; если это так, то мы указываем на следующий слот после хвоста и помещаем туда наш новый узел. После этого в строке tail = node мы обновляем и устанавливаем этот новый узел в качестве нашего текущего хвоста.
Но ждать! Прежде чем закрыть эту функцию, нам нужно проверить, существует ли вообще наша очередь; если нет (head == null), мы устанавливаем новый узел в качестве главы новой очереди. Хорошо, теперь нам пора.
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node head;
private Node tail;
public boolean isEmpty() {
return head == null;
}
public int peek() {
return head.data;
}
public void add(int data) {
Node node = new Node(data);
if (tail != null) {
tail.next = node;
}
tail = node;
if (head == null) {
head = node;
}
}
public int remove() {
int data = head.data;
head = head.next;
if (head == null) {
tail == null;
}
return data;
}
}
Итак, новейшая функция, которую мы здесь написали, - это функция remove, которая удаляет и возвращает заголовок очереди, также известный как первый человек в строке. Это также то, что я ранее описывал как функцию удаления из очереди.
Мы начинаем работу с функции, сначала извлекая данные из головы с помощью int data = head.data. После этого мы обновляем головной узел, заменяя его нашим новым узлом, перемещая головной узел в позицию после него, которая является head.next. Мы также включаем оператор if, чтобы определить случай, когда очередь не существует (если нет головы, то не должно быть и хвоста), а затем мы, наконец, возвращаем данные нового голова.
Итак, это была ваша очередь! Перейдем к стопкам.
Кодирование стека
Давайте сначала начнем с основ:
public static class Stack {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node top;
}
Как и в случае с очередью, мы сначала определяем класс Node, который содержит некоторые данные, указатель и конструктор. Затем мы определяем элемент top. Поскольку стек - это LIFO (последний вошел, первый вышел), нам действительно нужно иметь дело только с элементом, который находится наверху стека, поэтому нет необходимости в голове или хвосте, как в очереди.
public static class Stack {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node top;
public boolean isEmpty() {
return top == null;
}
public int peek() {
return top.data;
}
}
Затем, аналогично очереди, мы проверяем, существует ли стек, с помощью public boolean isEmpty (), а также создаем функцию, которая позволяет нам просто извлекать данные самого верхнего элемента с помощью peek ().
public static class Stack {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node top;
public boolean isEmpty() {
return top == null;
}
public int peek() {
return top.data;
}
public void push(int data) {
Node node = new node(data);
node.next = top;
top = node;
}
public void pop() {
int data = top.data;
top = top.next;
return data;
}
}
Как упоминалось ранее, когда дело доходит до стека, функция push добавляет новый элемент в верхнюю часть стека, а функция pop удаляет и возвращает самый верхний элемент. Именно это и будут делать эти новые методы, которые мы добавили; push создает новый узел с некоторыми данными и перемещает указатель этого нового узла так, чтобы он указывал на верх, таким образом делая «исходный» верхний вторым элементом в стеке. . Затем он обновляет элемент top только что созданным новым узлом. После этого в функции pop мы хотим иметь возможность возвращать «исходные» данные top, поэтому сначала мы просто собираемся получить доступ к этим данным с помощью top.data. Затем мы собираемся обновить самый верхний элемент узлом после «исходной» вершины, а затем вернуть данные новой вершины.
И вуаля! Теперь вы можете создавать свои собственные стеки и очереди.
Спасибо за внимание! Если вы нашли это полезным, вы можете предпринять следующие шаги:
- Пошлите сюда несколько хлопков!
- Следуйте за мной на Medium или свяжитесь со мной в LinkedIn, чтобы быть в курсе, когда выйдет следующая статья из этой серии!
- Попрактикуйтесь, решая еще несколько задач со стеками и очередями!
- Читайте следующую статью из этой серии о хеш-таблицах!
