Реализация стеков и очередей

@kaizer131 · Регистрация: 13.07.2009

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

Доброго времени суток!

Разбираюсь со стеками и очередями на примере следующей задачи:

“Дан стек, элементами которого являются действительные числа. Сформировать структуру данных очередь, в которую включить значения тех элементов из стека, которые не превосходят uz. Элементы с найденными значениями из стека исключить. А также получить:
(uz+r)/(uz+s),
где
r- сумма всех тех значений элементов, которые не превосходят u,
s- сумма значений элементов, больших u.”

Возник ряд вопросов:

1. Если мы берем из стека верхний элемент (например, для вывода на экран), то, получается, мы должны его перед этим занести в другой стек, чтоб этот элемент не потерялся?
2. Как правильно вывести на экран заполненную очередь, ведь мы не можем просто пройтись по её элементам для вывода. Значит ли это что нам нужно перед выводом сохранять их в другую очередь?

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

Delphi

program new_stack;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
type
 Stack =^Еlеm;
         Еlеm = Record
           inf : integer;
           next : Stack;
          end;
 
  Ocher =^och;
      och = record
           inf : integer;
           next : Ocher;
         end;
 
/////////////////////// Добавляем в стек ///////////////////////////////////////
 
Procedure In_stak(Var Beg:Stack; Sim:integer);
Var x:Stack;
Begin
    New(X);
    X^.inf:=Sim;
    X^.next:=Beg;
    Beg:=X;
End;
 
//////////////////////////// Достаём верхний элемент стека /////////////////////
 
procedure Out_stak(Var Beg: Stack; Var Flag: Boolean);
Var x: Stack;
Begin
    If   Beg= Nil  then  Flag:= false   else
            Begin
            Flag:=true;
            X:=Beg;
            Beg:=Beg^.next;
            Dispose(x);
             End;
End;
//////////////////////////////////////////////////////////////////////////////////
 
 
 
//////////////////////// Занесение в очередь ///////////////////////////////////
 Procedure writeO(Var BeginO, EndO : Ocher; c : integer);
Var
  Elem : Ocher;
Begin
  new(Elem);
  Elem^.inf := c;
  Elem^.Next := Nil;
  if BeginO = Nil {проверяем, пуста ли очередь}
    then
      BeginO := Elem {ставим указатель начала очереди на первый созданный элемент}
    else
      EndO^.Next := Elem; {ставим созданный элемент в конец очереди}
  EndO := Elem; {переносим указатель конца очереди на последний элемент}
End;
 
///////////////////////////// Чтение из очереди /////////////////////////////////
Procedure readO(Var BeginO : Ocher; Var INF : integer);
Var
  Elem : Ocher;
Function FreeO(x1 : Ocher): boolean;
Begin
  FreeO := (x1 = Nil);
End;
Begin
  if FreeO(BeginO)
    then
      writeln('Очередь пуста')
    else
      begin
        INF := BeginO^.inf; {считываем искомое значение в переменную с}
        Elem := BeginO; {ставим промежуточный указатель на первый элемент очереди}
        BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}
        dispose(Elem); {освобождаем память, занятую уже ненужным первым элементом}
      end;
End;
 
var
MY,MY2:Stack;
INF,I,uz,R,S:integer;
BeginO, EndO , O:Ocher;
IO:Boolean;
begin
 R:=0;
 S:=0;
 Randomize;
 write ('Input Uz :');
 readln(uz);
 
 
 
 MY:=nil;
 BeginO:=nil; EndO :=nil;
for I := 0 to 10 do
  begin
  In_stak(MY, random(100));
  end;
 
 
 
   write ('Ishodn stack :');
    while MY <> Nil do
    begin
    write (My^.inf);
    write ('-->');
    MY:=My^.next;
 
    end;
 
 
   readln;
 
 
  while MY <> Nil do
 
  Begin
  Out_stak(My,IO); // из основного стека достали
 
   if MY^.inf <uz then
 
    begin
    R:=MY^.inf;
    writeO( BeginO, EndO , MY^.inf); {помещаем элемент в очередь }
    end
    else
 
    begin
     if MY^.inf >=uz then
    begin
    S:=MY^.inf;
    In_stak(MY2, MY^.inf);
    end;
 
 
    End;
     MY := MY^.next;
  End;
 
 
/////////////// Вывод стека ////////////////////////////////////////////////
 while MY2 <> nil do
 begin
 write (MY2^.inf);
 MY2:=MY2^.next;
 end;
 
 /////////////// Вывод Очереди ////////////////////////////////////////////////
 while O <> nil do
 begin
 write (O^.inf);
 O:=O^.next;
 end;
 
 
/////////////// Вывод итогового числа ////////////////////////////////////////////////
 writeln ('Iskomoe chislo :');
 write ((uz+r)/(uz+s)) ;
 
 readln;
end.

@Splitter · 25.02.2010, 13:50

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

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

@kaizer131 · 25.02.2010, 14:04 **[ТС]**

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

1.
если вы реализовали процедуру которая "достает" элемент из стека, то да, он из стека пропадает,

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

Delphi

write ('Ishodn stack :');
    while MY <> Nil do
    begin
    In_stak(MY2, MY^.inf);{заносим во второй стек}
    write (My^.inf);
    write ('-->');
    MY:=My^.next;
    end;

@Splitter · 25.02.2010, 14:31

у Вас какая-то непонятная "доставалка" из стека, она ничего не возвращает, только перестраивает стек, удаляя верхний элемент, попробуйте переделать ее примерно так

Delphi

function Out_stak(Var Beg: Stack; Var Flag: Boolean):integer;
Var x: Stack;
Begin
    If   Beg= Nil  then  Flag:= false   else
            Begin
            Flag:=true;
            X:=Beg;
                        ut_stak:=Beg.inf;
            Beg:=Beg^.next;
            Dispose(x);
             End;
End;

тогда заполнить второй стек можно так

Delphi

var temp:integer;
flag:boolean;
...
 
while MY <> Nil do
    begin
    temp:=Out_stak(My,flag);
    if flag then
begin
    In_stak(MY2,temp );{заносим во второй стек}
    write (temp);
    write ('-->');
end
    end;

не проверял, но суть должна быть ясна

@kaizer131 · 25.02.2010, 14:54 **[ТС]**

в temp заносятся неверные значения

@Splitter · 25.02.2010, 15:22

а так?

Delphi

function Out_stak(Var Beg: Stack; Var Flag: Boolean):integer;
Var x: Stack;
Begin
        If   Beg= Nil  then  Flag:= false   else
                    Begin
                        Flag:=true;
                        X:=Beg;
                        Out_stak:=Beg.inf;
                        Beg:=Beg^.next;
                        Dispose(x);
                     End;
End;

@kaizer131 · 25.02.2010, 17:52 **[ТС]**

сейчас опробую

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

Delphi

1	Out_stak:=Beg.inf;

А разве можно присваивать функции значение ?

@Splitter · 25.02.2010, 20:42

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

А разве можно присваивать функции значение ?

можно конечно, для этого функция и нужна, можно еще написать

Delphi

1	return Beg.inf

что аналогично

Добавлено через 2 минуты
я балбес, Сишный синтаксис написал

правильный аналогичный вариант

Delphi

1	Result:=Beg.inf

@Splitter 203 / 145 / 16 Регистрация: 13.01.2009 Сообщений: 554
	25.02.2010, 13:50	2
	1. если вы реализовали процедуру которая "достает" элемент из стека, то да, он из стека пропадает, смысл стеков в том, что для них важен только текущий момент, допустим один поток кидает элементы в стек, другой их оттуда достает, обрабатывает и куда-то дальше отправляет, т.е. что было и что будет нас совершенно не волнует... 2. очередь, это как я понимаю однонаправленный список, сохраните указатель на его голову отдельно, потом пройдитесь по списку для вывода и верните указатель на голову из ранее сохраненного 0

@kaizer131 0 / 0 / 0 Регистрация: 13.07.2009 Сообщений: 36
	25.02.2010, 14:54 [ТС]	5
	в temp заносятся неверные значения 0

	25.02.2010, 20:42

Опции темы