Изменения

Перейти к: навигация, поиск

Стек

229 байт убрано, 21:38, 11 июня 2012
м
На саморасширяющемся массиве
<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции $push$ Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в $pop$, перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
struct vector int size, n int* v int* w vectorpop() size = 1 n = 0 v = new int[1] pop() int r = *(v + n) n-- if (n < size / 4) w = new int[size / 2] for i = 0..size / 4 w[i] = v[i] delete[] v v = w size = size / 2 return v[r] push(e) if (n == s - 1) w = new int[s * 2] for i = 0..s w[i] = v[i] delete[] v v = w s = s * 2 n++ v[n] = e
</wikitex>
285
правок

Навигация