Стек на односвязном линейном списке

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

План действий

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

Для работы со стеком нужно реализовать пять функций:

  1. Инициализация
  2. Включение элемента
  3. Исключение элемента
  4. Проверка на пустоту
  5. Удаление стека

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

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

Файл Stack_List.h

/****************************************/
/*			Стек на списке				*/
/****************************************/
#ifndef _STACK_LIST_H_
#define _STACK_LIST_H_
#include "List_One.h"
/*Описание исключительных ситуаций*/
const int stackListOk = listOneOK;
const int stackListEmpty = listOneEmpty;
const int stackListNoMem = listOneNoMem;
/**********************************/
/*Переменная ошибок*/
extern int listOneError;
/*Базовый тип стека на списке*/
typedef listOneBaseType stackListBaseType;
/*Тип стека на списке*/
typedef ListOne StackList;
/*Функции работы со стеком*/
void initStackList(StackList *S);						// Инициализация стека
void putStackList(StackList *S, stackListBaseType E);	// Включение в стек
void getStackList(StackList *S, stackListBaseType *E);	// Исключение из стека
void doneStackList(StackList *L);						// Удаление стека
int isEmptyStackList(StackList *S);						// Предикат: пуст ли стек
/**************************/
#endif

Файл Stack_List.c

/****************************************/
/*			Стек на списке				*/
/****************************************/
#include "Stack_List.h"
#include "List_One.h"
/*Инициализация стека*/
void initStackList(StackList *S) {
initListOne(S);
listOneError = stackListOk;
}
/*Включение в стек*/
void putStackList(StackList *S, stackListBaseType E) {
putListOne(S, E);
}
/*Исключение из стека*/
void getStackList(StackList *S, stackListBaseType *E) {
getListOne(S, E);
}
/*Удаление стека*/
void doneStackList(StackList *L) {
doneListOne(L);
}
/*Предикат: пуст ли стек*/
int isEmptyStackList(StackList *S) {
return isEmptyListOne(S);
}

Как видите, реализация оказалась не такой уж и сложной. В заголовочном файле стека подключается список, благодаря чему мы имеем возможность пользоваться всеми его функциями. Также следует отметить, что для стека мы не создаем переменную ошибок, а используем listOneError, которая определена в списке. Таким образом, если при работе со списком произойдет какая-либо ошибка, мы о ней будем знать.

На этом все, если у Вас возникли вопросы, можете задавать их в комментариях.

2 отзыва на “Стек на односвязном линейном списке

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

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