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

[kaizer131]

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

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

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

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

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

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

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.

[Utkin]

А ты выбери в качестве очереди динамический массив или нельзя?
Тогда

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

Можем и легко .

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

Также если подумать и использовать динамические массивы? Тогда данные из стека можно и не удалять, достаточно изменять указатель на текущий элемент...

[kaizer131]

К сожалению, по условию задачи нельзя прибегать к использованию массивов, необходимо использовать только очереди и стеки

[Utkin]

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

[kaizer131]

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

Ну так и используй стек, но построй его на динамическом массиве .

А можно подробнее про это ?

[Utkin]

Да запросто - создаешь динамический массив:

type
 Stack =record
           data : Array of Integer;   // Массив хранящихся чисел 
           Uk : integer;                  // Указатель на вершину стека 
           Count : Integer;             // Число элементов в стеке (но можно и без него обойтись)
  end;

Когда элементов не хватает добавляешь через SetLength, а вот удалять можно по-разному - либо также как и создавать, либо просто сместив указатель на вершину. В общем как тебе удобней .
Если сместить указатель, то фактически элементы в массиве (но не в стеке!) будут по-прежнему существовать и их можно будет читать как из обычного массива имя_стека.data[индекс_элемента] .

[k1r1ch]

Эх , уточнил условия - никаких массивов только очереди и стеки

А как вы очередь объявляете без массива? Вроде вот очередь (писал здесь, могут быть описки):

var
  queue: array [1..N] of integer;
  ps, pe: integer; {ps = pe = 1}

procedure queue_push(x: integer);
begin
  queue[pe] := x;
  if pe < N then Inc(pe) else pe := 1;
end;

function queue_pop: integer;
begin
  queue_pop := queue[ps];
  if ps < N then Inc(ps) else ps := 1;
end;

Или я не прав?

[kaizer131]

Нет не так.

Очередь – это вид связанного списка, в котором извлечение элементов происходит с начала списка, а добавление новых элементов – с конца. К этому виду списка, по определению, неприменима операция обхода элементов.

Очередь является динамической структурой – с течением времени изменяется и количество, и набор составляющих ее элементов.

Опишем очередь на языке программирования:

Type
  EXO = ^O;
  O = record
       Data : integer;
       Next : EXO;
  end;

Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.