Структуры данных: стеки и очереди
Записи и оператор with
Записи используются для создания своих типов данных
{ Обьявление записи - тип "Точка" }
type
TPoint = Record
x,y : double;
end;
{ Функция, вычисляющая расстояние между точками }
function dist( A,B : TPoint ):double;
begin
dist := sqrt( (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y) );
end;
{ Использование записей }
var A,B : TPoint;
begin
{ Инициализируем координаты точек }
A.x := 1; A.y := 2;
B.x := 10; B.y := 11;
writeln( dist(A,B) );
end.
Использование with:
{ Обьявление записи - тип "Персонаж в игре" }
type
TUnit = Record
x,y : integer; { Координаты клетки где стоит персонаж }
name : string; { Имя персонажа }
end;
var Unit1 : TUnit;
{ Инициализация без with }
Unit1.x := 2;
Unit1.y := 3;
Unit1.name := 'SUPER-HERO';
{ Инициализация с with }
with Unit1 do begin
x := 2;
y := 3;
name := 'SUPER-HERO';
end;
Реализация Стека и Очереди на базе массива
Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
const StackSize = 10000; { Размер стека (сколько в него можно положить элементов) }
{ === Хранение стека === }
var
Stack : array [1..StackSize] of Integer; { Массив для хранения стека }
StackTop : Integer = 0; { Вершина стека - индекс в массиве Stack }
{ === Операции со стеком === }
{ Стек пуст? }
function isEmpty : Boolean;
begin
isEmpty := StackTop = 0;
end;
{ Положить значение на вершину стека }
procedure Push( Value : Integer );
begin
assert( StackTop < StackSize, 'Стек полон! Больше положить в него нельзя!');
Inc(StackTop);
Stack[StackTop] := Value;
end;
{ Забрать значение с вершины стека }
function Pop : Integer;
begin
assert( not isEmpty, 'Нельзя извлечь элемент, потому что стек пуст!');
Pop := Stack[StackTop];
Dec( StackTop );
end;
{ === Тестирование работы стека === }
begin
Writeln(isEmpty); { Выводит "TRUE" - стек пуст }
Push(2); { В стеке: 2 }
Writeln(isEmpty); { Выводит "FALSE" - стек не пуст }
Push(5); { В стеке: 2, 5 }
Writeln(Pop); { Выводит "5", в стеке: 2 }
Writeln(Pop); { Выводит "2", в стеке пусто }
end.
Реализация на Python
# Стек на массиве фиксированного размера: push, pop и проверка пустоты за O(1), память O(n).
class ArrayStack:
def __init__(self, capacity):
self.items = [0] * capacity
self.top = 0 # число элементов; items[top] - первая свободная ячейка
def is_empty(self):
return self.top == 0
def push(self, value):
if self.top == len(self.items):
raise OverflowError("стек полон")
self.items[self.top] = value
self.top += 1
def pop(self):
if self.is_empty():
raise IndexError("стек пуст")
self.top -= 1
return self.items[self.top]
def main():
stack = ArrayStack(3)
print(stack.is_empty()) # True
stack.push(2)
stack.push(5)
print(stack.pop()) # 5
print(stack.pop()) # 2
print(stack.is_empty()) # True
if __name__ == "__main__":
main()
Реализация на Rust
// Стек на массиве фиксированного размера: push, pop и проверка пустоты за O(1), память O(N).
pub struct ArrayStack<const N: usize> {
items: [i32; N],
top: usize, // число элементов; items[top] - первая свободная ячейка
}
impl<const N: usize> ArrayStack<N> {
pub fn new() -> Self {
ArrayStack { items: [0; N], top: 0 }
}
pub fn is_empty(&self) -> bool {
self.top == 0
}
// Возвращает false, если стек полон.
pub fn push(&mut self, value: i32) -> bool {
if self.top == N {
return false;
}
self.items[self.top] = value;
self.top += 1;
true
}
// Возвращает None, если стек пуст.
pub fn pop(&mut self) -> Option<i32> {
if self.is_empty() {
return None;
}
self.top -= 1;
Some(self.items[self.top])
}
}
fn main() {
let mut stack: ArrayStack<3> = ArrayStack::new();
println!("{}", stack.is_empty()); // true
stack.push(2);
stack.push(5);
println!("{:?}", stack.pop()); // Some(5)
println!("{:?}", stack.pop()); // Some(2)
println!("{}", stack.is_empty()); // true
}Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
const QSize = 10000; { Размер очереди (сколько в неё можно положить элементов) }
var
Q : array [1..QSize] of Integer; { Массив для хранения очереди }
Q_Start : Integer = 1; { Указывает на голову очереди }
Q_End : Integer = 1; { Указывает на элемент, который заполнится, когда в очередь войдёт новый элемент }
{ = Операции с очередью = }
{ Очередь пуста? }
function isEmpty : Boolean;
begin
isEmpty := Q_Start = Q_End;
end;
{ Положить значение в конец очереди }
procedure Put( Value : Integer );
begin
Q[Q_End] := Value;
Dec(Q_End);
{ Поддержка закольцованности очереди }
if Q_End < 1 then Q_End := QSize;
end;
{ Забрать значение с начала очереди }
function Get : Integer;
begin
assert( not isEmpty, 'В очереди ничего нет!');
Get := Q[Q_Start];
Dec(Q_Start);
{ Поддержка закольцованности очереди }
if Q_Start < 1 then Q_Start := QSize;
end;
begin
Writeln(isEmpty); { Выводит "TRUE" - очередь пуста }
Put(2); { В очереди: 2 }
Writeln(isEmpty); { Выводит "FALSE" - очередь не пуста }
Put(5); { В очереди: 5, 2 }
Writeln(Get); { Выводит "2", в очереди: 5 }
Writeln(Get); { Выводит "5", в очереди пусто }
end.
Реализация на Python
# Очередь на кольцевом массиве: enqueue и dequeue за O(1), память O(n).
class RingQueue:
def __init__(self, capacity):
self.items = [0] * capacity
self.head = 0 # индекс первого элемента
self.size = 0 # число элементов в очереди
def is_empty(self):
return self.size == 0
def enqueue(self, value):
if self.size == len(self.items):
raise OverflowError("очередь полна")
tail = (self.head + self.size) % len(self.items) # первая свободная ячейка
self.items[tail] = value
self.size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("очередь пуста")
value = self.items[self.head]
self.head = (self.head + 1) % len(self.items) # кольцо: после последней ячейки снова первая
self.size -= 1
return value
def main():
queue = RingQueue(3)
for value in [1, 2, 3]:
queue.enqueue(value)
print(queue.dequeue()) # 1
queue.enqueue(4) # занимает освободившуюся ячейку в начале массива
rest = []
while not queue.is_empty():
rest.append(queue.dequeue())
print(rest) # [2, 3, 4]
if __name__ == "__main__":
main()
Реализация на Rust
// Очередь на кольцевом массиве: enqueue и dequeue за O(1), память O(N).
pub struct RingQueue<const N: usize> {
items: [i32; N],
head: usize, // индекс первого элемента
size: usize, // число элементов в очереди
}
impl<const N: usize> RingQueue<N> {
pub fn new() -> Self {
RingQueue { items: [0; N], head: 0, size: 0 }
}
pub fn is_empty(&self) -> bool {
self.size == 0
}
// Возвращает false, если очередь полна.
pub fn enqueue(&mut self, value: i32) -> bool {
if self.size == N {
return false;
}
let tail = (self.head + self.size) % N; // первая свободная ячейка
self.items[tail] = value;
self.size += 1;
true
}
// Возвращает None, если очередь пуста.
pub fn dequeue(&mut self) -> Option<i32> {
if self.is_empty() {
return None;
}
let value = self.items[self.head];
self.head = (self.head + 1) % N; // кольцо: после последней ячейки снова первая
self.size -= 1;
Some(value)
}
}
fn main() {
let mut queue: RingQueue<3> = RingQueue::new();
for value in [1, 2, 3] {
queue.enqueue(value);
}
println!("{:?}", queue.dequeue()); // Some(1)
queue.enqueue(4); // занимает освободившуюся ячейку в начале массива
let mut rest = Vec::new();
while let Some(value) = queue.dequeue() {
rest.push(value);
}
println!("{:?}", rest); // [2, 3, 4]
}Реализация на C/C++
Реализация Стека
#include <iostream>
#include <assert.h>
using namespace std;
// Определение класса Стек
// Шаблон с двумя параметрами:
// T - тип элемента (например: int, char, char*)
// size - размер стека (целое число)
template <typename T,int size>
class Stack{
T data[size]; // Данные стека
int count; // Количество элементов в стеке
// count указывает на ячейку после последнего элемента в стеке
// Например, если count = 1, то последний элемент это data[0]
public:
// Конструктор
Stack(){ count = 0; };
// Стек пуст?
bool isEmpty(){
return count <= 0;
};
// Стек полон?
bool isFull(){
return count >= size;
};
// Добавить на вершину стека
void push(T value){
assert(!isFull()); // Можно добавить только если стек ещё не полон
data[count++] = value; // Записываем значение в массив и сдвигаем счётчик вправо
}
// Снять с вершины стека
T pop(){
assert(!isEmpty()); // Можно снять только если стек не пуст
return data[--count]; // Уменьшаем счётчик (сдвигаем влево) и возвращаем значение
}
};
// Основная программа - тестирование стека
int main() {
Stack<int,5> s; // Создаём пример стека
assert(s.isEmpty()); // Сейчас стек должен быть пустым
s.push(5); // Добавляем один элемент
assert(!s.isEmpty());
assert(s.pop() == 5);
assert(s.isEmpty());
assert(!s.isFull());
s.push(1); s.push(2); s.push(3);
s.push(4); assert(!s.isFull()); // Стек ещё не полон после добавления четвёртого элемента
s.push(5); assert(s.isFull());
Stack<char,2> cs; // Заводим другой пример стека - с символами в качестве элементов
cs.push('a');
return 0;
}
Реализация очереди (циклической очереди)
#include <iostream>
#include <assert.h>
using namespace std;
// Определение класса Очередь
// Шаблон с двумя параметрами:
// T - тип элемента (например: int, char, char*)
// size - размер очереди (целое число)
template <typename T,int size>
class Queue{
T data[size]; // Данные очереди
int head; // Голова очереди (первый элемент)
int tail; // Хвост очереди (последний элемент)
public:
// Конструктор
Queue(){ head = -1; tail = 0; };
// Очередь пуста?
bool isEmpty(){
return head < tail;
};
// Очередь полна?
bool isFull(){
return len() >= size;
};
// Текущая длина очереди
int len(){
return head-tail+1;
};
// Добавить в начало очереди
void put(T value){
assert(!isFull()); // Можно добавить только если очередь не полна
++head; // Сдвигаем голову вправо
data[head % size] = value; // Записываем в ячейку с номером по модулю
// -----------------------------------------
// | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
// -----------------------------------------
// Количество ячеек - 10, максимальный размер очереди - 10
// Куда должен пойти 10-ый элемент? На 0-ую позицию
// Куда должен пойти 20-ый элемент? Тоже на 0-ую позицию
// Цикличность очереди обепечивается тем, что мы индекс элемента всегда берём по модулю максимального размера очереди
}
// Взять из конца очереди
T get(){
assert(!isEmpty()); // Можно снять только если очередь не полна
return data[tail++ % size]; // Забираем значение из хвоста и двигаем хвост вправо
}
};
// Основная программа - тестирование стека
int main() {
Queue<int,5> s; // Создаём пример стека
assert(s.isEmpty()); // Сейчас очередь должна быть пуста
s.put(5); // Добавляем один элемент
assert(!s.isEmpty());
assert(s.get() == 5);
assert(s.isEmpty());
assert(!s.isFull());
s.put(1); s.put(2); s.put(3);
s.put(4); assert(!s.isFull());
s.put(5); assert(s.isFull());
return 0;
}