Справочник от Автор24
Найди эксперта для помощи в учебе
Найти эксперта
+2

Списки, стеки, очереди

Замечание 1

Списки, стеки, очереди — это линейные структуры данных.

Введение

Структурой данных является контейнер, хранящий данные в некотором макете. Данный «макет» может позволить структуре данных стаnь эффективной в определенных операциях и неэффективной в иных. Существуют структуры данных следующих типов:

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

К числу основных структур данных относятся следующие структуры:

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

Списки, стеки и очереди

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

  • push(x), выполняет добавление x в стек;
  • pop(), выполняет извлечение верхнего элемента из стека.

Приведем пример реализации стека на языке программирования Java:

class Stack {

ίnt sίze;

ίnt$[$$]$ data;

Stack(ίnt capacίty) {

data = new ίnt $[$capacίty$]$;

}

void push(ίnt value) {

data$[$sίze++$]$ = value;

}

ίnt pop() {

return data$[$--sίze$]$;

}

}

Односторонняя очередь (Queue) является структурой данных, реализующей принцип FIFO, то есть, первым пришел, первым ушел. Для того чтобы реализовать очередь, необходимо кроме массива с данными организовать два указателя, а именно, на голову и хвост. Хвост показывает на окончание очереди, а голова на ее начало. Приведем пример реализации очереди на языке программирования Java:

«Списки, стеки, очереди» 👇
Помощь эксперта по теме работы
Найти эксперта
Решение задач от ИИ за 2 минуты
Решить задачу
Помощь с рефератом от нейросети
Написать ИИ

class Queue {

ίnt sίze;

ίnt head; // голова

ίnt taίl; // хвост

ίnt$[$$]$ data;

0005:

Queue(ίnt sίze) {

data = new ίnt $[$thίs.sίze = sίze$]$;

}

voίd add(ίnt value) {

ίf (++taίl == sίze)

taίl = 0;

data$[$taίl$]$ = value;

}

ίnt extract() {

ίf (++head == sίze)

head = 0;

return data$[$head$]$;

}

boolean ίsEmpty() {

return head == taίl;

}

}

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

Двусторонней очередью (Double ended queue, deque) является очередь, которая не имеет явно выраженного конца и начала. Такая очередь способна увеличиваться и уменьшаться в обоих направлениях. Приведем реализацию двусторонней очереди на языке программирования Java:

class Deque {

ίnt sίze;

ίnt head;

ίnt taίl;

ίnt$[$$]$ data;

Deque(ίnt sίze) {

data = new ίnt $[$thίs.sίze = sίze$]$;

}

voίd pushBack(ίnt value) {

ίf (++taίl == sίze)

taίl = 0;

data$[$taίl$]$ = value;

}

ίnt popBack() {

ίnt ret = data$[$taίl$]$;

ίf (--taίl $\lt$ 0)

taίl = sίze - 1;

return ret;

}

voίd pushFront(ίnt value) {

data$[$head$]$ = value;

ίf (--head $\lt$ 0)

head = sίze - 1;

}

ίnt popFront() {

ίf (++head == sίze)

head = 0;

return data$[$head$]$;

}

boolean ίsEmpty() {

return head == taίl;

}

}

Связный список является достаточно распространенной структурой данных. Все компоненты списка должны обладать указателем на следующий компонент (для двусвязного списка необходим еще указатель и на предыдущий компонент). Программист имеет доступ к указателю на начало списка. Зная его, он может получать доступ к любому компоненту, путем последовательного прохода всех предыдущих компонентов. То есть, списки удобно использовать тогда, когда хватает лишь последовательного доступа к данным. Списки могут быть организованы на массивах, хотя более удобно применять динамическую память. Приведем реализацию односвязного списка на языке программирования Java:

Item list = null; // указатель на список

/$*$ Добавить в начало $*$/

void insert(int value) {

Item insertion = new Item(value);

if (list == null) {

list = insertion;

} else {

insertion.next = list;

list.prev = insertion;

list = insertion;

}

}

/$*$ Добавить в конец $*$/

void append(int value) {

Item insertion = new Item(value);

if (list == null) {

list = insertion;

} else {

Item lastNode = list;

while (lastNode.next != null)

lastNode = lastNode.next;

lastNode.next = insertion;

insertion.prev = lastNode;

}

}

/$*$ Вставить после заданного узла $*$/

void insertAfter(Item node, int value) {

Item insertion = new Item(value);

Item next = node.next;

/$*$ Устанавливаем прямые связи $*$/

node.next = insertion;

insertion.next = next;

/$*$ Устанавливаем обратные связи $*$/

insertion.prev = node;

if (next != null) // node может быть концом списка!

next.prev = insertion;

} /$*$ Вставить перед заданным узлом $*$/

void insertBefore(Item node, int value) {

Item insertion = new Item(value);

Item prev = node.prev;

/$*$ Устанавливаем прямые связи $*$/

if (prev != null)

prev.next = insertion;

else // node может быть началом списка!

list = insertion;

insertion.next = node;

/$*$ Устанавливаем обратные связи $*$/

insertion.prev = prev;

node.prev = insertion;

}

/$*$ Вставить узел $*$/

void remove(Item node) {

Item prev = node.prev;

Item next = node.next;

/$*$ Обновляем связи $*$/

if (prev != null)

prev.next = next;

if (next != null)

next.prev = prev;

if (node == list)

list = next;

}

/$*$ Класс узла $*$/

class Item {

int value;

Item next;

Item prev;

Item(int value) {

this.value = value;

}

}

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

Дата написания статьи: 14.02.2023
Найди решение своей задачи среди 1 000 000 ответов
Крупнейшая русскоязычная библиотека студенческих решенных задач
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot