В данной статье рассмотрим такую элементарную структуру данных, как стек. Стек представляет собой динамическое множество, элементы которого добавляются и удаляются в соответствии со стратегией LIFO (last-in, first-out): первым из стека удаляется элемент, который был помещен туда последним. В программах, например, стек используется для работы с автоматическими переменными. По мере появления автоматические переменные добавляются в вершину стека. Когда их действие прекращается, они удаляются из стека.
Опишем основные свойства и операции стека в общем виде. Стек содержит определенное количество элементов, что делает его контейнером. Значит, его можно реализовать с помощью массива elements с количеством элементов STACK_SIZE. Дополнительно задаются атрибуты topIndex и topElement, представляющие индекс последнего помещенного в стек элемента и сам этот элемент соответственно. Если значение topIndex равно 0, то стек не содержит ни одного элемента и является пустым. Проверить стек на наличие в нем элементов можно с помощью операции isEmpty. Если производится попытка снять элемент с пустого стека, то это приводит к ошибке underflow (опустошение). Если значение topIndex равно STACK_SIZE, то стек переполняется, что приводит к ошибке overflow. Эта проверка осуществляется с помощью операции isFull.
Операция вставки элемента производится функцией PUSH (запись в стек), а операция удаления — функцией POP (снятие верхнего элемента со стека).
Существует множество эффективных способов реализации стеков. В данной статье рассмотрим объектно-ориентированный подход.
В разделе private класса Stack инкапсулируется способ представления данных (обычный массив, динамический, связный список, …). В данный момент ограничимся обычным массивом из STACK_SIZE элементов (константа, специфичная для класса, объявлена в 24 строке, см. листинг 1). В дальнейшем можно легко заменить его на динамический без внесения изменений в общедоступный (public) интерфейс класса.
Функции pop() и push() возвращают информацию о состоянии стека (пуст или заполнен), поэтому объявлены как bool, a не void. Таким образом, программист имеет возможность обработки ситуаций переполнения и очистки стека. Фактически, проверку переполнения и опустошения стека выполняют функции isFull и isEmpty, которые объявлены в разделе private.
Вместо того чтобы давать определение стека на основе конкретного типа данных (int, double, …), мы его опишем на базе обобщенного типа StackElement с использованием спецификатора typedef. Конечно, более правильным вариантом было бы использование шаблонов класса, но в данной статье мы пока их рассматривать не будем.
Далее представлен код на C++
Листинг 1. Файл Stack.h
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
typedef int StackElement;
class Stack
{
public:
Stack(); //default constructor
~Stack(); // destructor
/*inserts a new element to stack,
returns true if it is possible */
bool push(const StackElement & element);
/* deletes a top element from the stack,
returns true if it is possible*/
bool pop();
/* returns top element of stack*/
StackElement getTopElement() const;
private:
/* size of stack, constant */
enum {STACK_SIZE = 5};
StackElement elements[STACK_SIZE];
/* index of top element*/
int topIndex;
/* value of the top element*/
StackElement topElement;
/* checks if stack is empty */
bool isEmpty() const;
/* checks if stack is full */
bool isFull() const;
};
#endif
Листинг 2. Файл Stack.cpp
#include "stack.h"
Stack::Stack()
{
topIndex = 0;
}
Stack::~Stack(){}
bool Stack::isEmpty() const
{
return topIndex == 0;
}
bool Stack::isFull() const
{
return topIndex == STACK_SIZE;
}
bool Stack::push(const StackElement & element)
{
if (!isFull())
{
elements[topIndex++] = element;
topElement = elements[topIndex];
return true;
}
return false;
}
bool Stack::pop()
{
if (!isEmpty())
{
topElement = elements[--topIndex];
return true;
}
return false;
}
StackElement Stack::getTopElement() const
{
return topElement;
}
Листинг 3. Файл main.cpp
#include <iostream>
#include <cctype>
using namespace std;
#include "stack.h"
int main()
{
char ch;
int elem;
Stack stack;
cout<<"Enter 'I' to insert element to stack, \n"
<<"'D' to delete element from stack, \n"
<<"'Q' to quit\n";
while(cin>>ch && toupper(ch) != 'Q')
{
switch(ch)
{
case 'I' :
case 'i' : cout<< "Enter element to insert:\n";
cin>>elem;
if (stack.push(elem))
{
cout<<"Element "<<elem<<" is inserted to stack.\n";
}
else
{
cout<<"Stack overflow!\n";
}
break;
case 'D' :
case 'd' :
if (stack.pop())
{
cout<<"Element "<<stack.getTopElement()<<" is deleted from stack.\n";
}
else
{
cout<<"Stack underflow!\n";
}
break;
}
}
return 0;
}
Литература:
1) Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ.
2) С. Прата. Язык программирования С++. Лекции и упражнения.
dantkz
Viktor
Maksat Maratov
botique
