Мы были подвержены воздействию нескольких структур данных, включая массивы, связанные списки, хэш -таблицы и красные и черные деревья (бинарные деревья запросов). Сегодня давайте посмотрим на другую структуру данных: стек.
Что такое стек? Давайте сначала посмотрим на пример: стек эквивалентен очень узкой деревянной бочке. Когда мы вкладываем вещи в деревянную ствол и вынимаем вещи, мы обнаружим, что то, что мы положили внизу в начале, и первое, что мы вывели, было той, что мы просто вложили. Поэтому стек - это такой контейнер, который сначала и вышел (сначала в первую очередь, или позже и сначала). У него есть только один рот, поместите элементы в этот рот, а также выводит элементы в этот рот. Тогда давайте изучим стек в JDK в следующий раз.
1. Основное введение и использование вектора и стека
Давайте сначала посмотрим на определение JDK:
общедоступный стек класса <e> расширяет вектор <e> {Из вышесказанного мы видим, что стек унаследован от вектора, поэтому мы также должны иметь определенное понимание вектора.
Вектор: безопасные динамические массивы потока
Стек: унаследование вектора, защищенный потоком стек, реализованный на основе динамических массивов;
1. Особенности вектора и стека:
Vector и Arraylist в основном одинаковы. Разница в том, что вектор безопасен для потока и добавит синхронизированное ключевое слово перед возможными методами безопасных потоков;
Вектор: быстрая случайная скорость доступа, плохая вставка и производительность удаления (характеристики массива); поддерживает нулевые элементы; есть заказ; Элементы могут быть повторены; потокобезопасность;
Stack: после того, как в первую очередь реализует некоторые базовые методы работы стека (на самом деле, это не только после, прежде всего, потому что унаследован от вектора, может быть много операций, и в некотором смысле это не стек);
2. Структура вектора и стека:
Векторный класс
Это в основном то же самое, что и ArrayList, а остальные основные различия следующие:
1. Вектор защищен потоком
2. Рост ArrayList не соответствует росту вектора
Другие, если методы строительства противоречивы, вектор может инициализировать способность к способностям с помощью метода строительства, и существуют другие методы, такие как метод индекса. Вектор поддерживает поиск и поиск в указанном месте; Кроме того, Vector также имеет некоторые избыточные методы с дублирующими функциями, такими как метод Addelement и Setelementat. Причина этого связана с историческими причинами. Например, метод добавления остается раньше. Когда была введена фреймворк сбора, Vector присоединился к семейству коллекций и изменилась на реализацию интерфейса списка. Некоторые методы, определенные в интерфейсе списка, должны быть реализованы. Однако, по причинам совместимости, старые методы не могут быть удалены, поэтому появились некоторые старые методы с избыточностью. Теперь он был заменен ArrayList и в основном используется редко, так что просто поймите.
Стекк класс
Основная работа стека реализована. Метод заключается в следующем:
public Stack ();
Создать пустой стек
общественный синхронизированный e peek ();
Возвращает значение в верхней части стека;
Public E Push (E Item);
Операция стека;
общественный синхронизированный e pop ();
Операция вне стека;
Public Boolean Empty ();
Определите, является ли стек пустой;
Общественный синхронизированный поиск int (объект O);
Возвращает положение объекта в стеке;
Для приведенного выше стека мы в основном будем использовать только приведенный выше метод. Хотя он наследует вектор и имеет много методов, он в основном не будет использоваться, но он просто рассматривается как стек.
3. Основное использование
Некоторые методы в векторе используются следующим образом. Кроме того, метод перемещения вектора такой же, как и у ArrayList. Вы можете использовать Foreach, итератор и для прохождения петли;
Import java.util.arrays; импорт java.util.iterator; import java.util.list; import java.util.listiterator; import java.util.vector; Общедоступный тест класса {public static void main (string [] args) {vector <Integer> vector = new Vector <Inceger> (); for (int i = 0; i <10; i ++) {vector.add (i); } // print System.out.println (ecector.toString ()); // size () system.out.println (ector.size ()); // содержит System.out.println (ector.contains (2)); // итератор итератор <Integer> iterator = vector.iterator (); while (iterator.hasnext ()) {System.out.print (iterator.next () + ""); } // toarray object [] objarr = ecector.toarray (); System.out.println ("/nobjarr:" + arrays.aslist (objarr)); Integer [] intarr = ecector.toarray (new Integer [ector.size ()]); System.out.println ("intarr:" + arrays.aslist (intarr)); // добавить ecector.add (5); // Удалить Vector.Remove (5); System.out.println (Vector); // содержит System.out.println (ecector.containsall (arrays.aslist (5,6))); // addall vector.addall (arrays.aslist (555 666)); System.out.println (Vector); // removeall vector.removeall (arrays.aslist (555,666)); System.out.println (Vector); // addall Метод вектор. Addall (5, Arrays.aslist (666 666, 6)); System.out.println (Vector); // Получить метод System.out.println (ector.get (5)); // установить метод вектор .set (5, 55); System.out.println (Vector.get (5)); // Добавить метод Vector.Add (0, 555); System.out.println (Vector); // Удалить метод Vector.remove (0); System.out.println (Vector); // Indexof Method System.out.println (ecector.indexof (6)); // LastIndexof Method System.out.println (ecector.lastindexof (6)); // listicerator method listiceTerator <Integer> listiceTerator = vector.listiterator (); System.out.println (listicerator.hasprevious ()); // listiceTerator (index) method listiceTerator <Integer> ilistiterator = ector.listiterator (5); System.out.println (ilistiterator.previous ()); // Sublist Method System.out.println (Vector.sublist (5, 7)); // clear vector.clear (); System.out.println (Vector); }}Некоторые методы в стеке используются следующим образом. Поскольку стек наследует вектор, стек также может использовать методы, которые может использовать вектор. В следующем перечислены некоторые примеры уникальных методов Stack. Это очень просто, которые являются некоторыми основными операциями стека. В дополнение к нескольким методам перемещения вектора, Stack также имеет свои уникальные методы обхода (используя пустой метод и метод POP для достижения обхода сверху до нижней части стека):
Import java.util.stack; открытый тест класса {public static void main (string [] args) {Stack <Integer> Stack = new Stack <Integer> (); for (int i = 0; i <10; i ++) {Stack.add (i); } System.out.println (Stack); System.out.println (stack.peek ()); Stack.push (555); System.out.println (стек); System.out.println (stack.pop ()); System.out.println (стек); System.out.println (Stack.empty ()); System.out.println (Stack.search (6)); System.out.println ("stack traversal:"); while (! Stack.empty ()) {System.out.print (stack.pop () + ""); }}}Подраздел:
Вектор безопасен для потока, но имеет плохую производительность. Как правило, ArrayList используется, если нет особых требований;
Если вы планируете использовать стек в качестве стека, вы должны честно и строго следить за несколькими операциями стека. В противном случае было бы значимо использовать стек, и было бы лучше использовать вектор;
2. Структура Vector & Stacke и основное хранилище
Публичный вектор класса <e> расширяет AbstractList <e> List <e>, Randomaccess, Clonable, Java.io.serializable
Вектор - это класс реализации списка. Фактически, Vector также является контейнером списка на основе реализации массива. Его функции и код реализации в основном такие же, как ArrayList. Так что же отличается? Одним из них является то, что когда массив расширен, вектор составляет *2, а массив - *1,5+1; Другое состоит в том, что вектор безопасен для потока, а Arraylist-нет. Подход вектора, безопасный для потока, состоит в том, чтобы добавить синхронизированное ключевое слово в каждый метод, чтобы обеспечить его. Но здесь вектор больше не является официально (признан всеми) и не рекомендуется. Официально это потому, что его метод безопасности резьбы заключается в блокировке всего метода, что приводит к низкой эффективности. Так есть ли лучшее решение? На самом деле, нельзя сказать, что есть, но есть один из них, collections.synchronizedlist ()
Поскольку стек унаследован и основан на векторе, давайте посмотрим на некоторые определения и исходные коды метода вектора:
// базовый уровень использует массив для хранения защищенных данных объекта [] elementData; // количество элементов, защищенных int elementCount; // Настройка расширения контейнера и размера увеличения, защищенного int емкостью; Общественный вектор (int initialCapacity, int емкость) {super (); // Выход по границам Проверка IF (initialCapacity <0) бросить новую allosalargumentException («Незаконная емкость:» + initialCapacity); // Инициализировать массив this.ElementData = новый объект [initialCapacity]; this.capacityIncrement = емкость; } // Используйте метод блокировки синхронизированного ключевого слова, чтобы гарантировать, что только один поток может манипулировать методом одновременно с публичным синхронизированным логическим добавлением (e e) {modcount ++; // Проверка увеличения EncureCapacityHelper (elementCount + 1); elementData [elementCount ++] = E; вернуть истину; } private void EnsureCapacityHelper (int mincapacity) {// Текущее число элементов int oldCapacity = elementData .length; // необходимо ли расширить емкость, если (mincapacity> oldcapacity) {Object [] oldData = elementData; // Если расширение контейнера настраивается, расширяйте емкость в соответствии с емкостью, в противном случае расширяйте емкость в два раза (*2) int newcapacity = (емкость,> 0)? (OldCapacity + емкость): (OldCapacity * 2); if (newcapacity <mincapacity) {newcapacity = mincapacity; } // массив Copy elementData = arrays.copyof (elementdata, newcapacity); }}Вектор просто вижу это. Если другой метод стека не называется, он не будет проанализирован. Если вы не понимаете, вы можете проверить анализ исходного кода ArrayList.
3. Анализ основных методов
1. Peek () - Получите объект в верхней части стека
/ ** * Получить объект в верхней части стека, но не удаляйте */ public synchronized e peek () {// текущее количество элементов контейнера int len = size (); // Если нет элемента, добавьте исключение непосредственно, если (len == 0) бросьте новый hymystackexception (); // Метод вызова элементата для извлечения последнего элемента массива (последний элемент находится в верхней части стека) returnatat (len - 1); } / *** Получить элемент в этой позиции в соответствии с индексом индекса, этот метод находится в векторе* / public ementat (int index) {// выйти из границ if (index> = elementCount) {бросить новый arrayIndexoutOfBoundSexception (index + "> =" + elementCount); } // Получить элемент return (e) elementData [index]; }2.pop () - выпейте стек (из стека), получите объект в верхней части стека и удалите объект из контейнера
/ *** Шмель стека, получить и удалить объект в верхней части стека*/ public synchronized e pop () {// Записать объект в верхней части стека e obj; // текущее количество элементов контейнера int len = size (); // Получить объект в верхней части стека obj через метод peek () obj = peek (); // Вызовите метод removeLement, чтобы удалить объект в верхней части стека RemoveElementat (Len - 1); // Вернуться к объекту в верхней части стека Вернуть OBJ; } / *** Удалить элемент в соответствии с индексом индекса* / public void void lementElementat (int index) {modcount ++; // выходить из границ if (index> = elementCount) {бросить новый arrayIndexoutOfBoundSexception (index + "> =" + elementCount); } else if (index <0) {бросить новый arrayIndexoutofboundsexception (index); } // Рассчитайте количество элементов массива, которые будут перемещены int j = elementCount - index - 1; if (j> 0) {// переместить массив, удалите один в середине, поэтому перемещайте последующий элемент вперед (движущийся сюда непосредственно перезаписать элемент позиции индекса, который эквивалентен удалению). Arraycopy (ElementData, Index + 1, ElementData, Index, J); } // минус 1 elementCount--; // Установить последний элемент контейнера на пустой (потому что элемент был удален, а элементы, стоящие за индексом, были перемещены вперед, поэтому последний был бесполезен) elementData [elementCount] = null; / * Чтобы GC выполнил свою работу */}3.push (e item) - нажмите (в стек), добавьте объект в контейнер и верните его
/ ** * Добавить объект в контейнер и вернуть */ public E push (e item) {// call Addelement в addelement (item); // Возврат элемента возвращаемого элемента; } /*** Добавьте элемент в контейнер. Этот метод находится в Vector*/ public Synchronized void Addelement (e obj) {modcount ++; // Проверка увеличения EncureCapacityHelper (elementCount + 1); // Поместите объект в массив, количество элементов +1 elementData [elementCount ++] = obj; }4.Search (Object O) - Возвращает положение объекта в контейнере, верхняя часть стека составляет 1
/ ** * Возвращает позицию объекта в контейнере, верхняя часть стека составляет 1 */ public synchronized int search (объект o) {// Найти элемент из массива, из последнего появления int i = lastindexof (o); // Поскольку верхняя часть стека подсчитывает 1, вам нужно использовать Size () - i для расчета if (i> = 0) {return size () - i; } return -1; }5.empty () - это контейнер пуст
/ *** Проверьте, является ли контейнер пустым*/ public boolean empty () {return size () == 0; }Подраздел:
На этом этапе метод стека анализируется. Поскольку стек в конечном итоге основан на массивах, он все еще легко понять (потому что он основан на ArrayList).
Хотя исходный код стека в JDK был проанализирован, необходимо обсудить его здесь. Я не знаю, нашел ли я, что стек здесь очень странно.
(1) Почему стек реализован на основе массивов?
Мы все знаем характеристики массивов: они удобны для запросов на основе подписок (случайный доступ), но память фиксирована, а эффективность расширения емкости низкая. Легко придумать наиболее подходящую вещь для стека, чтобы использовать связанные списки.
(2) Почему стек наследует вектор?
Наследование означает, что стек наследует векторный метод, который заставляет стека чувствовать себя немного неуместным, как список, так и стек. Что должно быть разумным подходом, если вам нужно наследовать вектор: стек не наследует вектор, но имеет только ссылку на сам вектор, верна ли агрегация?
Единственное объяснение заключается в том, что стек был создан JDK1.0. В то время в контейнерах в JDK не было только векторов, таких как ArrayList, LinkedList и т. Д., И поскольку они уже имеют вектор и могут реализовать функции стека, затем сделать это. Полем Полем Поскольку это идеально для реализации стека со связанными списками, давайте попробуем:
импортировать java.util.linkedlist; открытый класс LinkedStack <e> {private LinkedList <e> Linked; public linkedStack () {this.linked = new LinkedList <e> (); } public e push (e item) {this.linked .addfirst (item); вернуть элемент; } public e pop () {if (this.linked.isempty ()) {return null; } вернуть this.linked.removefirst (); } public e peek () {if (this.linked.isempty ()) {return null; } вернуть this.linked.getFirst (); } public int search (e item) {int i = this.linked.indexof (item); вернуть i + 1; } public boolean empty () {return this.linked.isempty (); }}Здесь используется стек, реализованный LinkedList. Помните, что, как упомянуто в LinkedList, LinkedList реализует интерфейс Deque, чтобы его можно было использовать в качестве стека (сначала и выхода) и очередь (сначала и вне).
4. Разница между Vector & ArrayList
В интерфейсе списка есть три класса реализации, а именно ArrayList, Vector и LinkedList. Список используется для хранения нескольких элементов, может поддерживать порядок элементов и позволяет повторение элементов.
Соответствующие различия между тремя конкретными классами реализации следующие:
1. ArrayList является наиболее часто используемым классом реализации списка, внутренне реализованным через массивы, что позволяет быстрому случайному доступу к элементам. Недостаток массивов заключается в том, что между каждым элементом не может быть расположено. Когда размер массива не будет удовлетворен, емкость для хранения должна быть увеличена. Необходимо сказать, что данные уже скопируются в новое пространство для хранения. При вставке или удалении элементов из среднего положения ArrayList массив необходимо скопировать, перемещаться, а стоимость относительно высока. Следовательно, он подходит для случайных поисков и обходов, а не для вставки и удаления.
2. Вектор также реализуется с помощью массивов, разница заключается в том, что он поддерживает синхронизацию потоков, то есть в определенный момент, только один поток может написать вектор, чтобы избежать несоответствия, вызванного несколькими потоками, написанными одновременно, но для реализации синхронизации, так как он медленнее, чем доступ к ArrayList.
3. LinkedList использует связанную структуру списка для хранения данных, которая очень подходит для динамической вставки и удаления данных, а случайный доступ и скорость обхода относительно медленные. Кроме того, он также предоставляет методы, которые не определены в интерфейсе списка, которые специально используются для управления заголовком таблицы и хвостовых элементов и могут использоваться в качестве стеков, очередей и двунаправленных очередей.
5. Краткое понимание очереди очереди, двойной очередь deque
1. очередь
Новый интерфейс java.util.queue был добавлен в Java5 для поддержки общих операций в очереди. Этот интерфейс расширяет интерфейс java.util.collection.
Очередь общественного интерфейса <e> Extends Collection <e>
В дополнение к базовым операциям сбора, очереди предоставляют другие операции вставки, извлечения и проверки.
Каждый метод имеет две формы: одна бросает исключение (когда операция сбой), а другая возвращает специальное значение (нулевое или ложное, в зависимости от операции).
Очереди обычно (но не обязательно) сортируют отдельные элементы в FIFO (сначала сначала). Тем не менее, очередь приоритетов и очередь LIFO (или стека) являются исключениями. В первом сортируется элементы в соответствии с естественным порядком предоставленного компаратора или элементов, а последний сортирует элементы в LIFO (последнее в первую очередь).
В очереди FIFO все новые элементы вставлены в конце очереди, а элемент удаления удаляется из заголовка очереди.
При использовании очереди постарайтесь избежать методов Add () и удалить () сбора, но используйте предложение (), чтобы добавить элементы и использовать опрос () для получения и удаления элементов. Их преимущество состоит в том, что они могут определить, достигается ли успех путем возврата значения, и методы add () и remote () будут бросать исключения, когда они потерпят неудачу. Если вы хотите использовать переднюю часть без удаления элемента, используйте метод элемента () или peek ().
Метод предложения может вставить элемент, в противном случае он возвращает false. Это отличается от метода Collection.Add, который может не добавлять элементы, только бросая неконтролируемое исключение.
Методы rement () и опроса () удаляют и возвращают заголовок очереди. Какой элемент удален из очереди является функцией политики сортировки очередей, которая отличается от различных реализаций. Методы remote () и oppl () ведут себя по -разному только тогда, когда очередь пуст: метод remote () выбрасывает исключение, в то время как метод опроса () возвращает нулевое.
element () и peek () возвращайте, но не удаляйте заголовок очереди.
Реализации очередей, как правило, не допускают введения нулевых элементов, хотя некоторые реализации (такие как LinkedList) не запрещают введение нулевых. Даже в реализациях, которые разрешают NULL, NULL не должен быть вставлен в очередь, поскольку NULL также используется в качестве специального возврата для метода опроса, что указывает на то, что очередь не содержит элементов.
Стоит отметить, что класс LinkedList реализует интерфейс очереди, поэтому мы можем использовать LinkedList в качестве очереди.
импортировать java.util.queue; импортировать java.util.linkedlist; public class testqueue {public static void main (string [] args) {queue <string> queue = new LinkedList <string> (); queue.ffer ("Hello"); queue.ffer ("World!"); queue.offer ("Привет!"); System.out.println (queue.size ()); String Str; while ((str = queue.poll ())! = null) {System.out.print (str); } System.out.println (); System.out.println (queue.size ()); }}2. deque
Общественный интерфейс deque <e> расширяет очередь <e>
Линейная коллекция, которая поддерживает вставку и удаление элементов на обоих концах.
Название Deque - это аббревиатура «двойной очередь» и обычно читается как «колода».
Большинство реализаций Deque не имеют фиксированного ограничения по количеству элементов, которые они могут содержать, но этот интерфейс поддерживает как очередь ограниченных возможностей, так и двойные очереди без ограничений с фиксированным размером.
Этот интерфейс определяет метод доступа к элементам на обоих концах двойной очереди. Предоставляет методы для вставки, удаления и проверки элементов. Поскольку этот интерфейс наследует очередь интерфейса очередей, существует две формы для каждого из его методов: один бросает исключение, когда операция не выполняется, а другая возвращает специальное значение (нулевое или ложное, в зависимости от операции).
а При использовании двойной очереди в качестве очереди вы получите поведение FIFO (первое, первое). Добавьте элемент в конце двойной очереди и удалите элемент с начала двойной очереди. Методы, унаследованные от интерфейса очереди, полностью эквивалентны методу DEQA, как показано в следующей таблице:
беременный Используется как Lifo (последний в первом выходе). Этот интерфейс должен использоваться первым, а не устаревшим классом стека. При использовании двойной очередь в качестве стека элемент подталкивается в начало двойной очереди и появляется с начала двойной очереди. Метод стека полностью эквивалентен методу Deque, как показано в следующей таблице: