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

При написании различных программ программисты пользуются различными структурами данных, некоторые из них — встроенные (те, которые предлагает тот или иной язык программирования), другие же — производные, те, которые создает сам программист. Сегодня пойдет речь о производных структурах, а именно о стеке.

Определение стека

Стек — последовательность, в которой включение и исключение элементов осуществляется с одной стороны этой последовательности.

Стек является структурой типа LIFO (от англ. Last In, Firts Out, "Последним пришел - первым ушел"). Чтобы лучше понять, что такое стек, давайте представим, что у нас есть пять тарелок с номерами 1, 2, 3, 4, 5. Теперь мы складываем их в стопку в порядке возрастания номеров. То есть, самой нижней тарелкой будет являться тарелка с номером 1, а самой верхней — с номером 5. Получается, что тарелка № 5 вошла в стопку последней, однако когда нам понадобится несколько тарелок из этой стопки, то именно пятую мы возьмем первой.

Реализация стека

Стек можно реализовать по-разному, на массиве, списке, и т.д. В этой статье рассмотрим стек на массиве. Реализация производится на языке C.

Первым делом напишем наш заголовочный файл, который назовем StackArray.h

/****************************************/
/*			Стек на массиве				*/
/****************************************/
#ifndef _STACK_ARRAY_H_
#define _STACK_ARRAY_H_
/*Размер стека*/
#define SIZE_STACK_ARRAY 100
/*Описание исключительных ситуаций*/
const int okStackArray = 0;											// Все нормально
const int fullStackArray = 1;										// Стек переполнен
const int emptyStackArray = 2;										// Стек пуст
/*********************************/
/*Переменная ошибок*/
extern int errorStackArray;
/*Базовый тип стека*/
typedef int stackArrayBaseType;
/*Дескриптор стека*/
typedef struct {
stackArrayBaseType buf[SIZE_STACK_ARRAY];						// Буфер стека
unsigned uk;													// Указатель
} StackArray;
/******************/
/*Функции работы со стеком*/
void initStackArray(StackArray *S);									// Инициализация стека
void putStackArray(StackArray *S, stackArrayBaseType E);			// Включение в стек
void getStackArray(StackArray *S, stackArrayBaseType *E);			// Исключение из стека
int isFullStackArray(StackArray *S);								// Предикат: полон ли стек
int isEmptyStackArray(StackArray *S);								// Предикат: пуст ли стек
/**************************/
#endif

Здесь мы сначала задаем максимальный размер стека, затем константы, описывающие исключительные ситуации, и переменную ошибок. Для чего это? Спросите вы. Все просто! В процессе работы со стеком могут случиться различные ситуации: переполнение массива, либо обращение к несуществующему элементу стека. Именно переменная ошибок, равная okStackArray, и будет являться признаком того, что ошибок не было.

Теперь напишем реализации функций работы со стеком.

/****************************************/
/*			Стек на массиве				*/
/****************************************/
#include <stdio.h>
#include "Stack_Array.h"
/*Переменная ошибок*/
int errorStackArray;
/*Инициализация стека*/
void initStackArray(StackArray *S) {
S->uk = 0;
errorStackArray = okStackArray;
}
/*Включение в стек*/
void putStackArray(StackArray *S, stackArrayBaseType E) {
/*Если стек переполнен*/
if (isFullStackArray(S)) {
return;
}
/*Иначе*/
S->buf[S->uk] = E;				// Включение элемента
S->uk++;							 	// Сдвиг указателя
}
/*Исключение из стека*/
void getStackArray(StackArray *S, stackArrayBaseType *E) {
/*Если стек пуст*/
if (isEmptyStackArray(S)) {
return;
}
/*Иначе*/
*E = S->buf[S->uk - 1];		// Считывание элемента в переменную
S->uk--;							 	// Сдвиг указателя
}
/*Предикат: полон ли стек*/
int isFullStackArray(StackArray *S) {
if (S->uk == SIZE_STACK_ARRAY) {
errorStackArray = fullStackArray;
return 1;
}
return 0;
}
/*Предикат: пуст ли стек*/
int isEmptyStackArray(StackArray *S) {
if (S->uk == 0) {
errorStackArray = emptyStackArray;
return 1;
}
return 0;
}

Ну вот и все. Стек готов. Можно смело им пользоваться Реализация стека на массиве (C, Массив, Стек) Вот пример программы.

#include <stdio.h>
#include <locale.h>
#include "Stack_Array.h"
int main() {
setlocale(LC_CTYPE, "");
/*Тестирование стека*/
puts("Стек на массиве");
StackArray S;
stackArrayBaseType a;
initStackArray(&S);
putStackArray(&S, 10);
putStackArray(&S, 15);
puts("\tВвели: 10, 15\n\tВывод: ");
getStackArray(&S, &a);
printf("%d ", a);
getStackArray(&S, &a);
printf("%d", a);
return 0;
}

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *