Реализовать дек как массив, создать процедуры добавления и удаления

@Artishok · Регистрация: 27.12.2009

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

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

@Puporev · 24.09.2010, 19:56

Дек это типа стек, только двухсторонний, можно работать с начала и с конца. Вот здесь не на Паскале, но мне кажется это очень четко и коротко написано.
http://informatics.mccme.ru/mo... php?id=580
А в этой теме можно взять пример.
https://www.cyberforum.ru/pascal/thread77419.html

@Artishok · 24.09.2010, 21:51 **[ТС]**

то есть ссылки на предыдущий элемент надо или нет?

@Puporev · 24.09.2010, 21:53

В 2 стороны, с начала в конец или с конца к началу. Это другими словами двухсвязный список.

@Artishok · 25.09.2010, 19:27 **[ТС]**

Не по теме:

где же ты standart template library....

Добавлено через 37 минут

Pascal
1
2
3
4
type deck = record
       data: array[1..MAXSIZE] of integer;
       head, tail: integer;
     end;

раз это очередь то через массив структура дека будет такой?

Добавлено через 20 часов 47 минут

Pascal
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
type
  deque = record
    data: array[1..MAXSIZE] of integer;
    head, tail: integer;
  end;
 
procedure push_front(var d: deque; x: integer);
begin
  if d.head < 1 then d.head += maxsize;
  d.data[(d.head - 1) mod maxsize] := x;
end;
 
procedure push_back(var d: deque; c: integer);
begin
  d.data[(d.tail + 1) mod maxsize] := x;
end;
 
function pop_front(var d: deque): integer;
begin
  result := d.data[(d.head + 1) mod maxsize];
end;
 
function pop_back(var d: deque): integer;
begin
  if d.head < 1 then d.tail += maxsize;
  result := d.data[(d.head - 1) mod maxsize];
end;

вот что-то накидал.можете сказать насколько все неправильно?(перебивал с кода Си)

@lexus_ilia · 26.09.2010, 11:46

Artishok, массивы? Какие ещё массивы, ничего такого не надо, хорошенько посмотрите тему (ссылку на которую давал Puporev), я там расписывал как работать с динамическими структурами, вот оттуда и пляшите.

@Artishok · 26.09.2010, 14:09 **[ТС]**

так через динамику я сам сделаю.
а мне сказали чтобы через массив.

Не по теме:

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

@Puporev · 26.09.2010, 14:48

Artishok, Так вам просто массив нужен? И написать процедуры добавления и удаления элементов в начало и в конец? Или что?

@Artishok · 26.09.2010, 18:36 **[ТС]**

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

Pascal
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const
  maxsize = 10000;
 
type
  deque = record
    data: array[1..MAXSIZE] of integer;
    head, tail: integer;
  end;
 
procedure push_front(var d: deque; x: integer);
begin
  if d.head < 1 then d.head += maxsize;
  d.data[(d.head - 1 ) mod maxsize] := x;
end;
 
procedure push_back(var d: deque; x: integer);
begin
  d.data[(d.tail + 1) mod maxsize] := x;
end;
 
function pop_front(d: deque): integer;
begin
  result := d.data[(d.head + 1) mod maxsize];
end;
 
function pop_back(d: deque): integer; //
begin
  if d.tail < 1 then d.tail += maxsize;
  result := d.data[(d.tail - 1) mod maxsize];
end;
 
var
  dd: deque;
  dlen: integer;
 
begin
  dd.head := 0;
  dd.tail := 0;
  if dd.tail > dd.head then dlen := (dd.tail - dd.head) mod maxsize
  else
    dlen := maxsize - (dd.head - dd.tail) mod maxsize;
  push_front(dd, 1);
  push_back(dd, 2);
  push_back(dd,3);
  while dd.head<>dd.tail do
  writeln(pop_back(dd));
  //write(pop_front(dd));
  if dd.head = dd.tail then writeln('ff'); //признак пустоты дека. 
end.

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

C
1
--d->h

не эквивалентно

Pascal
1
d.tail - 1

а вот на Си аналогичный код работает верно.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#define maxn 1000
 
using namespace std;
 
typedef struct
{
    int h,t;
    int val[maxn];
} deque;
 
void push_front(deque *d, int x)
{
if (d->h<1) d->h +=maxn; //chtob ukazateli ne bili otritsatelnimi
 d->val[(--d->h)%maxn]=x;
}
 
void push_back(deque *d,int x)
{
    d->val[(d->t++)%maxn]=x;
}
 
int pop_front(deque *d)
{
    return d->val[(d->h++)%maxn];
}
 
int pop_back(deque *d)
{
    if (d->t<1) d->t +=maxn;
    return d->val[(--d->t)%maxn];
}
int main()
{
    deque a;
    int dlen;
    if (a.t>a.h) dlen=(a.t-a.h)%maxn;
    else dlen=maxn-(a.h-a.t)%maxn;
    a.t=0;
    a.h=0;
    push_back(&a,5);
    push_back(&a,1);
    push_back(&a,2);
    push_back(&a,3);
    push_back(&a,4);
    push_back(&a,6);
    push_back(&a,7);
    while (a.h !=a.t-3) //proverki
    {
        std::cout<<pop_front(&a)<<endl;
    }
    std::cout<<"etap 2"<<endl;
    if (a.h==a.t) std::cout<<"finita"<<endl; 
    else                            //nebolshaia proverka raboti
    {
    while (a.h !=a.t)
    {
        std::cout<<pop_front(&a)<<std::endl;
    }
    }
    if (a.h==a.t) std::cout<<"finita"<<endl;
    return 0;
}

@Puporev · 26.09.2010, 18:51

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

if d.head < 1 then d.head += maxsize;

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

result := d.data[(d.head + 1) mod maxsize];

И это работает в Паскале?

Добавлено через 9 минут
Я думаю все намного проще.

Pascal
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
29
30
31
32
33
const
  maxsize = 10000;
 
type
  data: array[1..MAXSIZE] of integer;
 
procedure push_front(var d: data; x:integer; var n: integer);
var i:integer;
begin
  n:=n+1;
  for i:=n downto 2 do
  d[i]:=d[i-1];
  d[1]:=x;
end;
 
procedure push_back(var d: deque; x:integer; var n: integer);
begin
  n:=n+1;
  d[n]:=x;
end;
 
procedure pop_front(var d: deque;var n:integer);
var i:integer;
begin
 for i:=1 to n-1 do
 d[i]:=d[i+1];
 n:=n-1;
end;
 
procedure pop_back(var n:integer): integer;
begin
  n:=n-1;
end;

@Artishok · 26.09.2010, 18:55 **[ТС]**

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

И это работает в Паскале?

в pascalabc.net да.
там также работает такой код

Pascal
1
2
3
begin
var x:integer:=3; //или var x:=3
end;

Pascal
1
2
3
4
5
6
uses
  system;
 
begin
  console.WriteLine('Hello world');
end.

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767

	Реализовать дек как массив, создать процедуры добавления и удаления 24.09.2010, 19:46. Показов 6767. Ответов 10 Метки нет (Все метки) надо реализовать дек через массив. такой вопрос. дек - это как бэ очередь с возможностями удаления и добавления как в стеке.а вот что насчет проходов? только с одного конца проходы или нет? 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	24.09.2010, 19:56
	Дек это типа стек, только двухсторонний, можно работать с начала и с конца. Вот здесь не на Паскале, но мне кажется это очень четко и коротко написано. http://informatics.mccme.ru/mo... php?id=580 А в этой теме можно взять пример. https://www.cyberforum.ru/pascal/thread77419.html 1

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767
	24.09.2010, 21:51 [ТС]
	то есть ссылки на предыдущий элемент надо или нет? 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	24.09.2010, 21:53
	В 2 стороны, с начала в конец или с конца к началу. Это другими словами двухсвязный список. 0

@lexus_ilia 3067 / 727 / 69 Регистрация: 24.09.2008 Сообщений: 1,531
	26.09.2010, 11:46
	Artishok, массивы? Какие ещё массивы, ничего такого не надо, хорошенько посмотрите тему (ссылку на которую давал Puporev), я там расписывал как работать с динамическими структурами, вот оттуда и пляшите. 0

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767
	26.09.2010, 14:09 [ТС]
	так через динамику я сам сделаю. а мне сказали чтобы через массив. Не по теме: если бы через динамику то я на паре сразу бы и сдал.а так взял домой. некоторым например дали очередь через массив организовать. P.s. правда я не понимаю зачем это нужно т.к. не вижу преимуществ при организации через массив. 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	26.09.2010, 14:48
	Artishok, Так вам просто массив нужен? И написать процедуры добавления и удаления элементов в начало и в конец? Или что? 0