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

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

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

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

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

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

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

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

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

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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
1
2
3
4
5
6
7
8
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
1
2
3
4
5
6
7
8
9
10
11
12
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
1
2
3
4
5
6
7
8
9
10
11
12
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

Новые блоги и статьи Все статьи Все блоги /
sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .	SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .
Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .	Lazarus. Таблица с объединением ячеек. Massaraksh7 21.03.2025 Понадобилась представление на экране таблицы с объединёнными ячейками. И не одной, а штук триста, и все разные. На Delphi я использовал для этих целей TStringGrid, и то, кривовато получалось. А в. . .	Async/await в Swift: Асинхронное программирование в iOS mobDevWorks 20.03.2025 Асинхронное программирование долго было одной из самых сложных задач для разработчиков iOS. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .

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

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

Опции темы