Структура данных стек: шаблон класса Stack

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

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

Концептуально, структура данных — стек очень проста: она позволяет добавлять или удалять элементы в определенном порядке. Каждый раз, когда добавляется элемент, он попадает на вершину стека, единственный элемент, который может быть удален из стека — элемент, который находится на вершине стека. Таким образом, стек, как принято говорить, «первым пришел, последним ушел — FILO» или «последним пришел, первым ушел — LIFO». Первый элемент, добавленный в стек будет удален из него в последнюю очередь.

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

В некотором смысле, стеки являются частью фундаментального языка информатики. Когда вы хотите реализовать очередь типа — «первый пришел, последним ушел», то имеет смысл говорить о стеках с использованием общей терминологии. Кроме того, такие очереди участвуют во многих процессах, начиная от теоретических компьютерных наук, например функции push-down и многое другое.

Стеки имеют некоторые ассоциируемые методы:

Push — добавить элемент в стек;
Pop — удалить элемент из стека;
Peek — просмотреть элементы стека;
LIFO — поведение стека,
FILO Equivalent to LIFO

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

Этот стек был реализован с шаблонами, чтобы его можно было использовать практически для любых типов данных. Причем размер стека определяется динамически, во время выполнения программы. В стек добавлена также дополнительная функция: peek(), которая показывает n-й элемент от вершины стека.

#ifndef STACK_H
#define STACK_H

#include <cassert> // для assert
#include <iostream>

#include <iomanip> // для setw

template <typename T>
class Stack
{
private:
    T *stackPtr;                      // указатель на стек
    const int size;                   // максимальное количество элементов в стеке
    int top;                          // номер текущего элемента стека
public:
    Stack(int = 10);                  // по умолчанию размер стека равен 10 элементам
    Stack(const Stack<T> &);          // конструктор копирования
    ~Stack();                         // деструктор

    inline void push(const T & );     // поместить элемент в вершину стека
    inline T pop();                   // удалить элемент из вершины стека и вернуть его
    inline void printStack();         // вывод стека на экран
    inline const T &Peek(int ) const; // n-й элемент от вершины стека
    inline int getStackSize() const;  // получить размер стека
    inline T *getPtr() const;         // получить указатель на стек
    inline int getTop() const;        // получить номер текущего элемента в стеке
};

// реализация методов шаблона класса STack

// конструктор Стека
template <typename T>
Stack<T>::Stack(int maxSize) :
    size(maxSize) // инициализация константы
{
    stackPtr = new T[size]; // выделить память под стек
    top = 0; // инициализируем текущий элемент нулем;
}

// конструктор копирования
template <typename T>
Stack<T>::Stack(const Stack<T> & otherStack) :
    size(otherStack.getStackSize()) // инициализация константы
{
    stackPtr = new T[size]; // выделить память под новый стек
    top = otherStack.getTop();

    for(int ix = 0; ix < top; ix++)
        stackPtr[ix] = otherStack.getPtr()[ix];
}

// функция деструктора Стека
template <typename T>
Stack<T>::~Stack()
{
    delete [] stackPtr; // удаляем стек
}

// функция добавления элемента в стек
template <typename T>
inline void Stack<T>::push(const T &value)
{
    // проверяем размер стека
    assert(top < size); // номер текущего элемента должен быть меньше размера стека

    stackPtr[top++] = value; // помещаем элемент в стек
}

// функция удаления элемента из стека
template <typename T>
inline T Stack<T>::pop()
{
    // проверяем размер стека
    assert(top > 0); // номер текущего элемента должен быть больше 0

    stackPtr[--top]; // удаляем элемент из стека
}

// функция возвращает n-й элемент от вершины стека
template <class T>
inline const T &Stack<T>::Peek(int nom) const
{
  //
  assert(nom <= top);

  return stackPtr[top - nom]; // вернуть n-й элемент стека
}

// вывод стека на экран
template <typename T>
inline void Stack<T>::printStack()
{
    for (int ix = top - 1; ix >= 0; ix--)
        cout << "|" << setw(4) << stackPtr[ix] << endl;
}

// вернуть размер стека
template <typename T>
inline int Stack<T>::getStackSize() const
{
    return size;
}

// вернуть указатель на стек (для конструктора копирования)
template <typename T>
inline T *Stack<T>::getPtr() const
{
    return stackPtr;
}

// вернуть размер стека
template <typename T>
inline int Stack<T>::getTop() const
{
    return top;
}

#endif // STACK_H

Шаблон класса Stack реализован в отдельном *.h файле, да, именно реализован, я не ошибся. Все дело в том, что и интерфейс шаблона класса и реализация должны находиться в одном файле, иначе вы увидите список ошибок похожего содержания:

ошибка undefined reference to «метод шаблона класса»

Интерфейс шаблона класса объявлен с 9 по 28 строки. Все методы класса содержат комментарии и, на мой взгляд, описывать их работу отдельно не имеет смысла. Обратите внимание на то, что все методы шаблона класса Стек объявлены как inline функции. Это сделано для того, чтобы ускорить работу класса. Так как встроенные функции класса работают быстрее, чем внешние.

Сразу после интерфейса шаблона идет реализация методов класса Стек, строки 32 — 117. В реализации методов класса ничего сложного нет, если знать как устроен стек, шаблоны и классы. Заметьте, в классе есть два конструктора, первый объявлен в строках 32-33, — это конструктор по умолчанию. А вот конструктор в строках 41-5, — это конструктор копирования. Он нужен для того, чтобы скопировать один объект в другой. Метод Peek, строки 80 — 88 предоставляет возможность просматривать элементы стека. Необходимо просто ввести номер элемента, отсчет идет от вершины стека. Остальные функции являются служебными, то есть предназначены для использования внутри класса, конечно же кроме функции printStack(), она вывод элементы стека на экран.

Теперь посмотрим на драйвер для нашего стека, под драйвером я подразумеваю программу в которой тестируется работа класса. Как всегда это main функция, в которой мы и будем тестировать наш шаблон класса Stack. Смотрим код ниже:

#include <iostream>

using namespace std;

#include "stack.h"

int main()
{
    Stack<char> stackSymbol(5); 
    int ct = 0;
    char ch;

    while (ct++ < 5)
    {
        cin >> ch;
        stackSymbol.push(ch); // помещаем элементы в стек
    }

    cout << endl;

    stackSymbol.printStack(); // печать стека

    cout << "\n\nУдалим элемент из стека\n";
    stackSymbol.pop();

    stackSymbol.printStack(); // печать стека

    Stack<char> newStack(stackSymbol);

    cout << "\n\nСработал конструктор копирования!\n";
    newStack.printStack();

    cout << "Второй в очереди элемент: "<< newStack.Peek(2) << endl;

    return 0;
}

Создали объект стека, строка 9, размер стека при этом равен 5, то есть стек может поместить не более 5 элементов. Заполняем стек в цикле while, строки 13 — 17. В строке 21 выводим стек на экран, после удаляем один элемент из стека, строка 24 и снова выводим содержимое стека, поверьте оно изменилось, ровно на один элемент. Смотрим результат работы программы:

CppStudio.com

LOTR!

|   !
|   R
|   T
|   O
|   L

Удалим элемент из стека
|   R
|   T
|   O
|   L

Сработал конструктор копирования!
|   R
|   T
|   O
|   L
Второй в очереди элемент: T

В строке 28 мы воспользовались конструктором копирования, о том самом, о котором я писал выше. Не забудем про функцию peek(), давайте посмотри на второй элемент стека, строка 33.

На этом все! Стек у нас получился и исправно работает, попробуйте его протестировать, например на типе данных int. Я уверен, что все останется исправно работать.

#pragma once
#ifndef STACK_H
#define STACK_H

#include <cassert>
#include <iostream>
#include <iomanip>
#include <algorithm>

int const MaxSize = 10;

template <typename T>
class Stack {
private:
	T *stackPtr;
	const int size;
	int top;
public:
	Stack();
	Stack(const Stack<T> &);

	~Stack();

	Stack& operator=(Stack& s);
	inline void push(const T &);
	inline T pop();
	inline void printStack();
	inline const T &at(int) const;
	inline int getStackSize() const;
	inline T *getPtr() const;
	inline int getTop() const;
};

template <typename T>Stack<T>::Stack() :
	size(MaxSize) {
	stackPtr = new T[size];
	top = 0;
}

template <typename T>
Stack<T>::Stack(const Stack<T> & otherStack) :
	size(otherStack.getStackSize()) {
	stackPtr = new T[size];
	top = otherStack.getTop();

	for (int ix = 0; ix < top; ix++)
		stackPtr[ix] = otherStack.getPtr()[ix];
}

template <typename T>
Stack<T>::~Stack() {
	delete[] stackPtr;
}

template <typename T>
inline Stack<T>& Stack<T>::operator=(Stack& s) {
	if (this == &s) {
		return *this;
	}
	std::swap(s.stackPtr, stackPtr);
	std::swap(s.top, top);
	return *this;
}

template <typename T>
inline void Stack<T>::push(const T &value) {
	assert(top < size);
	stackPtr[top++] = value;
}

template <typename T>
inline T Stack<T>::pop() {
	assert(top > 0);
	return stackPtr[--top];
}

template <class T>
inline const T &Stack<T>::at(int nom) const {
	assert(nom <= top);
	return stackPtr[top - nom];
}

template <typename T>
inline void Stack<T>::printStack() {
	for (int ix = top - 1; ix >= 0; ix--)
		std::cout << "|" << std::setw(4) << stackPtr[ix] << std::endl;
}

template <typename T>
inline int Stack<T>::getStackSize() const {
	return size;
}

template <typename T>
inline T *Stack<T>::getPtr() const {
	return stackPtr;
}

template <typename T>
inline int Stack<T>::getTop() const {
	return top;
}

#endif

Ярослав Ерстенюк

14.01.2016

Спасибо за статью!

Но оператор присваивания надо либо явно запретить:

Stack& operator=(const Stack&) =delete;

либо добавить , типа(и включить <algorithm>):

//не проверял!
Stack& operator=(Stack s)//копирующая инициализация
{
    assert(s.getStackSize()==getStackSize());
    std::swap(s.stackPtr,stackPtr);
    std::swap(s.top,top);
}     //для s будет вызван деструктор

dleen
25.09.2014
и интерфейс шаблона класса и реализация должны находиться в одном файле

Почему?
Войдите, чтобы ответить
Дима
21.12.2013
Что значит size(maxSize) ?
Войдите, чтобы ответить
Дима
21.12.2013
И так же хотелось бы узнать,зачем употреблять const?
Войдите, чтобы ответить
Дима
21.12.2013
Не могли бы вы пояснить,к чему эти записи

#ifndef STACK_H
#define STACK_H
Войдите, чтобы ответить
- Уладзіслаў Вавілаў
  03.07.2015
  Это директивы препроцессора
  Войдите, чтобы ответить

Структура данных: стеки

Комментарии

Sergiro

Ярослав Ерстенюк

dleen

Дима

Дима

Дима

Уладзіслаў Вавілаў

Оставить комментарий