Домой Софт Мастерская Лирика ЧаВО Юмор E-Mail ICQ статус 197-577-902

Лекции по информатике - Стек (stack)

Общая информация

Стек (stack) - это динамическая структура данных с последовательным доступом. Доступ к элементам стека осуществляется следующим образом, элементы из стека можно доставать только в порядке, обратном порядку добавления их в стек.

Рис. 1. Стек (stack)

Примерами стеков могут служить:

  1. обыкновенная детская пирамидка: большое колечко, которое было надето раньше, нельзя снять, не сняв маленькое, которое было надето позже;
  2. железнодорожный тупик: вагон нельзя выгнать из тупика, не выгнав предварительно вагон, который был загнан позже;
  3. труба с одним запаянным концом, куда помещают разноцветные бочонки.

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

Работа стека организована по принципу LIFO (Last In First Out) - последним пришел, первым ушел.

Элемент стека, который в данный момент можно взять, т.е. верхний, называется вершиной стека. Если число элементов в стеке не может превышать некоторой величины, то стек называют ограниченным, а максимальное число элементов в нем - глубиной стека.

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

Приведем пример реализации неограниченного стека целых чисел основанного на односвязном списке.

Содержание файла stack.h:

#ifndef STACK_H
#define STACK_H

#include <iostream.h>
#include <malloc.h>

/*
** Класс "Стек целых чисел" на основе односвязного списка
*/

typedef int stackdata; // элемент стека
                       // изменяя это объявление вы легко
                       // можете получить стек других типов
                       // например, структур, классов, символов. 

// элемент односвязного списка
struct listitem
{
  stackdata data; // данные
  listitem* next; // указатель на следующий элемент списка
};

// Класс исключений для CStack
class EStack
{
  private:
    char* msg; // сообщение об ошибке
  public:
    EStack(const char* errmsg) { msg = strdup(errmsg); }
    ~EStack() { free(msg); }
    const char* getmsg() { return msg; }
};

class CStack
{
  private:
    listitem* head; // голова односвязного списка

  public:
    CStack();                              // конструктор
    CStack(const CStack&);                 // конструктор копирования
    ~CStack() { clear(); }                 // деструктор 
    bool empty() const { return head==0; } // стек пуст?
      // здесь применена так называеся технология inline
      // везде где будет стоять вызов метода empty()
      // компилятор вместо вызова процедуры "вшьет" данный код
      // в место вызова. Это увеличивает производительность,
      // т.к. на вызов любой подпрограммы требуется дополнительное время.
      // Однако не следует злоупотреблять inline подстановкой - ее нужно
      // использовать только для маленьких функций/методов.

    CStack& clear();                       // очистить стек 
    CStack& push(const stackdata& data);   // добавить элемент в стек
    stackdata pop();                       // извлечь элемент из стека 
    const stackdata& see() const;          // посмотреть элемент в вершине стека
    CStack& operator = (const CStack&);    // оператор присваивания
    friend ostream& operator << (ostream&, const CStack&);
      // Оператор вывода стека в поток
};

// конструктор стека
CStack::CStack()
{
  head = 0;
}

CStack::CStack(const CStack& stack)
{
  head = 0;
  *this = stack;
}

CStack& CStack::clear()
{
  while(head)
  {
    listitem* temp = head->next;
    delete head;
    head = temp;
  }
  return *this;
}

CStack& CStack::push(const stackdata& data)
  // Этот метод добавляет указанный элемент в вершину стека и
  // в качестве результата возвращает ссылку на экземпляр стека.
  // В принципе можно было бы просто обойтись void. Но
  // тогда был бы невозможен следующий вызов:
  //   stack2 = stack1.push(10)
  // или такой:
  //   stack1.push(1).push(2).push(3)
  //
  // Также обратите внимание на то, как объявлен параметр data:
  //   const stackdata& data, т.е. по ссылке
  // В нашем случае (стек целых чисел) это лишнее, т.к. никакого
  // выйгрыша от этого нет. Но если вы захотите сделать стек из более 
  // рерурсоемких структур, то имеенно так и нужно делать, т.к.
  // иначе при вызове метода будет создаваться копия объекта (структуры,
  // класса, и т.п.)
{
  listitem* item = new listitem;
  item->data = data;
  item->next = head;
  head = item;
    // Здесь мы выделили память под новый элемент односвязного
    // списка, скопировали данные, и сделали новый элемент списка
    // его головой - вершиной стека.
  
  return *this;
}

stackdata CStack::pop()
  // Извлекает элемент из вершины стека
  // Если стек пуст, то генерирует исключительную ситуацию
{
  if(empty()) throw (EStack("Stack is empty"));

  listitem* old = head;
  head = head->next;                 // сдвигаем вершину стека
  stackdata data = old->data;
  delete old;                        // удаляем старую вершину
  return data;
}

const stackdata& CStack::see() const
{
  if(empty()) throw (EStack("Stack is empty"));
  return head->data;  
}

CStack& CStack::operator = (const CStack& stack)
{
  if (this == &stack) return *this;
    // Игнорируем попытку присвоить стек самому себе
  clear();
  if(!stack.empty())
  {
    head = new listitem;
    listitem* cur = head;
    listitem* src = stack.head;
    while(src)
    {
      cur->data = src->data;
      if(src->next)
      {
        cur->next = new listitem;
        cur = cur->next;
      } else
        cur->next = 0;
      src = src->next;
    }
  }
  return *this;
}

ostream& operator << (ostream& s, const CStack& stack)
{
  listitem* item = stack.head;
  while(item)
  {
    s << item->data << endl;
    item = item->next;
  }
  return s;
}

#endif

Реализация шаблона "Стек"

Шаблон - это заготовка для класса, параметризованный класс. Наш шаблон "Стек" будет иметь один параметр - тип данных из которых будет состоять стек. Используя шаблон легко объявить стеки совершенно произвольных типов данных:

#include "stacktemplate.h"
int main()

{
  stack<int> IntStack; // стек целых чисел
  stack<char> CharStack; // стек символов
  return 0;
}

Т.к. мы уже имеем готовый класс "стек целых чисел", то его легко переделать в шаблон "Стек".

Содержание файла stacktemplate.h:

#ifndef STACKTAMPLATE_H
#define STACKTAMPLATE_H

/*
** Public Domain
** Copyrights (c) 2004 Slava Antonov
** http://slava.users.otts.ru
*/

#include <iostream.h>
#include <malloc.h>

// Класс исслючений для стека
class EStack
{
  private:
    char* msg;  // сообщение об ошибке
  public:
    EStack(const char* errmsg) { msg = strdup(errmsg); }
    ~EStack() { free(msg); }
    const char* getmsg() { return msg; }
};

// Сообщения об ошибках
#define ESTACK_EMPTY "Stack is empty"

// Шаблон элемента односвязного списка
template <class T>
struct l1item
{
  T data;
  l1item<T>* next;
};

// Шаблон стека на основе односвязного списка
template <class T>
class stack
{
  private:
    l1item<T>* head; // голова односвязного списка

  public:
    stack() { head = NULL; }                   // конструктор
    stack(const stack<T>&);                    // конструктор копирования
    ~stack() { clear(); }                      // деструктор 
    bool empty() const { return head==NULL; }  // стек пуст?
    stack<T>& clear();                         // очистить стек 
    stack<T>& del();                           // удалить элемент из стека
    stack<T>& push(const T& data);             // добавить элемент в стек
    T pop();                                   // извлечь элемент из стека 
    const T& see() const;                      // посмотреть элемент в вершине стека
    stack<T>& operator = (const stack<T>&);    // оператор присваивания
};

// Конструктор копирования
template <class T>
stack<T>::stack(const stack<T>& Stack)
{
  head = NULL;
  *this = Stack;
}

// Очистка стека (удаление всех элементов)
template <class T>
stack<T>& stack<T>::clear()
{
  while(!empty()) del();
  return *this;
}

// Удаление элемента из вершины стека
template <class T>
stack<T>& stack<T>::del()
{
  if(empty()) throw(EStack(ESTACK_EMPTY));

  l1item<T>* tmp = head->next;
  delete head;
  head = tmp;
  return *this;
}

// Добавление элемента с стек
template <class T>
stack<T>& stack<T>::push(const T& data)
{
  l1item<T>* item = new l1item<T>;
  item->data = data;
  item->next = head;
  head = item;
  return *this;
}

// Извлечение элемента из стека
template <class T>
T stack<T>::pop()
{
  if(empty()) throw (EStack(ESTACK_EMPTY));

  l1item<T>* old = head;
  head = head->next;
  T data = old->data;
  delete old;
  return data;
}

// Просмотр элемента в вершине стека
template <class T>
const T& stack<T>::see() const
{
  if(empty()) throw (EStack(ESTACK_EMPTY));
  return head->data;  
}

// Оператор присваивания
template <class T>
stack<T>& stack<T>::operator = (const stack<T>& Stack)
{
  if (this == &Stack) return *this;
  clear();
  if(!Stack.empty())
  {
    head = new l1item<T>;
    l1item<T>* cur = head;
    l1item<T>* src = Stack.head;
    while(src)
    {
      cur->data = src->data;
      if(src->next)
      {
        cur->next = new l1item<T>;
        cur = cur->next;
      } else
        cur->next = NULL;
      src = src->next;
    }
  }
  return *this;
}

#endif
Слава Антонов © 2002 — August 13, 2008
Индекс цитирования
Hosted by uCoz