10_Очередь

1. Линейные динамические структуры данных Очереди

1

2.

Очередь – это линейная динамическая
структура данных, при которой изъятие
компонентов происходит из начала
цепочки, а добавление - в конец цепочки.
L
g
v
g
v
1
2
...
g
v .
n
R
Очередь отличается от стека тем, что добавляется
второй указатель – R, указывающий на элемент с
полем, указывающим на nil.
2

3. Программа создания очереди type point=^node; node=record g:integer; v:point end; var 1 L, R, K: point; K –дополнительная

переменная
2
j, i:integer;
3 begin
4
j:=strtoint(memo1.lines[0]); первый элемент очереди создается отдельно
5
new(K);
6
K^.g:=j;
7
K^.v:=nil;
8
R:=K;
9
L:=K;
10 for i:=1 to memo1.lines.count-1 do begin
11
j:=strtoint(memo1.lines[i]);
12
new(K);
13
K^.g:=j;
14
K^.v:=L;
15
L:=K
16 end;
17 end;
3

4.

var
1
L, R, K: point; K –дополнительная переменная
R
L
K
4

5.

Пусть исходные данные: 5 3 4 1 (вводятся с
помощью объекта memo1)
5
new(K);
6 K^.g:=j;
7 K^.v:=nil;
K^.g
5
K^.v
.
R
L
K
5

6.

8
9
R:=K;
L:=K;
5
L
.
R
K
6

7.

10 for i:=1 to memo1.lines.count-1 do begin
11
j:=strtoint(memo1.lines[i]);
12
new(K);
для i=1
5
L
.
R
K
7

8.

10 for i:=1 to memo1.lines.count-1 do begin
11
j:=strtoint(memo1.lines[i]);
12
new(K);
для i=1
5
L
.
R
K
8

9.

Пусть исходные данные: 5 3 4 1 (вводятся с
помощью объекта memo1)
для i=1
13 K^.g:=j;
14 K^.v:=L;
K^.g
3
5
L
.
K^.v
R
K
9

10.

15
L:=K
3
5
L
.
R
K
10

11.

15
L:=K
3
5
L
.
R
K
11

12.

Пусть исходные данные: 5 3 4 1 (вводятся
с помощью объекта memo1)
для i=3
1
4
3
5
v
v
v
v.
R
L
K
12

13. Добавление нового узла к очереди Добавление нового узла к очереди происходит справа (используется указатель R)

13

14.

1 var
2 rnew: point; rnew – вспомогательная переменная
3 z:integer; число для добавления
4 begin
5 z:=strtoint(edit1.text);
6 new(rnew);
7 R^.v:=rnew;
8 rnew^.g:=z;
9 rnew^.v:=nil;
10 R:=rnew;
11 end;
Очередь построена в предыдущем примере.
14

15.

1 var
2 rnew: point;
3 z:integer;
4 begin
5 z:=strtoint(edit1.text);
L
rnew
1
4
3
5
v
v
v
v.
R
15

16.

6 new(rnew);
rnew
rnew^.g
rnew^.v
L
1
4
3
v
v
v
5
.
R^.v
R
16

17.

rnew
7 R^.v:=rnew;
rnew^.g
L
1
4
3
v
v
v
5
R^.v
rnew^.v
R
17

18.

Пусть z=6
rnew
8 rnew^.g:=z;
9 rnew^.v:=nil;
rnew^.g
1
4
3
5
6
v
v
v
v
.
rnew^.v
L
R
18

19.

10 R:=rnew;
rnew
1
4
3
5
6
v
v
v
v
.
L
R
19

20.

10 R:=rnew;
rnew
1
4
3
5
6
v
v
v
v
.
L
R
20

21. Исключение узла из очереди

Исключение узла из очереди происходит
слева (используется указатель L)
21

22.

1 var
2 Lold: point; Lold – вспомогательная
переменная
3 z:integer;
4 begin
5 Lold:=L;
6 z:=Lold^.g;
7 L:=Lold^.v;
8 dispose(Lold);
9 end;
22

23.

1 var
2 Lold: point;
3 z:integer;
L
Lold
1
4
3
5
v
v
v
v.
R
23

24.

5 Lold:=L;
Lold
L
1
4
3
5
v
v
v
v.
R
24

25.

6 z:=Lold^.g;
7 L:=Lold^.v;
Lold
1
Lold^.v
L
4
3
5
v
v
v.
R
25

26.

8 dispose(Lold);
Lold
1
L
4
3
5
v
v
v.
R
26

27.

8 dispose(Lold);
Lold
недоступна
1
L
4
3
5
v
v
v.
R
27

28. Поиск элемента в очереди

Пусть нужно найти определенный
элемент в очереди (например – 3).
28

29.

1 var
2 dop: point; dop – вспомогательная переменная
3 fl:boolean;
4 begin
5 dop:=L;
6 fl:=true; элемента нет в списке
7 while (dop<>nil) and fl do
8
if dop^.g=3 then fl:=false
9
else dop:=dop^.v;
10 end;
29

30.

1 var
2 dop: point;
3 fl:boolean;
L
dop
1
4
3
5
v
v
v
v.
R
30

31.

5 dop:=L;
6 fl:=true;
dop
L
1
4
3
5
v
v
v
v.
R
31

32.

7 while (dop<>nil) and fl do
8
if dop^.g=3 then fl:=false
9
else dop:=dop^.v;
dop
dop^.g
1
L
dop^.v
4
3
5
v
v
v.
R
32

33.

7 while (dop<>nil) and fl do
8
if dop^.g=3 then fl:=false
9
else dop:=dop^.v;
dop
dop^.g
1
4
v
L
dop^.v
3
5
v
v.
R
33

34.

7 while (dop<>nil) and fl do
8
if dop^.g=3 then fl:=false
9
else dop:=dop^.v;
dop
dop^.g
L
1
4
v
v
3
5
v.
dop^.v
R
Если элемента, равного 3 в списке нет, то dop=nil
fl:=true
34

35. Добавление элемента в середину очереди Добавление элемента происходит после элемента с полем dop^.g=3, который был найден в

предыдущем примере и на который
указывает переменная dop. (Указатель dop уже
стоит на элементе, после которого нужно
вставить новый элемент).
35

36.

1 var
2 rnew: point; rnew – вспомогательная переменная
3 z:integer;
4 begin
5 z:=strtoint(Edit1.text);
6 new(rnew);
7 rnew^.g:=z;
8 rnew^.v:=dop^.v;
9 dop^.v:=rnew;
10 end;
36

37.

1 var
2 rnew: point;
dop
rnew
dop^.g
L
1
4
v
v
3
5
v.
dop^.v
R
37

38.

6 new(rnew);
rnew
dop
dop^.g
L
1
4
v
v
3
5
v.
dop^.v
R
38

39.

7 rnew^.g:=z; Пусть z=6
8 rnew^.v:=dop^.v;
rnew
dop
6
rnew^.g
rnew^.v
dop^.g
1
4
v
L
3
5
v.
v
dop^.v
R
39

40.

9 dop^.v:=rnew;
dop
rnew
dop^.g
1
4
v
L
3
6
5
v.
v
dop^.v
R
40

41.

9 dop^.v:=rnew;
dop
rnew
dop^.g
1
4
v
L
3
6
5
v.
v
dop^.v
R
41

42.

Построение циклического
(кольцевого) списка
R^.v:=L;
L
1
4
3
5
v
v
v
v.
R^.v
R
42

43.

Построение циклического
(кольцевого) списка
R^.v:=L;
L
1
4
3
5
v
v
v
v
R^.v
R
Любой указатель R или L может быть принят за
начало списка
Очереди используются для моделирования СМО
(систем массового обслуживания)
43