Стеки. Пользовательская реализация стека

   
На этом шаге мы приведем пользовательскую реализацию стека.

   
Стандартный класс stack<> ставит на первое место не удобство и безопасность, а скорость работы. Поэтому вашему вниманию
предлагается нестандартная реализация стека. Она обладает двумя преимуществами:

  • функция рор() возвращает верхний элемент;
  • при пустом стеке функции рор() и top() генерируют исключения.

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

// ************************************************************
// *  Stack.hpp
// *   - более удобный и безопасный класс стека
// * ************************************************************
#ifndef STACK_HPP
#define STACK_HPP

#include <deque>
#include <exception>

template <class T>
class Stack {
  protected:
    std::deque<T> c;        // Контейнер для хранения элементов

  public:
    /* Класс исключения, генерируемого функциями pop() и top()
     * при пустом стеке
     */
    class ReadEmptyStack : public std::exception {
      public:
        virtual const char* what() const throw() {
            return "read empty stack";
        }
    };
  
    // Количество элементов
    typename std::deque<T>::size_type size() const {
        return c.size();
    }

    // Проверка пустого стека
    bool empty() const {
        return c.empty();
    }

    // Занесение элемента в стек
    void push (const T& elem) {
        c.push_back(elem);
    }

    // Извлечение элемента из стека с возвращением его значения
    T pop () {
        if (c.empty()) {
            throw ReadEmptyStack();
        }
        T elem(c.back());
        c.pop_back();
        return elem;
    }

    // Получение значения верхнего элемента
    T& top () {
        if (c.empty()) {
            throw ReadEmptyStack();
        }
        return c.back();
    }
};

#endif // STACK_HPP 

   
При использовании этого класса стека пример из 329 шага можно записать в следующем виде:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include <iostream>
#include "Stack.hpp" // Использование нестандартного класса стека

#include <conio.h>   //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{

 try {
    Stack<int> st;

    // Занесение трех элементов в стек
    st.push(1);
    st.push(2);
    st.push(3);

    // Извлечение и вывод двух элементов из стека
    cout << ToRus("Извлечение и вывод двух элементов из стека: \n");
    cout << st.pop() << ' ';
    cout << st.pop() << ' ';
    cout << endl;

    // Модификация верхнего элемента
    st.top() = 77;

    // Занесение двух новых элементов
    st.push(4);
    st.push(5);

    // Извлечение одного элемента без обработки
    st.pop();

    // Извлечение и вывод трех элементов
    //    - ОШИБКА: одного элемента не хватает

    cout << ToRus("Извлечение и вывод трех элементов:\n");
    cout << st.pop() << ' ';
    cout << st.pop() << endl;
    cout << st.pop() << endl;
   }
  catch (const exception& e) {
     cerr << "EXCEPTION: " << e.what() << endl;
  }

  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

   
При последнем вызове рор() намеренно допущена ошибка. В отличие от стандартного класса стека с неопределенным поведением
наш класс генерирует исключение. Результат выполнения программы выглядит так:


Рис.1. Результат работы приложения

   
Со следующего шага мы начнем рассматривать очереди.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

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