Стек

Теги: Стек, стек на си, реализация стека, стек на массиве, динамически растущий стек, стек на односвязном сиске

Стек

Стек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип LIFO (“Last in – first out”): последним зашёл – первым вышел. Или первым зашёл – последним вышел.

Стек позволяет хранить элементы и поддерживает, обычно, две базовые операции:

PUSH – кладёт элемент на вершину стека
POP – снимает элемент с вершины стека, перемещая вершину к следующему элементу

Также часто встречается операция PEEK, которая получает элемент на вершине стека, но не снимает его оттуда.

Стек является одной из базовых структур данных и используется не только в программировании, но и в схемотехнике, и просто в производстве, для реализации технологических процессов и т.д.; стек используется в качестве вспомогательной структуры данных во многих алгоритмах и в других более сложных структурах.

Пусть, например, у нас есть стек чисел. Выполним несколько команд. Изначально стек пуст. Вершина стека – указатель на первый элемент, никуда не указывает. В случае си она может быть равна NULL.

Push 3

Теперь стек состоит из одного элемента, числа 3. Вершина стека указывает на число 3.

Push 5

Стек состоит из двух элементов, 5 и 3, при этом вершина стека указывает на 5.

Push 7

Стек состоит из трёх элементов, вершина стека указывает на 7.

Pop

Вернёт значение 7, в стеке останется 5 и 3. Вершина будет указывать на следующий элемент – 5.

Pop

Вернёт 5, в стеке останется всего один элемент, 3, на который будет указывать вершина стека.

Pop

Вернёт 3, стек станет пуст.

Последовательное выполнение операций push 3, push 5, push 7, pop, pop, pop

Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.

Когда мы будем работать со стеком, возможны две основные и часто встречающиеся ошибки:

1. Stack Underflow: Попытка снять элемент с пустого стека
2. Stack Overflow: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)

Программная реализация

Рассмотрим три простые реализации стека:

1) Стек фиксированного размера на массиве
2) Динамически растущий стек на массиве
3) Динамически растущий стек на односвязном списке

Стек фиксированного размера, построенный на массиве

Отличительная особенность – простота реализации и максимальная скорость выполнения. Такой стек может применяться в том, случае, когда его максимальный размер известен заранее или известно, что он мал.

Сначала определяем максимальный размер массива и тип данных, которые будут в нём храниться:

#define STACK_MAX_SIZE 20
typedef int T;

Теперь сама структура

typedef struct Stack_tag {
	T data[STACK_MAX_SIZE];
	size_t size;
} Stack_t;

Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.

Кладём новый элемент на стек.

void push(Stack_t *stack, const T value) {
	stack->data[stack->size] = value;
	stack->size++;
}

Единственная проблема – можно выйти за пределы массива. Поэтому всегда надо проверять, чтобы не было ошибки Stack overflow:

#define STACK_OVERFLOW  -100
#define STACK_UNDERFLOW -101

void push(Stack_t *stack, const T value) {
	if (stack->size >= STACK_MAX_SIZE) {
		exit(STACK_OVERFLOW);
	}
	stack->data[stack->size] = value;
	stack->size++;
}

Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему

T pop(Stack_t *stack) {
	if (stack->size == 0) {
		exit(STACK_UNDERFLOW);
	}
	stack->size--;
	return stack->data[stack->size];
}

И функция peek, возвращающая текущий элемент с вершины

T peek(const Stack_t *stack) {
	if (stack->size <= 0) {
		exit(STACK_UNDERFLOW);
	}
	return stack->data[stack->size - 1];
}

Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение size

Вспомогательные функции для печати элементов стека

void printStackValue(const T value) {
	printf("%d", value);
}

void printStack(const Stack_t *stack, void (*printStackValue)(const T)) {
	int i;
	int len = stack->size - 1;
	printf("stack %d > ", stack->size);
	for (i = 0; i < len; i++) {
		printStackValue(stack->data[i]);
		printf(" | ");
	}
	if (stack->size != 0) {
		printStackValue(stack->data[i]);
	}
	printf("\n");
}

Заметьте, что в функции печати мы использует int, а не size_t, потому что значение len может стать отрицательным. Функция печатает сначала размер стека, а потом его содержимое, разделяя элементы символом |

Проверка

Stack_t stack;
stack.size = 0;

push(&stack, 3);
printStack(&stack, printStackValue);
push(&stack, 5);
printStack(&stack, printStackValue);
push(&stack, 7);
printStack(&stack, printStackValue);
printf("%d\n", pop(&stack));
printStack(&stack, printStackValue);
printf("%d\n", pop(&stack));
printStack(&stack, printStackValue);
printf("%d\n", pop(&stack));
printStack(&stack, printStackValue);
_getch();

Рассмотрим также ситуации, когда есть ошибки использования. Underflow

void main() {
	Stack_t stack;
	stack.size = 0;

	push(&stack, 3);
	pop(&stack);
	pop(&stack);
	_getch();
}

Overflow

void main() {
	Stack_t stack;
	size_t i;
	stack.size = 0;

	for (i = 0; i < 100; i++) {
		push(&stack, i);
	}
	_getch();
}

Динамически растущий стек на массиве

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

Стек будет состоять из указателя на данные, размера массива (максимального), и числа элементов в массиве. Это число также будет и указывать на вершину.

typedef struct Stack_tag {
	T *data;
	size_t size;
	size_t top;
} Stack_t;

Для начала понадобится некоторый начальный размер массива, пусть он будет равен 10

#define INIT_SIZE 10

Алгоритм работы такой: мы проверяем, не превысило ли значение top значение size. Если значение превышено, то увеличиваем размер массива. Здесь возможно несколько вариантов того, как увеличивать массив. Можно прибавлять число, можно умножать на какое-то значение. Какой из вариантов лучше, зависит от специфики задачи. В нашем случае будем умножать размер на число MULTIPLIER

#define MULTIPLIER 2

Максимального размера задавать не будем. Программа будет выпадать при stack overflow или stack underflow. Будем реализовывать тот же интерфейс (pop, push, peek). Кроме того, так как массив динамический, сделаем некоторые вспомогательные функции, чтобы создавать стек, удалять его и чистить.

Во-первых, функции для создания и удаления стека и несколько ошибок

#define STACK_OVERFLOW  -100
#define STACK_UNDERFLOW -101
#define OUT_OF_MEMORY   -102
Stack_t* createStack() {
	Stack_t *out = NULL;
	out = malloc(sizeof(Stack_t));
	if (out == NULL) {
		exit(OUT_OF_MEMORY);
	}
	out->size = INIT_SIZE;
	out->data = malloc(out->size * sizeof(T));
	if (out->data == NULL) {
		free(out);
		exit(OUT_OF_MEMORY);
	}
	out->top = 0;
	return out;
}

void deleteStack(Stack_t **stack) {
	free((*stack)->data);
	free(*stack);
	*stack = NULL;
}

Всё крайне просто и понятно, нет никаких подвохов. Создаём стек с начальной длиной и обнуляем значения.

Теперь напишем вспомогательную функцию изменения размера.

void resize(Stack_t *stack) {
	stack->size *= MULTIPLIER;
	stack->data = realloc(stack->data, stack->size * sizeof(T));
	if (stack->data == NULL) {
		exit(STACK_OVERFLOW);
	}
}

Здесь, заметим, в случае, если не удалось выделить достаточно памяти, будет произведён выход с STACK_OVERFLOW.

Функция push проверяет, вышли ли мы за пределы массива. Если да, то увеличиваем его размер

void push(Stack_t *stack, T value) {
	if (stack->top >= stack->size) {
		resize(stack);
	}
	stack->data[stack->top] = value;
	stack->top++;
}

Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера

T pop(Stack_t *stack) {
	if (stack->top == 0) {
		exit(STACK_UNDERFLOW);
	}
	stack->top--;
	return stack->data[stack->top];
}
T peek(const Stack_t *stack) {
	if (stack->top <= 0) {
		exit(STACK_UNDERFLOW);
	}
	return stack->data[stack->top - 1];
}

Проверим

void main() {
	int i;
	Stack_t *s = createStack();

	for (i = 0; i < 300; i++) {
		push(s, i);
	}
	for (i = 0; i < 300; i++) {
		printf("%d ", peek(s));
		printf("%d ", pop(s));
	}

	deleteStack(&s);
	_getch();
}

Напишем ещё одну функцию, implode, которая уменьшает массив до размера, равного числу элементов в массиве. Она может быть использована тогда, когда уже известно, что больше элементов вставлено не будет, и память может быть частично освобождена.

void implode(Stack_t *stack) {
	stack->size = stack->top;
	stack->data = realloc(stack->data, stack->size * sizeof(T));
}

Можем использовать в нашем случае

for (i = 0; i < 300; i++) {
	push(s, i);
}
implode(s);
for (i = 0; i < 300; i++) {
	printf("%d ", peek(s));
	printf("%d ", pop(s));
}

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

У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 2 раза (в нашем случае) требуется мало обращений к памяти, но при этом каждое последующее увеличение может привести к ошибке, особенно при маленьком количестве памяти в системе. Если же использовать более щадящий способ выделения памяти (например, каждый раз прибавлять по 10), то число обращений увеличится и скорость упадёт. На сегодня, проблем с размером памяти обычно нет, а менеджеры памяти и сборщики мусора (которых нет в си) работают быстро, так что агрессивное изменение преобладает (на примере, скажем, реализации всей стандартной библиотеки языка Java).

Реализация стека на односвязном списке

Что такое односвязный список, будет подробнее рассказано дальше. Коротко: односвязный список состоит из узлов, каждый из которых содержит полезную информацию и ссылку на следующий узел. Последний узел ссылается на NULL.

Никакого максимального и минимального размеров у нас не будет (хотя в общем случае может быть). Каждый новый элемент создаётся заново. Для начала определим структуру узел

#define STACK_OVERFLOW  -100
#define STACK_UNDERFLOW -101
#define OUT_OF_MEMORY   -102

typedef int T;
typedef struct Node_tag {
	T value;
	struct Node_tag *next;
} Node_t;

Функция вставки первого элемента проста: создаём новый узел. Указатель next кидаем на старый узел. Далее указатель на вершину стека перекидываем на вновь созданный узел. Теперь вершина стека указывает на новый узел.

void push(Node_t **head, T value) {
	Node_t *tmp = malloc(sizeof(Node_t));
if (tmp == NULL) {
		exit(STACK_OVERFLOW);
	}
	tmp->next = *head;
	tmp->value = value;
	*head = tmp;
}

Функция pop берёт первый элемент (тот, на который указывает вершина), перекидывает указатель на следующий элемент и возвращает первый. Здесь есть два варианта – можно вернуть узел или значение. Если вернём значение, то придётся удалять узел внутри функции

Node_t* pop1(Node_t **head) {
	Node_t *out;
	if ((*head) == NULL) {
		exit(STACK_UNDERFLOW);
	}
	out = *head;
	*head = (*head)->next;
	return out;
}

T pop2(Node_t **head) {
	Node_t *out;
	T value;
	if (*head == NULL) {
		exit(STACK_UNDERFLOW);
	}
	out = *head;
	*head = (*head)->next;
	value = out->value;
	free(out);
	return value;
}

Теперь вместо проверки на длину массива везде используется проверка на равенство NULL вершины стека.

Простая функция peek

T peek(const Node_t* head) {
	if (head == NULL) {
		exit(STACK_UNDERFLOW);
	}
	return head->value;
}

Итерирование достаточно интересное. Просто переходим от одного узла к другому, пока не дойдём до конца

void printStack(const Node_t* head) {
	printf("stack >");
	while (head) {
		printf("%d ", head->value);
		head = head->next;
	}
}

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

size_t getSize(const Node_t *head) {
	size_t size = 0;
	while (head) {
		size++;
		head = head->next;
	}
	return size;
}

Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.

Тестируем

void main() {
	int i;
	Node_t *head = NULL;
	for (i = 0; i < 300; i++) {
		push(&head, i);
	}
	printf("size = %d\n", getSize(head));
	while (head) {
		printf("%d ", peek(head));
		printf("%d ", pop2(&head));
	}
	_getch();
}

или так

void main() {
	int i;
	Node_t *head = NULL;
	Node_t *tmp;
	for (i = 0; i < 300; i++) {
		push(&head, i);
	}
	printf("size = %d\n", getSize(head));
	while (head) {
		printf("%d ", peek(head));
		tmp = pop1(&head);		
		printf("%d ", tmp->value);
		free(tmp);
	}
	_getch();
}

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

Оглавление

Базовые операции. Сортировка слиянием