Второй способ - кольцевой массив.
При такой реализации очередь описывается также как и в 1 способе
Для такой очереди возможна ситуация когда индекс начала очереди меньше индекса конца
Очередь заполнена полностью, когда первый элемент следует сразу за последним
Ввели соглашение, что индекс начала очереди указывает не на первый элемент а на предшествующий
Procedure delturn(var Q:turn);
Begin
Q.begt:=0;
Q.endt:=0;
End;
Проверка на пустоту
Function emptyt(var Q:turn):Boolean;
Begin
Emptyt:=(Q.begt=0 and Q.endt=0)
End;
Постановка в очередь
Procedure insertturn(var Q:turn;x:TE);
Begin
With Q do begin
If endt=n then endt:=1 else endtendt+1;
If begt=endt then writeln(‘очередь переполнена’); endt:=endt-1; exit end;
Mas[endt]:=x
End;
Процедура удаление первого элемента из очереди
Procedure removeturn(var Q:turn; var x:TE);
Begin
If empty(Q) then begin writeln(‘очередь пуста’); exit end;
With (Q) do begin
If begt=0 then begt:=1
Else begt:=begt+1
X:=mas[begt];
If begt:=endt then delturn
Третий способ реализации очереди.
Очередь реализуется в виде однонаправленного связного списка с заголовком, в котором запоминаются ссылки на 1 и последний узлы списка.
Type
Ptrknot=^knot;
Knot=record
Data:TE;
Next:ptrknot
End;
QUE=record
begQ,endQ:ptrknot
end;
очистка
procedure delq(var Q:que);
begin
Q.begq:=nil;
Q.endQ:=nil;
End;
Function emptyQ(var Q:que):Boolean;
Begin
Emptyq:=Q.endQ:nil
End;
Запись в очередь.
Procedure insertQ(var s:que;X:TE);
Var p:ptrknot;
Begin
New(p);
P^.data:=x;p^.next:=nil;
If Q.endQ=nil then Q.begQ:=p
Else Q.endQ^.next=p;
Q.endQ:=p;
End;
Процедура удаления из очереди.
Procedure removeQ (var Q:QUE;var x:TE);
Var P:ptrknot;
Begin
If emptyQ(Q) then writeln(‘очередь пуста’); exit end;
P:=Q.begQ;
X:=p^.data;
Q.begQ:=p^.next
If Q.begQ=nil then Q.endQ=nil;
Dispose(p);
End;
Реализация очереди с помощью циклического списка.
Для работы с очередью, реализованной циклическим списком, нужен только один указатель.
type ptrCQ = ^CircleQue;
TECQ = … ;
CircleQue = record
data: TECQ;
next: ptrCQ;
end;
var CQ: ptrCQ;
Процедура постановки элемента в очередь.
procedure InsertCQ(var CQ: ptrCQ; x: TECQ);
var p: ptrCQ;
begin
new(p);
p^.data := x;
if CQ = nil then CQ := p else p^.next := CQ^.next;
CQ^.next := p;
CQ := p;
end;
Процедура извлечения элемента из очереди.
procedure RemoveCQ(var CQ: ptrCQ; var x: TECQ);
var p: ptrCQ;
begin
if CQ = nil then begin
writeln(‘Очередь пуста.’);
exit;
end;
p := CQ^.next;
x := p^.data;
if p = CQ then CQ := nil else CQ^.next := p^.next;
dispose(p);
end;
Реализация стека.
Стек – это такая динамическая структура данных, которая организована по принципу «последним пришёл – первым ушёл» (LIFO). В отличие от очереди, в стеке доступен только один элемент.
Для работы со стеком необходимы следующие операции:
1) очистить стек;
2) проверить, является ли стек пустым;
3) записать элемент в стек;
4) извлечь элемент из стека.
Стек можно реализовать двумя способами:
1) с помощью массива;
2) с помощью списков.
Реализация стека с помощью массива.
Под стек отводится массив из n компонентов.
const n = … ;
type TES = … ;
STACK = record
HST: 0..n;
MST: array[1..n] of TES;
end;
var ST: STACK;
Процедура очистки стека или создания пустого стека.
procedure delSTACK(var ST: STACK);
begin
ST.HST := 0;
end;
Функция проверки, пуст ли стек.
function emptySTACK(var ST: STACK): boolean;
begin
emptySTACK := ST.HST = 0;
end;
Процедура записи в стек нового элемента.
procedure PushST(var ST: STACK; x: TES);
begin
with ST do begin
if HST = n then begin
writeln(‘Стек переполнен.’);
exit;
end;
HST := HST + 1;
MST[HST] := x;
end;
end;
Процедура извлечения из стека.
procedure POPST(var ST: STACK; var x: TES);
begin
with ST do begin
if emptySTACK(ST) then begin
writeln(‘Стек пуст.’);
exit;
end;
x := MST[HST];
HST := HST – 1;
end;
end;
Реализация стека с помощью связанного списка.
Для реализации стека может использоваться как линейный список, так и циклический. Последний введённый в стек элемент называется вершиной стека.
type TES = … ;
STACKL = ^Node;
Node = record
data: TES;
next: STACKL;
end;
Процедура записи в стек.
procedure PushSL(var SL: STACKL; x: TES);
var p: STACKL;
begin
new(p);
p^.data := x;
p^.next := SL;
SL := p;
end;
Процедура извлечения из стека.
procedure POPSL(var SL: STACKL; var x: TES);
var p: STACKL;
begin
if SL = nil then begin
writeln(‘Стек пуст.’);
exit;
end;
p := SL;
SL := p^.next;
x := p^.data;
dispose(p);
end;
Реализация стека циклическим списком.
Процедура записи в стек.
procedure PushSC(var STCL: STACKC; x: TES);
var p: STACKC;
begin
new(p);
p^.data := x;
if STCL = nil then STCL := p else p^.next := STCL^.next;
STCL^.next := p;
end;
Процедура извлечения из стека.
procedure POPSC(var STCL: STACKC; var x: TES);
var p: STACKC;
begin
if STCL = nil then begin
writeln(‘Стек пуст.’);
exit;
end;
p := STCL^.next;
x := p^.data;
if p = STCL then STCL := nil else STCL^.next := p^.next;
dispose(p);
end;
Стеки используются в компиляторах.
Задание: написать программу, проверяющую, правильно ли во введённом выражении расставлены скобки. Исходными данными для программы является строка, содержащая открывающие и закрывающие скобки из набора: { } ( ) [ ] < >.
Пример строки: {a * [c + x * (d – f)]}.
Подходящей структурой данных для решения задачи является стек. Как только встретили открывающую скобку, помещаем её в стек. Если встретилась закрывающая скобка, проверяем, парная ли она. Если парная, извлекаем соответствующую другую скобку из стека. Если непарная, расстановка скобок – неверная. Если скобки расставлены правильно, и стек пуст, итог – скобки расставлены правильно; если стек не пуст, то скобки расставлены неправильно. Необходимо также проверить, было ли занесение в стек. Если не было, то в строке нет скобок. Предусмотреть случай, когда сначала встречается закрывающая скобка. Если вначале встретилась закрывающая скобка, а стек пуст, расстановка скобок неверна. Стек реализовать списком.