Как описать абстрактный тип данных?

@M@k7 · Регистрация: 17.10.2011

Студворк — интернет-сервис помощи студентам

очередь

@ramarren14 · 06.12.2011, 22:24

По идее как двусторонний массив(данные можно добавлять и в конец, и в начало).

Jupiter · 06.12.2011, 22:26

Сообщение от M@k7

Как описать абстрактный тип данных?

Это типа предложение сделать за вас? На форуме вообще-то есть поиск, и точно существует тема посвященная спискам, стекам, очередям и другим абстрактным структурами данных

@Chelioss · 06.12.2011, 22:28

Сообщение от ramarren14

По идее как двусторонний массив(данные можно добавлять и в конец, и в начало).

Двусторонний массив? Это как?

@DU · 06.12.2011, 22:35

Абстрактный - подразумевает наличие чисто виртуальных ф-ий. Интерфейс короче. У FIFO (first input first output) очереди интерфейс из двух ф-ий. одна для засовывания объекта в очередь, другая для высовывания из нее. Не шаблонная очередь для интов выглядит так:

C++
1
2
3
4
5
6
7
8
class Queue
{
public:
  virtual ~Queue() {}
 
  virtual void push(int val) = 0;
  virtual int pop() = 0;
};

Можно дополнить полезными ф-иями для определения количества объектов в очереди и т.п.
Реализовывать интерфейс можно как захочется. хоть на массивах, хоть на списках.

@alex_x_x · 06.12.2011, 22:36

предлагаю как в лиспе
тип пара + 4 оператора

абстрактней некуда

@Chelioss · 06.12.2011, 22:36

Сообщение от DU

Абстрактный - подразумевает наличие чисто виртуальных ф-ий.

ТС не об этом написал.

Jupiter · 06.12.2011, 22:38

Сообщение от DU

Абстрактный - подразумевает наличие чисто виртуальных ф-ий

DU, стоит различать абстрактный типы и структуры данных

@DU · 06.12.2011, 22:39

какой вопрос, такой ответ. заголовок + содержимое наталкивает на абстрактный интерфейс для очереди. если нет, то что такое абстрактный тип данных?

@M@k7 · 06.12.2011, 22:50 **[ТС]**

Абстра́ктный тип да́нных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций.

Мне нужен пример желательно с описантем.

@DU · 06.12.2011, 22:58

не хотите абстрактных классов. ок. вот очередь, которая соответствует вашему определению АТД

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Queue
{
public:
  void push(int val)
  {
    m_list.push_front(val);
  }
 
  int pop()
  {
    const int ret = m_list.back();
    m_list.pop_back();
    return ret;
  }
 
  unsigned size() const
  {
    return unsigned(m_list.size());
  }
 
  bool empty() const
  {
    return m_list.empty();
  }
 
private:
  std::list<int> m_list;
};

@ramarren14 · 06.12.2011, 23:04

Сообщение от Chelioss

Двусторонний массив? Это как?

Ну как то вот так!
http://pikucha.ru/i7fNG

@Chelioss · 06.12.2011, 23:45

Сообщение от DU

std::list<int> m_list;

std::deque же.

Сообщение от ramarren14

Ну как то вот так!
http://pikucha.ru/i7fNG

И где там написано про двусторонний массив?

@DU · 07.12.2011, 00:18

похоже вы не видите связи между тем определением, которое привели и тем классом, который я тут привел.

Поясняю

Абстра́ктный тип да́нных (АТД) — это тип данных

Queue - тип данных

, который предоставляет для работы с элементами этого типа определённый набор функций

C++
1
2
3
4
void Queue::push(int)
int Queue::pop()
unsigned Queue::size() const
bool Queue::empty() const

Все эти методы и есть тот самый набор ф-ий, который позволяет что-то делать с очередью

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

Можете считать дефолтный конструктор для Queue той самой ф-ией, которая и создает экзепляр абстрактного типа данных Очередь.

list<int> m_list - это деталь имплементации этой очереди. Она скрыта от пользователей очереди. Если вам не нравится std::list<int> , можете использовать любой другой std-ый контейнер или написать свой или еще как вам угодно это сделать. Пользователей класса Queue детали реализации вообще не должны волновать. Они работают с публичным набором функций (интерфейсом) класса Queue. Про инкапсюляцию слышали? Вот это и есть ее проявление: в классе Queue детали реализации скрыты за публичным интерфейсом.

@Chelioss · 07.12.2011, 00:24

Даже не читал полностью ваше сообщениею
Адаптер std::queue содержит по умолчанию контейнер типа std::deque.

@DU · 07.12.2011, 00:43

Адаптер std::queue содержит по умолчанию контейнер типа std::deque.

Можно же и списком параметризовать. deque - вероятно самый оптимальный для этих целей.
Но дело не в этом. Вопрос у ТС - как описать очередь. Можно трактовать двояко:
1 Где мне взять готовую очередь?
2 Как мне самому написать класс, представляющий очередь?
Подобного рода вопросы возникают в вузах, а там на начальных этапах требуют самодельной реализацииачальнии всяких динамических массивов, сортировок, очередей и т.д. Использование stl считается недопустимым читом. Поэтому в кратце и был изложен сбособ самодельной реализации (описания) очереди. Что действительно нужно ТС - хз.

Вот кстати пример требований к очереди:
С++ структура даных очередь
Хотят иметь возможность добавлять в начало очереди. с такими требованиями стандартная queue не подходит. Придется свой класс писать.

@alkagolik · 07.12.2011, 02:43

Сообщение от DU

Использование stl считается недопустимым читом.

это факт, "а факты, как известно вещь упрямая".

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@M@k7 7 / 7 / 1 Регистрация: 17.10.2011 Сообщений: 165

	Как описать абстрактный тип данных? 06.12.2011, 22:17. Показов 16273. Ответов 16 Метки нет (Все метки) очередь 0

@ramarren14 2 / 2 / 0 Регистрация: 14.07.2011 Сообщений: 49
	06.12.2011, 22:24
	По идее как двусторонний массив(данные можно добавлять и в конец, и в начало). 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	06.12.2011, 22:36
	предлагаю как в лиспе тип пара + 4 оператора абстрактней некуда 0

@DU 1500 / 1146 / 165 Регистрация: 05.12.2011 Сообщений: 2,279
	06.12.2011, 22:39
	какой вопрос, такой ответ. заголовок + содержимое наталкивает на абстрактный интерфейс для очереди. если нет, то что такое абстрактный тип данных? 0

@M@k7 7 / 7 / 1 Регистрация: 17.10.2011 Сообщений: 165
	06.12.2011, 22:50 [ТС]
	Абстра́ктный тип да́нных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Мне нужен пример желательно с описантем. 0

@Chelioss 186 / 186 / 21 Регистрация: 08.01.2011 Сообщений: 1,139
	07.12.2011, 00:24
	Даже не читал полностью ваше сообщениею Адаптер std::queue содержит по умолчанию контейнер типа std::deque. 0