Очереди, queue Опции

[Гость_Boris]

Как видно из задания, задача будет идти о очередях.
Если кто забыл - напоминаю: основное правило очереди - первым вошёл - первым вышел!
Итак. Пусть дан одномерный массив (он задаёт количество элементов).
Задача заключается в следующем: с помощью функций put и get реализовать распечатку текста на экране.
.Например:
get(1)
get(2)
writeln(get)
writeln(get)

Причём если следующая команда get будет превышать массив, то число будет !!!!!записываться
в конец очереди (другой вариант - в начало)!!!!!!!!!!!!
пример:
put(1)
put(2)
put(3)
get
get
get ; здесь массив состоит из 2-х элементов и происходит переполнение ...

ВАЖНО:
функции имеют слежующий вид:

function put(i:integer):boolean; (возвращает false если очередь пуста(по-моему - а может когда переполнение??)
и true, если переполнения нет)

function get:integer;

Вот и всё: ПОМОГИТЕ бедному студенту.!
P.S:
Вот я написал, но при переполнении не то, совсем не то:

Код

uses crt;
const m=10;
var n:array[0..m] of integer;
   i,j: integer;
procedure Init;
begin
 for i:=1 to m do n[i]:=0;
 n[0]:=1;
end;
function put(a:integer):boolean;
begin
 put:=false;
 if n[0]<=m then
  begin
    n[n[0]]:=a;
    n[0]:=n[0]+1;
    put:=true;
  end;
end;
function get: integer;
begin
 if n[0]>1 then
  begin
    get:=n[1];
    n[0]:=n[0]-1;
    for i:=1 to m-1 do
     n[i]:=n[i+1];
  end;
end;
begin
init;
clrscr;
writeln;
put(1);
put(2);
put(3);
writeln(get);
writeln(get);
put(4);
writeln(get);
writeln(get);
readln;
end.

[volvo]

Гость_Boris

Если кто забыл - напоминаю: основное правило очереди - первым вошёл - первым вышел!

Причём если следующая команда get будет превышать массив, то число будет !!!!!записываться в конец очереди (другой вариант - в начало)!!!!!!!!!!!!

Вы же сами себе противоречите! До переполнения очереди - все в порядке. Но как только произошло переполнение, следующий элемент записывается первым, и тут Вы пытаетесь взять элемент из очереди... Что получилось? Нарушилось правило очереди (FIFO), т.к. элемент, который вошел последним, выйдет первым

Решите уже для себя, очередь это или какая-то другая структура данных... С очередями такой трюк не проходит...

[GoodWind]

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

может при переполнении стоит сдвигать очередь вперед, тогда можно обойтись малой кровью (в смысле потеряется только передний элемент очереди) ?

Код

function put(a:integer):boolean;
begin
put:=false;
if n[0]=10 then
 begin
   for i:=1 to 9 do n[i]:=n[i+1];
   n[0]:=9;
 end;
if n[0]<m then
 begin
   n[n[0]]:=a;
   n[0]:=n[0]+1;
   put:=true;
 end;
end;

вот так примерно... не знаю работает или нет, т.к. в набирал прям тут без проверки...

[Гость_Boris]

Так вот я и прошу переделать программу!

[volvo]

Так вот я и прошу переделать программу!

Поймите, нельзя переделать программу, не зная точного алгоритма

в конец очереди (другой вариант - в начало)

возвращает false если очередь пуста(по-моему - а может когда переполнение??

это алгоритм?

[Гость_Boris]

А функцию get тогда как переделать?
Или всё тоже самое оставить????

Добавлено (9.11.04 19:45):
Нет - ээто не алгоритм...
Конкретно: в конец очереди и false - если пусто

[GoodWind]

А функцию get тогда как переделать?

а разве переполненность очереди влияет на get ??

[Гость_Boris]

Ещё как...а в принципе ... дайте подумать...наврно всё таки нет.
Буду тестить! А вы тестили? КАк ?

[GoodWind]

Нет не тестил :no:
Предоставлю Вам сию почетную обязанность :yes:

[Гость_Boris]

Только что тестил ...
при m=3 b
put(1) pu(2) pu(3) pu(4) get get get get

пишет
1
2
4
21463

(странные цифры вылазиют)

[GoodWind]

дык вы пытаетесь из очереди длиной 3 элемента взять 4 элемента, вот и получается бурда

[Гость_Boris]

Так я же и говорю: если в друг очередь больше то последний элемент затирается и на его место пишется новый (в моём примере 3 должна затереться
4). А вы как думали?

[volvo]

Попробуйте так:

Код

const
 m = 3;

var
 a: array[1 .. m] of integer;
 first, last: integer;
 overflow: boolean;

{ инициализация очереди }
procedure init;
 begin
   first := 0; last := 0;
 end;

function get: integer;
 begin
   { при извлечении из очереди в любом случае
      признак переполнения снимается... }
   overflow := false;
   { извлекаем всегда первый эпемент }
   get := a[1];
   { после извлечения уменьшаем количество элементов в очереди }
   if last > 0 then dec(last);
   { и сдвигаем всю очередь на 1 позицию ближе к началу }
   move(a[2], a[1], (m - 1)*sizeof(integer));
   { освободившееся место в конце очереди заполняем нулем }
   a[m] := 0;
 end;

function put(x: integer): boolean;
 begin
   { устанавливаем признак переполнения - очередь считается
      переполненной, если она уже была переполненной до этой
      операции или если указатель конца очереди стоит на
      последнем элементе }
   overflow := overflow or (last = m);
   { если очередь переполнена, увеличения указатель конца
      очереди не происходит, иначе - он увеличивается на 1 }
   inc(last, byte(not overflow));
   { и в соответствующую ячейку пишется значение }
   a[last] := x;
   { функция возвращает признак переполнения очереди }
   put := overflow
 end;

var
 r: boolean;

begin
 init; { вызывать перед началом работы с очередью... }
 r := put(1);
 r := put(2);
 r := put(3);
 r := put(4);
 writeln(get);
 writeln(get);
 writeln(get);
 r := put(5);
 writeln(get);
end.

при переполнении Put возвращает True и последний элемент очереди затирается вновь введенным. Get при попытке чтения из пустой очереди возвращает 0...

Сообщение отредактировано: volvo - 10.11.2004 19:42

[Гость_Boris]

Спасибо..юработает.
Спасибо большое.

Добавлено (9.11.04 21:42):
Volvo, конечно ты молодец, но можно с подробнми комментариями, пожалуйста,
а то я в чужих программах не разбеоусь никогда.
Если не трудно,Volvo, напиши

[volvo]

Гость_Boris

Комментарии к программе добавлены

[Гость_Boris]

Thank - спасибо

Добавлено (10.11.04 14:30):

Сегодня мне сказали,что эта программа неправильная,т.к. например:

Код

const m=2
...
...
put(1)
put(2)
put(3)
writeln(get)
writeln(get)
writeln(get)
put(4)
writeln(get)

ТО ОТвет должен быть:

1
3
0
4

[volvo]

Гость_Boris

Скажите, Вы не догадываетесь о существовании на клавиатуре F7, F8 и окна Watches? Неужели трудно было догадаться, из-за чего это происходит ??? Смотрите исправленную версию Get...

P.S. Тесты нужно давать сразу...

[Гость_Boris]

Всё равно пишет : 1 3 4
а должен : 1 3 0 4

[volvo]

Ну что мне, EXE выслать? Какой компилятор?

P.S. А чему М равно?

Сообщение отредактировано: volvo - 10.11.2004 21:29

[Altair]

ЗЫ: я так понял задача решена (раз за нее взялся volvo )
НО!
я думаю что вообще-то все можно было решить с помощью функций и процедур из FAQ'а:

procedure QueueInit (VAR Q:TQueue); {INIT}
Function QueueEmpty(Q:TQueue):boolean; {проверка на заполненность}
Procedure OueuePush(var q:TQueue; e:TElem);  {поместить в хвост}
Function QueuePop(var q:TQueue):TElem;    {извлечь из хвоста}

Это все что нужно!