Стек с использованием связанного списка на Java

Реализация стека с использованием связанного списка

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

Node.java

LinkList.java

LinkListStack.java

LinkListStackDemo.java

3 ответа

Сложность времени

Временная сложность операций push и pop должна быть $ O (1) $, и это тоже в вашем случае. Неважно, сколько элементов у вас есть, эти операции должны занимать постоянное время. (UPDATE: вы отредактировали исходное сообщение и сделали pop уничтожить весь стек. Это не нормально! операция pop в стеке должна вернуть последнее добавленное значение. Это $ O (1) $ time.)

Избегайте печати на stdout

Вместо методов display* , которые печатаются на stdout , было бы лучше переопределить toString . Таким образом, ваша реализация будет более проверкой.

Обобщить

Зачем ограничивать стек, связанный список, элементы узла до типа int ? Было бы тривиально легко переписать, чтобы он работал с любым типом T .

Вопрос помечен как «новичок», поэтому я понимаю, что вы еще не знакомы с дженериками. В этом случае см. этот официальный учебник . Или, возможно, вы также можете узнать из моей реализации примера ниже.

Добавьте метод isEmpty для стека

В вашем связанном списке есть метод isEmpty , но в стеке нет. Было бы неплохо иметь такой метод для стека.

Переосмысливание колеса

Когда вы изобретаете колесо (здесь, связанный список), хорошо имитировать то, что существует. Например, java.util.LinkedList использует имена методов addFirst и removeFirst вместо insertFirst и deleteFirst . Хорошо следовать примеру.

Модификаторы доступа и инкапсуляция

Как указывал @rolfl, Node не должен отображаться снаружи. Пользователям стека не нужно знать его внутреннюю работу.

Кроме того, члены Node должны быть закрытыми, а data и next могут быть final . Аналогично в стеке элемент связанного списка должен быть закрытым.

Нейминг

Во многих местах используются бедные имена.

• Вместо n для нового узла при замене первого элемента связанного списка newFirst будет более интуитивно понятным
• Вместо temp для старого первого элемента, удаленного из связанного списка, oldFirst будет более интуитивно понятным
• Вместо li для связанного списка в стеке, linkedList будет более интуитивно понятным

Рекомендуемая реализация

Единичные тесты

Ну, здесь есть несколько вещей.

Начиная с класса Node. Это не должно быть общедоступным. У вас нет причин раскрывать логику для чего-либо, кроме класса LinkedList. Обычно включает класс Node как статический внутренний класс структуры данных. Что-то вроде:

Сложность

Вы утверждаете, что сложности для push и pop – $ O (n) $, но это неверно. Обе эти операции влияют только на заголовок списка, например:

Как следствие, это операции $ O (1) $, и это то, что я ожидал бы для связанного списка insert-at-the-head.

LinkedList

Метод deleteFirst не должен возвращать значение узла. Это должно быть «зеркальное отражение» метода вставки. Метод insert вставляет int , а метод delete должен возвращать int .

LinkedListStack

pop() должны возвращать всплывающее значение. Твоя ничего не возвращает, она недействительна. Это не нормально.

Примечание. было указано, что ваш метод pop удаляет все значения из списка из-за while (!isEmpty()) . Этот цикл был добавлен после того, как я написал эту часть ответа (но прежде, чем я нажал ‘submit’). Предложение, приведенное выше, является точным для классического метода «pop», который удаляет первое значение из стека (а в Java и многих других языках тоже возвращается это значение).

Что у вас сейчас хуже, у вас есть метод под названием «поп», который ничего не делает, это «чистый» метод, он опустошает стек. В результате у вас вообще нет стека, у вас есть класс под названием Stack, который не является стеком. Кроме того, во многих случаях WOM (Write Only Memory) вы можете записывать значения в Stack, но никогда не читайте их.

Резюме

Ваш отступ отключен. Я предполагаю, что это связано с тем, что вы не знакомы с системой уценки Code Review. Вы должны вставить свой код в поле редактирования, затем выбрать его все, а затем нажать ctrl – k .

Почему вы пишете

, потому что вы его написали, pop() будет вытеснять все элементы из стека, а не один. Или я ошибаюсь?

Javist

Свежие записи

Связанный список основан стек реализация

В компьютерной науке, стек временного абстрактных типов данных и их структуры, основанной на принципе Последний In First Out (LIFO). Стеки очень широко и широко используется в современных компьютерных системах, и, как правило, осуществляется через сочетание аппаратных и программных функций.

Следующий код показывает, как реализовать стек с помощью связанных списков:

// CONSTRUCTION: with no initializer

// void push( x ) –> Insert x

// void pop( ) –> Remove most recently inserted item

// Object top( ) –> Return most recently inserted item

// Object topAndPop( ) –> Return and remove most recent item

// boolean isEmpty( ) –> Return true if empty; else false

// void makeEmpty( ) –> Remove all items

// top, pop, or topAndPop on empty stack

* List-based implementation of the stack.

* @author Mark Allen Weiss

public class ListStack implements Stack <

* Construct the stack.

* Test if the stack is logically empty.

* @return true if empty, false otherwise.

public boolean isEmpty ( ) <

return topOfStack == null ;

* Make the stack logically empty.

* Insert a new item into the stack.

* @param x the item to insert.

public void push ( Object x ) <

topOfStack = new ListNode ( x, topOfStack ) ;

* Remove the most recently inserted item from the stack.

* @throws UnderflowException if the stack is empty.

throw new UnderflowException ( “ListStack pop” ) ;

* Get the most recently inserted item in the stack.

* Does not alter the stack.

* @return the most recently inserted item in the stack.

* @throws UnderflowException if the stack is empty.

public Object top ( ) <

throw new UnderflowException ( “ListStack top” ) ;

* Return and remove the most recently inserted item

* @return the most recently inserted item in the stack.

* @throws UnderflowException if the stack is empty.

public Object topAndPop ( ) <

throw new UnderflowException ( “ListStack topAndPop” ) ;

Object topItem = topOfStack.element;

private ListNode topOfStack;

* Exception class for access in empty containers

* such as stacks, queues, and priority queues.

* @author Mark Allen Weiss

public class UnderflowException extends RuntimeException <

* Construct this exception object.

* @param message the error message.

public UnderflowException ( String message ) <

// void push( x ) –> Insert x

// void pop( ) –> Remove most recently inserted item

// Object top( ) –> Return most recently inserted item

// Object topAndPop( ) –> Return and remove most recent item

// boolean isEmpty( ) –> Return true if empty; else false

// void makeEmpty( ) –> Remove all items

// top, pop, or topAndPop on empty stack

* Protocol for stacks.

* @author Mark Allen Weiss

public interface Stack <

* Insert a new item into the stack.

* @param x the item to insert.

void push ( Object x ) ;

* Remove the most recently inserted item from the stack.

* @exception UnderflowException if the stack is empty.

* Get the most recently inserted item in the stack.

* Does not alter the stack.

* @return the most recently inserted item in the stack.

* @exception UnderflowException if the stack is empty.

* Return and remove the most recently inserted item

* @return the most recently inserted item in the stack.

* @exception UnderflowException if the stack is empty.

* Test if the stack is logically empty.

* @return true if empty, false otherwise.

* Make the stack logically empty.

// Basic node stored in a linked list

// Note that this class is not accessible outside

// of package weiss.nonstandard

public ListNode ( Object theElement ) <

public ListNode ( Object theElement, ListNode n ) <

Стек с использованием связанного списка на Java

Сегодня будем говорить об алгоритмах и структурах данных для реализации фундаментальных типов данных — мультимножества, очереди и стека. Может быть, вы немного знакомы с ними, но сегодня мы рассмотрим их подробно. Начнем со стека.

Идея в том, что во многих приложениях есть множества объектов для обработки. Это простые операции. Нужно добавлять элементы к коллекции, удалять элементы из неё, проходить по всем объектам, проводя над ними какие-либо операции, проверять, не пуста ли она. Намерения вполне понятные. Ключевой момент: когда нужно удалить элемент коллекции, какой именно удалять? Есть две классические структуры данных: стек и очередь. Они различаются выбором элемента для удаления. В стеке мы удаляем последний добавленный элемент.

Термины, которые мы используем: push для вставки элемента и pop для удаления последнего добавленного элемента. Подход называется LIFO (last in first out)— последний зашел – первый вышел. Для очереди мы берем добавленный раньше всех элемент. Чтобы не путаться в операциях, добавление элемента назовем NQ, а удаление — DQ. Этот способ называется FIFO (first in first out) — первый пришел – первый вышел. Посмотрим, как всё это реализовать.

Подтемой сегодня будет модульное программирование. Идея в том, что бы полностью разделять интерфейс и реализацию. При наличии четко определенной структуры и типов данных, как стек или очередь, мы полностью скрываем детали реализации от клиента. Клиент может выбрать различные реализации но код должен использовать только базовые операции.

С другой стороны, реализация не может знать детально потребности клиента. Код должен лишь реализовать операции. В этом случае, многие клиенты могут использовать одну реализацию. Мы можем создавать модульные, многократно используемые библиотеки алгоритмов и структур данных, из которых строятся более сложные алгоритмы и структуры данных. Это позволяет при необходимости сосредоточиться на быстродействии. Это модульный стиль программирования, который возможен благодаря объектно-ориентированным языкам, как Java. Будем придерживаться этого стиля. Начнем разговор со стеков.

Давайте тщательно разберем реализацию стека прямо сейчас. Для разминки предположим, что у нас есть коллекция строк. Они могут быть короткими или длинными. Мы хотим иметь возможность сохранять коллекцию строк, удалять и выводить последние добавленные строки, проверять, пуста ли она.

Так вот наше API, конструктор для создания пустого стека. Для вставки используется метод push, аргумент которого — строка, для удаления — метод pop, который выводит строку, добавленную последней. Метод isEmpty возвращает логическое значение. В некоторых приложениях, мы будет включать метод Size.

Как обычно, сначала напишем клиент, а затем разберем реализацию.

Наш клиент читает строки из стандартного ввода и использует команду pop, которую обозначим дефисом. Итак, этот клиент читает строки из стандартного ввода. Если строка равна знаку дефис, берем строку сверху стека и печатаем её. В противном случае, если строка не равна дефису, она добавляется наверх стека.

Есть файл tobe.text, клиент будет вставлять строки “to be or not to” в стек. Затем, когда дело доходит до дефиса, он выдаст последний добавленный элемент, в данном случае это “to”. Затем добавит “be” наверх стека и выдаст верхний элемент стека, то есть “be” и элемент, добавленный последним. Т.е. “Be” уйдет, “to” тоже, за ними идет “not” и так далее. Этот простой тестовый клиент можно использовать для проверки наших реализаций. Посмотрим код для реализации стека.

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

В реализации стека, когда мы делаем добавление (push), то вставляем новый узел в начало списка. Когда извлекаем элемент, то удаляем первый элемент списка. Это последний добавленный элемент. Посмотрим, как выглядит этот код. Используем внутренний класс Java. То есть будем манипулировать объектами “узел”, каждый из которых состоит из строки и ссылки на другой объект “узел”. Таким образом операция pop для списка реализуется очень просто. Во-первых нужно вывести первый элемент в списке, поэтому сохраняем его. Возьмем first.item и сохраним в переменную item.

Чтобы избавиться от первого узла, просто сдвигаем указатель первого элемента списка на следующий за ним элемент. Теперь первый элемент готов быть удаленным сборщиком мусора. Остается только вывести элемент, который мы сохранили. Это была операция pop. Что насчет push операции?

Мы хотим добавить новый элемент в начало списка. Первое: сохраняем указатель на начало списка. Это oldfirst = first. Затем создаем новый узел, который поместим в начало списка. Это: first = new Node. Затем присваиваем ему значения. В поле item — строку, которую хотим вставить в начало списка В этом случае “not”. И в поле next вставим указатель oldfirst, который теперь второй элемент списка. Так после этой операции, “first” указывает на начало списка. Элементы списка расположены в обратном порядке относительно их добавления в стек.

Эти 4 строки реализуют стековую операцию push(). А вот полная реализация на базе связного списка всего кода для реализации стека строк в Java. В этом классе конструктор ничего не делает, поэтому его нет.

Вот внутренний класс, который мы используем для элементов списка. Делаем его внутренним, чтобы ссылаться напрямую на него. И тогда единственной переменной стека является ссылка на первый узел в списке, и она на старте равна null. Тогда isEmpty просто проверка first на null. Push — это четыре строки кода, которые я уже показывал, pop — это 3 строки кода, которые были даны раньше. Это полный код односвязного списка, который является хорошей реализацией спускающегося списка для любого клиента.

Можно проанализировать алгоритм и предоставить информацию о его быстродействии клиентам. В этом случае видно, что каждая операция в худшем случае тратит постоянное время. Всего несколько инструкций для каждой из операций. Тут нет циклов. Это, очевидно, весьма неплохо.

Что насчет памяти?

Зависит от реализации и компьютера, здесь проанализирована типичная java реализация. Вы можете проверить её для различных сред выполнения, так что она показательна. Для каждого объекта в Java 16 байт идет на заголовок. Дополнительно 8 байт, потому что это внутренний класс. В классе Node есть 2 встроенные ссылки: одна на строку, другая на узел, каждая из них — 8 байт. Итак 40 байт для записи стека.

Если у нас есть стек размером N, он займет 40 N байт. Ещё немного занимает first элемент, это около N для целого стека. При большом N значение 40*N точно оценивает требуемую память. Оно не учитывает место для самих строк внутри клиента. Но с этим мы можем правильно оценить затраты ресурсов реализацией для различных клиентских программ.

Время постоянное, но есть и более быстрые реализации стека. Если стек используется во внутренних циклах неких алгоритмов, то важно поискать более быстрые реализации. Другой способ реализации стека — это использование массива для хранения элементов. Посмотрим на него.

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

При использовании массива, мы просто держим N элементов стека в массиве. И позиция массива c индексом N — это место расположения вершины стека, куда должен быть помещен следующий элемент. Таким образом, для push(), мы просто добавляем новый элемент в s[N]. А для pop() удаляем элемент s[N-1] и уменьшаем N.

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

Итак, вот полная реализация стека, использующая массив для представления структуры стека. Здесь переменная экземпляра, представляющая собой массив строк. А также наша переменная N, которая представляет собой как размер стека, так и индекс следующей свободной позиции.

У этого класса есть конструктор. Он создает массив. Здесь мы немного сжульничали для упрощения, займемся этим позже. Обман состоит в требовании указывать размер стека. Это нормально для некоторых приложений, но слишком обременительно для многих других.

Клиент не знает размеров стека. Ему может потребоваться множество стеков одновременно. Они могут достичь максимальной вместимости в разное время. Нужно избавиться от такого требования, и мы это сделаем. Но, код становится почти тривиальным, если мы явно используем вместимость. Для проверки на пустоту мы проверяем, равен ли N нулю.

Для размещения элемента используем N как индекс массива, помещаем туда элемент и увеличиваем N. Вот это, N++, используется во многих языках программирования как сокращение для “используй индекс и увеличь его на 1”. А для pop() мы уменьшаем индекс, затем используем его для возврата элемента массива. Таким образом, каждая из операций является однострочной. Это прекрасная реализация для некоторых клиентов. Это реализация стека с помощью массива, но она ломает API, требуя от клиента указания вместимости стека.

Итак, что с этим делать? Есть пара вещей, которые мы не рассмотрели. Мы не написали кода для выброса исключения, если клиент пытается извлечь элемент из пустого стека. Вероятно, следует это сделать. А что случится, если клиент поместит слишком много элементов? Поговорим об изменении размера, которое позволяет избежать переполнения.

Вопрос ещё в том, могут ли клиенты вставлять null элементы в структуру данных. В данном случае мы это позволяем. Но нужно позаботиться о проблеме лойтеринга, когда в массиве хранится ссылка на объект, который на самом деле не используется. Когда мы удаляем значение стека, то в массиве остается ссылка на него. Мы знаем, что больше не используем его, а Java нет.

Для более эффективного использования памяти нужно устанавливать удаленные элементы в Null. Так, чтобы не оставалось ссылок на старые элементы, и сборщик мусора мог освободить память, так как на неё больше никто не ссылается. Это деталь, но для максимально эффективного использования памяти необходимо это учесть.

Автор этого материала – я – Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML – то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

статьи IT, алгоритмы, стек, java, теория программирования

Стек Java: реализация, методы

Класс Java Stack, java.util.Stack, представляет собой классическую структуру данных стека. Вы можете поместить элементы на вершину стека и снова извлечь их, что означает чтение и удаление элементов с его вершины.

Класс фактически реализует интерфейс List, но вы редко используете его в качестве списка — за исключением, когда нужно проверить все элементы, хранящиеся в данный момент в стеке.

Обратите внимание, что класс Stack является подклассом Vector, более старого класса Java, который синхронизируется. Эта синхронизация добавляет небольшую нагрузку на вызовы ко всем методам стека. Кроме того, класс Vector использует несколько более старых (не рекомендуемых) частей Java, таких как Enumeration, который заменяется интерфейсом Iterator.Если вы хотите избежать этих проблем, вы можете использовать Deque вместо стека.

Основы

Стек — это структура данных, в которой вы добавляете элементы к «вершине» стека, а также снова удаляете элементы сверху. Это также называется принципом «первым пришел — первым вышел (LIFO)». В отличие от этого, Queue использует принцип «первым пришел — первым обслужен (FIFO)», когда элементы добавляются в конец очереди и удаляются из начала очереди.

Как создать стек в Java?

Для использования стека необходимо сначала создать экземпляр класса Stack:

Как создать с универсальным типом

Можно задать универсальный тип стека, указав тип объектов, которые может содержать экземпляр стека. Тип стека указывается при объявлении переменной стека. Вот пример:

Стек, созданный выше, может содержать только экземпляры String.

Рекомендуется использовать универсальный тип в ваших экземплярах стека, поскольку он упрощает код (не требуется преобразование при доступе к объектам в стеке) и снижает риск того, что вы поместите объект неправильного типа в стек.

Толкающий элемент

Получив экземпляр Stack, вы можете поместить элементы в верхнюю часть стека. Они должны быть объектами. Таким образом, вы фактически толкаете объекты в стек.

Этот пример помещает строку с текстом 1 в стек. Строка 1 затем сохраняется в верхней части стека.

Вытолкнутый элемент

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

Как только элемент извлечен из стека, элемент больше не присутствует в стеке.

Как увидеть верхний элемент

Класс имеет метод peek (), который позволяет увидеть верхний элемент в стеке, не удаляя его:

После запуска этого примера переменная topElement будет содержать объект String 1, который был помещен в стек непосредственно перед вызовом peek(). Объект String все еще присутствует в стеке после вызова peek().

Поиск

Вы можете искать объект, чтобы получить его индекс, используйте метод search(). Метод вызывается для каждого объекта, чтобы определить, присутствует ли искомый объект в стеке. Индекс, который вы получаете, является индексом с вершины стека, то есть верхний элемент имеет индекс 1.

Перебор элементов

Можно выполнить итерацию элементов, получив итератор из стека с помощью метода iterator().

Использование потока

Также возможно обрабатывать элементы через API Stream. Вы делаете это, сначала получая его из стека с помощью метода stream().

Как только вы получили поток, можете обрабатывать элементы в потоке.

Обратите внимание, что этот пример использует Lambda в качестве параметра для метода Stream.forEach(). Лямбда просто распечатывает элемент в System.out.

Обратный список

Вы можете использовать стек для реверсирования списка. Вы делать это, перемещая все элементы из списка в стек, начиная с элемента с индексом 0, затем 1 и т. д. Каждый элемент удаляется из списка, а затем помещается в стек. После того, как все элементы находятся в стеке, вы вытаскиваете элементы один за другим и добавляете их обратно в пустой список.

Стек с использованием связанного списка на Java

Для оптимальной работы приложения JVM делит память на область стека (stack) и область кучи (heap). Всякий раз, когда мы объявляем новые переменные, создаем объекты или вызываем новый метод, JVM выделяет память для этих операций в стеке или в куче

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

Стек работает по схеме LIFO (последним вошел, первым вышел). Всякий раз, когда вызывается новый метод, содержащий примитивные значения или ссылки на объекты, то на вершине стека под них выделяется блок памяти

Когда метод завершает выполнение, блок памяти, отведенный для его нужд, очищается, и пространство становится доступным для следующего метода

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

Эти объекты имеют глобальный доступ и могут быть получены из любого места программы

Рассмотрим выполнение кода по шагам:

1. До начала выполнения метода main(), в стеке будет выделено пространство для хранения примитивов и ссылок этого метода:
   • примитивное значение idтипа intбудет храниться непосредственно в стеке
   • ссылочная переменная pName типа String будет создана в стеке, но сама строка будет храниться в области, называемой String Pool (является частью Кучи)
   • ссылочная переменная pтипа Personбудет также создана в памяти стека, но будет указывать на объект, расположенный в куче

Стек с использованием связанного списка на Java

Небольшой дисклеймер. Эта статья рассчитана на повторение и/или изучение основных структур данных для собеседования на java developer позицию.
Ссылка на оригинал статьи от ex-Facebook и ex-Microsoft разработчика Fahim ul Haq

Никлаус Вирт, швейцарский ученый, в 1976 году написал книгу под названием «Алгоритмы + структуры данных = программы».

Спустя 40 с лишним лет это уравнение остается в силе. Вот почему кандидаты на разработку программного обеспечения должны продемонстрировать свое понимание структур данных вместе со своими приложениями.

Почти все проблемы требуют глубокого понимания структур данных и того же требуют от разработчика. И в целом неважно, кандидат закончил только что университет или имеет 10-ти летний опыт.

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

Изучать структуры данных очень важно, даже если вы просто пытаетесь улучшить свой текущий код. Давайте начнем с понимания основ.

Структура данных, что это?

Проще говоря, структура данных – это контейнер, в котором хранятся данные в определенной компоновке. Такая «компоновка» позволяет структуре данных быть эффективной в одних операциях и неэффективной в других. Ваша цель – понять структуры данных, чтобы вы могли выбрать структуру, наиболее оптимальную для рассматриваемой проблемы.

Зачем нам знать структуры данных перед собеседованием?

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

Независимо от того, какую проблему вы решаете, вам так или иначе приходится иметь дело с данными – будь то зарплата сотрудника, цены на акции, список покупок или даже простой телефонный справочник.

Исходя из разных сценариев, данные должны храниться в определенном формате. У нас есть несколько структур данных, которые покрывают нашу потребность хранить данные в разных форматах.

Обычно используемые структуры данных

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

1. Массивы
2. Стеки
3. Очереди
4. Связанные списки
5. Деревья
6. Графы/диаграммы
7. Tries / попытки (это те же деревья, но в целях изучения лучше сделать на них отдельный акцент).
8. Хэш таблицы

Массивы

Массив – это самая простая и наиболее широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов. Вот изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

Каждому элементу данных присваивается положительное числовое значение, называемое индексом,которое соответствует позиции этого элемента в массиве. Большинство языков определяют начальный индекс массива как 0.

Ниже приведены два типа массивов:

• Одномерные массивы (как показано выше)
• Многомерные массивы (массивы массивов)

Основные операции с массивами

• Insert-вставка элемента по заданному индексу
• Get — возвращает элемент по указанному индексу
• Delete-удаление элемента с заданным индексом
• Size— получить общее количество элементов в массиве

Часто задаваемые вопросы на интервью по Массивам

• Найти второй минимальный элемент массива
• Первые неповторяющиеся целые числа в массиве
• Объединить два отсортированных массива
• Переставить положительные и отрицательные значения в массивах

Стеки/стопки

Мы все знакомы с известным вариантом отмены (Undo – ctrl+z прим. автора перевода) , который присутствует почти в каждом приложении. Когда-нибудь задумывались, как это работает? Идея: вы сохраняете предыдущие состояния вашей работы (которые ограничены определенным числом) в памяти в таком порядке, что последнее появляется первым. Это не может быть сделано только с помощью массивов. То есть это реализуется с помощью стека.

Реальным примером стопки (стека) может быть стопка книг, расположенных в вертикальном порядке. Чтобы получить книгу, которая находится где-то посередине, вам нужно будет удалить все книги, размещенные поверх нее. Вот как работает метод LIFO (Last In First Out).

Вот изображение стека, содержащего три элемента данных (1, 2 и 3), где 3 находится вверху и будет удален первым:

Основные операции стека:

• Push-вставка элемента сверху
• Pop — возвращает верхний элемент, после удаления из стека
• isEmpty-возвращает true, если стек пуст
• Top-возвращает верхний элемент без удаления из стека

Часто задаваемые вопросы интервью стека

• Оценить постфиксного выражения с помощью стека
• Сортировка значений в стеке
• Проверка на скобки в выражении

Очередь

Подобно стеку, очередь-это еще одна линейная структура данных, которая хранит элемент последовательным образом. Единственное существенное различие между стеком и очередью заключается в том, что вместо использования метода LIFO очередь реализует метод FIFO, который является коротким для First in First Out.

Идеальный пример очереди в реальной жизни: очередь людей, ожидающих в билетной кассе. Если придет новый человек, он присоединится к очереди с конца, а не с самого начала — и человек, стоящий впереди, первым получит билет и, следовательно, покинет линию.

Вот изображение из очереди с четырьмя элементами данных (1, 2, 3 и 4), где 1 находится на самом верху и будет удален первый:

• Enqueue () – вставляет элемент в конец очереди
• Dequeue () – удаляет элемент из начала очереди
• isEmpty () – возвращает true, если очередь пуста
• Top () – возвращает первый элемент очереди

• Реализовать стек с помощью очереди
• Обратного первые k элементов очереди
• Генерировать двоичные числа от 1 до n, используя очередь

Связанные списки

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

Связанный список похож на цепочку узлов, где каждый узел содержит информацию, например данные, и указатель на следующий узел в цепочке. Есть указатель head, который указывает на первый элемент связанного списка, и если список пуст, то он просто указывает на null или nothing.

Связные списки используются для реализации файловых систем, хэш-таблиц и списков смежности.

Вот визуальное представление внутренней структуры связанного списка:

Ниже перечислены типы связанных списков:

• Однонаправленный Список (Однонаправленный)
• Двунаправленный список (двунаправленный)

Основные операции связанного списка:

• InsertAtEnd-вставляет данный элемент в конец связанного списка
• InsertAtHead-вставка данного элемента в начало / начало связанного списка
• Delete-удаление данного элемента из связанного списка
• DeleteAtHead-удаление первого элемента связанного списка
• Search-возвращает данный элемент из связанного списка
• isEmpty-возвращает true, если связанный список пусто

Часто задаваемые вопросы интервью по связанному списку

• Реверс связанного списка
• Обнаружение цикла в связанном списке
• Возвращает N-й узел из конца в связанном списке
• Удаление дубликатов из связанного списка

Graphs

Граф-это набор узлов, которые соединены друг с другом в виде сети. Узлы также называются вершинами. Пара (x, y) называется ребром, что указывает на то, что вершина x связана с вершиной y. Ребро может содержать вес / стоимость, показывая, сколько затрат требуется для прохождения от вершины x до y.

• неориентированный граф
• ориентированный граф

В языке программирования графики могут быть представлены в двух формах:

• Массив смежности
• Список Смежности

Общие алгоритмы обхода графов:

• Поиск По Ширине
• Поиск по глубине

Часто задаваемые вопросы интервью Graph

• Реализовать поиск по ширине и глубине
• Проверьте, является ли график деревом или нет
• Количество ребер в графе
• Найти кратчайший путь между двумя вершинами

Деревья

Дерево-это иерархическая структура данных, состоящая из вершин (узлов) и ребер, соединяющих их. Деревья похожи на графики, но ключевой момент, который отличает дерево от графика, заключается в том, что цикл не может существовать в дереве.

Деревья широко используются в искусственном интеллекте и сложных алгоритмах для обеспечения эффективного механизма хранения для решения проблем.

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

Ниже перечислены типы деревьев:

• N-ary дерево
• сбалансированное дерево
• бинарное дерево
• Двоичное Дерево Поиска
• Дерево AVL
• Красное Черное Дерево
• 2-3 дерево

Часто задаваемые вопросы интервью дерево

• Найти высоту двоичного дерева
• K-е максимальное значение в двоичном дереве поиска
• Идентифицировать узлы на расстоянии ” k” от корня
• Поискать предков данного узла в двоичном дереве

Попытка или Префиксные деревья

Trie, который также известен как ”префиксные деревья”, является древовидной структурой данных, которая оказывается довольно эффективной для решения проблем, связанных со строками. Он обеспечивает быстрый поиск и в основном используется для поиска слов в словаре, предоставления автоматических предложений в поисковой системе и даже для IP-маршрутизации.

Вот иллюстрация того, как три слова “top”, “thus” и “their” хранятся в Trie:

Слова хранятся сверху вниз, где зеленые цветные узлы “p”, “s” и “r” указывают конец “top”, “thus” и “their” соответственно.

Часто задаваемые вопросы интервью:

• Количество общее количество слов в Trie
• Напечатать все слова, хранящиеся в боре
• Элементов сортировка массива с помощью дерева
• Форма слова из словаря с помощью Trie
• Создание словаря T9

Хэш Таблицы

Хэширование – это процесс, используемый для уникальной идентификации объектов и хранения каждого объекта в некотором заранее вычисленном уникальном индексе, называемом его “ключом”.”Итак, объект хранится в виде пары” ключ-значение“, а коллекция таких элементов называется “словарем”.- Каждый объект можно обыскать с помощью этого ключа. Существуют различные структуры данных, основанные на хэшировании, но наиболее часто используемой структурой данных является хэш-таблица.

Хэш-таблицы обычно реализуются с использованием массивов.

Производительность структуры данных хэширования зависит от этих трех факторов:

• функция хеширования
• Размер хэш-таблицы
• Способ Управления Столкновением

Вот иллюстрация того, как хэш отображается в массиве. Индекс этого массива вычисляется с помощью хэш-функции.

Часто задаваемые вопросы интервью хэширования

• Найти симметричные пары в массиве
• Проследить полный путь путешествия
• Найти, является ли массив подмножеством другого массива
• Проверьте, являются ли заданные массивы непересекающимися

Выше изложены 8 структур данных, которые помогут вам в прохождении собеседования