Задача на стеки и очереди. Опции

[Анисия]

Добрый день. Помогите разобраться с очередями и стеками. Как организовать очередь из n целых чисел. Пока взяла 5 чисел, это получается что надо сформировать массив. Посмотрите пожалуйста правильно сделала?

program Lab_4;
const  max=5;
type Evt= integer;
var
elem:array [1..max] of Evt;
spos, rpos:integer;

end.

[volvo]

это получается что надо сформировать массив

Тебе что, стек организовать надо на основе массива? Извращение... Стек - он тем и хорош, что не имеет ограничений, которые имеет массив, а ты опять хочешь его загнать в те же рамки?

В FAQ-е, в теме "Все о динамических структурах данных" есть информация о создании стеков/очередей в нормальном виде...

[Анисия]

Тебе что, стек организовать надо на основе массива? Извращение... Стек - он тем и хорош, что не имеет ограничений, которые имеет массив, а ты опять хочешь его загнать в те же рамки?

В FAQ-е, в теме "Все о динамических структурах данных" есть информация о создании стеков/очередей в нормальном виде...

Мне надо сформировать очередь из n чисел.

[volvo]

Очередь можно сформировать на основе статического массива, или на основе динамического выделения памяти. Какое формирование нужно тебе?

Вот тебе пример: сформировала ты очередь из 5-ти чисел, а преподаватель тебе говорит: а добавь-ка шестое число... И что? Выходишь из программы, меняешь цифры, перекомпилируешь, запускаешь заново и вводишь 6 чисел? А ведь этого можно избежать, и вводить столько чисел, на сколько хватит памяти. Ну, в общем решать тебе, конечно... Я просто говорю, как лучше, но как всегда это никого не интересует - все делают по-своему. А потом приходят, и говорят, что не сдали...

[Lapp]

Мне кажется, что дело даже не в том, что шестой элемент не влезет, а в том, что если взять заведомо большой массив (чтоб все влезло на все случаи жизни), то будет неоправданная трата памяти. Динамическая память хороша именно тем, что выделяется только тогда, когда она нужна.

Но использование памяти - это другая тема. И вполне возможно, что Анисия этого еще просто не знает. Так что ничего не вижу плохого в демонстрации собственно принципа очереди на статическом массиве. Вот, я продолжил (немного изменив некоторые идентификаторы) программу из первого поста:

program Lab_4;
const
  max=5;
  m=max-1;

type
  tElem= integer;

var
  Line: array [0..m] of tElem;
  a: tElem;
  spos,rpos,n: integer;


function Put(e: tElem): boolean;
begin
  if n<Max then begin
    Rpos:=(Rpos+1) mod max;
    Line[Rpos]:=e;
    Inc(n);
    Put:=true
  end
  else Put:=false
end;


function Get(var e: tElem): boolean;
begin
  if n>0 then begin
    e:=Line[Spos];
    Spos:=(Spos+1) mod max;
    Dec(n);
    Get:=true
  end
  else Get:=false
end;


procedure Init;
begin
  Spos:=0;
  Rpos:=m;
  n:=0
end;

begin
  Init;
  WriteLn(Put(1));
  WriteLn(Put(2));
  WriteLn(Put(5));
  WriteLn(Put(-1));
  WriteLn(Put(10));
  WriteLn(Put(4));    {тут очередь переполнится, и пойдет false}
  WriteLn(Put(6));

  while Get(a) do WriteLn('Got ',a);
  ReadLn
end.

Анисия - разберешься?

[Анисия]

Анисия - разберешься?

Попробую...

[Анисия]

Подскажите что означает две команды Dec и Inс???

Сообщение отредактировано: Анисия - 6.03.2009 8:40

[Lapp]

Подскажите что означает две команды Dec и Inс???

Dec(x) эквивалентно x:=x-1
Inc(x) эквивалентно x:=x+1

[amega]

а можно маденький вопросик? уже которою програму просматриваю. били на форуме я ни как не могу понять, чем отличается

type
  tElem= integer;

var
  Line: array [0..m] of tElem;
  a: tElem;
  spos,rpos,n: integer; //почему тогда здесь не писали тип telem?
function Put(e: tElem): boolean;

от того что мы просто зделает так

var
  Line: array [0..m] of integer;;
  a: integer;
  spos,rpos,n: integer;
function Put(e: integer): boolean;

[volvo]

//почему тогда здесь не писали тип telem?

Не путай теплое с мягким... TElem описывает тип данных, а то, что ты показал - это индексы, а они всегда целочисленные... А вот если тебе понадобится очень быстро сменить тип данных, с которыми работает программа, например, на вещественный (без лазания по коду и многократной перекомпиляции, чтоб выяснить "а где еще недопустимое присваивание"), то достаточно будет всего лишь изменить TElem.

[amega]

Не путай теплое с мягким... TElem описывает тип данных, а то, что ты показал - это индексы, а они всегда целочисленные... А вот если тебе понадобится очень быстро сменить тип данных, с которыми работает программа, например, на вещественный (без лазания по коду и многократной перекомпиляции, чтоб выяснить "а где еще недопустимое присваивание"), то достаточно будет всего лишь изменить TElem.

о спасибо! буду знать теперь)

[Анисия]

Попробовала сегодня написать, счою программку на очереди. Ну не как не могу понять почему у меня выводится значения:
vvod 69
vvod 0
vvod 0
vvod 0

 
program ocher;
const
m=4;

type
tEl=integer;

var
line: array [1..m] of tEl;
a: tEl;
f,r, n:integer;

function vvod( e:tEl): boolean;
begin
if n<m then begin
f:=f+1;
line[f]:=e;
inc(n);
vvod:=true ; end
else vvod:=false; end;

function vivod( var e:tEl): boolean;
begin
if n>0 then begin
e:=line[r];
r:=r+1;
dec(n);
vivod:=true;
end
else vivod:=false; end;

procedure init;
begin
r:=0; f:=m; n:=0;
end;

begin
init;
writeln(vvod(2));
writeln(vvod(3));
writeln(vvod(4));
writeln(vvod(5));
writeln(vvod(6));

while vivod(a) do
writeln('vvod ', a);
readln;
end.

[volvo]

Добавь первой строкой {$R+} и запусти свою программу еще раз... Ты узнаешь много интересного

[Анисия]

Выходит за пределы страницы f:=f+1; на этой строке

[Lapp]

Выходит за пределы страницы f:=f+1; на этой строке

И это все, что ты можешь сказать?.. Это определила не ты, а железная машина. А ты должна из этого сделать выводы.

Но сначала поправка: не страницы, а массива. И не на этой строке, а на следующей.
Ты f чем инициалицировала? 4? Так. А потом к нему единицу прибавила? Прибавила. Что вышло? Правильно, 5. А массив у тебя размерности какой? 4. Так чего ты хочешь?..

Тебе надо сделать не просто приращение f, а циклическое приращение по модулю 5. И массив тебе, думаю, надо нумерновать с нуля, а не с единицы. Тогда приращение f сделаешь так:

f:=(f+1) mod 5;

Понятно?
Еще ты с m запуталась. Пусть m будет длина очереди, а нумерация - от 0 до m-1=m1.
Вот, смотри, я тебе все это сделал. И, ПОЖАЛУЙСТА, обрати внимание на формат.. Ну нельзя же программы писать как записки соседу по парте!..

program ocher;
const
  m=5;
  m1=m-1;

type
  tEl=integer;

var
  line: array [0..m1] of tEl;
  a: tEl;
  f,r, n:integer;

function vvod( e:tEl): boolean;
begin
  if n<m then begin
    f:=(f+1) mod m;
    line[f]:=e;
    inc(n);
    vvod:=true
  end
  else vvod:=false
end;

function vivod( var e:tEl): boolean;
begin
  if n>0 then begin
  e:=line[r];
  r:=r+1;
  dec(n);
  vivod:=true;
  end
  else vivod:=false;
end;

procedure init;
begin
  r:=0; f:=m1; n:=0;
end;

begin
  init;
  writeln(vvod(2));
  writeln(vvod(3));
  writeln(vvod(4));
  writeln(vvod(5));
  writeln(vvod(6));

  while vivod(a) do
  writeln('vvod ', a);
  readln;
end.

И последнее: зачем ты стала переделывать мой код? Только сейчас заметил, что он практически идентичен)). Для тренировки? Ок, похвально, что не копи-пейст)).
Спрашивай еще, что неясно.

[Анисия]

Мне дали вот такое задание: организовать очередь из n целых чисел. Изменить ссылки так, чтобы последний элемент очереди стал первым, первый – вторым, вто-рой – третьим и т.д.

[Анисия]

Как я правидно поняла, надо циклом создавать очередь чисел, и первый эелемнт помещать в конец очереди

program ctack;

type link=^node;
eltype=integer;
node= record
      elem:eltype;
      next: link;
      end;
list=link;
var start, last:link;


procedure zam( var l:list);
begin
     if L<>nil then
        begin
             start:=l;
             last:=l^.next;
             l^.next:=nil;

А как сдвигать ссылку на следующий элемент7

[volvo]

Изменить ссылки так, чтобы последний элемент очереди стал первым, первый – вторым, вто-рой – третьим и т.д.

Мне всегда нравятся вот такие задания... Просто великолепно. А ничего, что для этого не надо менять никакие ссылки? Это задание вообще не надо делать. Это не очередь уже, вот в чем дело... Ты в очереди когда-нибудь стояла? Знаешь, что это? Это FIFO - "первым пришел, первым вышел". А ты что предлагаешь? Пришел кто-то последним, тут его раз, перекинуть в самое начало, а всех отодвинуть? Какая-то коррумпированная очередь у тебя. Не пойдет... Не предназначена для этого очередь. Чтоб первый стал последним - легко, для этого достаточно изъять элемент из очереди, и добавить его снова, он добавится в конец... С деком твоя операция тоже делается легко, поскольку там очередь - двухсторонняя, там можно брать элемент с любой стороны, и добавлять его тоже в любую сторону, хоть в "голову", хоть в "хвост", он предназначен для таких операций, рассчитан на них. А очередь, увы, нет...

Поймите уже раз и навсегда: нельзя вообще лезть на уровень указателей, когда работаешь с очередью. Равно, как и с любой другой структурой данных. Твое дело при работе с очередями - запрограммировать 2 операции: Get (которая берет элемент из начала очереди), и Put (которая добавляет элемент в ее конец). Всё, ничего больше... Точно так же, как при работе со стеком никому в голову не придет менять указатели, все что надо - это Push/Pop, иначе это уже не стек, а простой список...

[Lapp]

А ты что предлагаешь? Пришел кто-то последним, тут его раз, перекинуть в самое начало, а всех отодвинуть?

ага, а так всегда и делалось у нас! Так просто не отучишь..

Справедливости ради, замечу, что в принципе эту операцию можно осуществить, если в реализации очереди предусмотрена функция Length (Длина). Тогда просто нужно повторить перекладывание из начала в хвост Length-1 раз.

Мне кажется, нет смысла все это вещать пользователю Анисия. Человек, ни разу не сказавший тривиальное "спасибо" ни одному из отвечавших, практически не отвечающий на вопросы собеседников, вряд ли заслуживает каких бы то ни было советов или объяснений..

[Анисия]

Спасибо за то, что указали за мою бестактность.... Больше не буду.

Но я действительно не понимаю.......

Сообщение отредактировано: Анисия - 1.04.2009 7:57