Структуры данных: Стек и очередь

Дата создания: 2009-04-13 20:39:33
Последний раз редактировалось: 2012-02-08 07:01:25

Стек (stack)

Мы рассматриваем эту структуру данных так сказать для общего развития. Применение стеков при программировании компьютерных игр не слишком распространено. Тем не менее, стек довольно полезен в определённых ситуациях.

Для создания стека мы будем использовать класс.

Что это вообще такое? Стек можно представлять в виде стопки. Каждый новый элемент кладётся на предыдущий. При этом взять можно только последний элемент. Чтобы достать самый первый элемент из стека, нужно сначала достать элементы, которые были добавлены после первого.

В стеке реализуется так называемая стратегия последним вошёл, первым вышел - Last in, first out (LIFO).

Минимум для реализации стека: массив в котором хранится стек, вершина стека (всегда указывает на последний элемент), функция проталкивания (push) элемента в стек, функция выталкивания (pop) элемента из стека.

Стек довольно прост в реализации:

class stack
{
private:
  int top;   // вершина стека
  int s[10]; // массив в котором хранится стек

public:
  stack (): top(0) // конструктор без параметров
  {}

  void push(int var); // функция для проталкивания элементов в стек
  int pop();                  // функция выталкивания элементов из стека
};

void stack::push(int var)
{
  top++;        // Увеличение вершины.
  s[top] = var; // Добавление значения в элемент
}               // на который указывает вершина.


int stack::pop()
{
  int var = s[top]; // Получаем значение элемента на который 
  top--;            // указывает вершина и уменьшаем вершину.
  return var;
}

Здесь представлен самый примитивный вариант стека. Стек представлен массивом s. Данная реализация стека может работать только с переменными типа int. К тому же, максимальный размер стека мы ограничили десятью элементами.

Использовать такой стек в реальной программе очень опасно! Потому что нет механизмов по предотвращению переполнения и опустошения стека.

Ваша задача немножко доработать стек. Добавьте проверку на переполнение и опустошение стека. Для этого создайте две функции: empty() (пустой) и full() (полный). Данные функции нужно вызывать в push() или pop().

Очереди

Есть ещё одна структура данных близкая к стекам. Называется она очередью.

В очереди реализуется стратегия Первым вошёл, первым вышел - First in, first out (FIFO).

Сразу рассмотрим реализацию:

class queue
{
private:
  int head, tail; // переменные хранящие начальный и конечный индексы
  int q[10]; // очередь содержащая десять элементов

public:
  queue() : head(0),tail(0) // конструктор
  {}
  void enqueue(int number) // добавление в очередь
  {
  q[tail] = number;
  tail = (tail+1) % 10;
  }
  int dequeue () // удаление из очереди
  {
  int temp = q[head];
  head = (head+1) % 10;
  return temp;
  }
};

Queue - очередь.
Enqueue - поместить в очередь.
Dequeue - вывести из очереди.
Head - начало.
Tail - конец.
Temp - временный.

head - позиция первого элемента в очереди

tail - позиция в которую будет добавляться элемент.

При условии head = tail, очередь пуста.

В данном примере очередь хранится в массиве q из десяти элементов.

За добавление/удаление из очереди отвечают две функции enqueue() и dequeue().

В функцию enqueue() передаётся значение, которое присваивается последнему элементу очереди. Затем индекс последнего элемента (tail) увеличивается. Обратите внимание, что если индекс достигнет последнего значения - в нашем примере 9, то индекс переносится в начало. Достигается это использованием операции взятия остатка от деления (%). Например: допустим что в данный момент tail = 9, мы вызываем функцию enqueue(3), в десятый элемент массива (q[9]) заносится значение 3. Затем происходит увеличение tail на единицу. теперь оно равно 10. Теперь получившееся значения делится на 10 и берётся остаток. 10 % 10 = 0. Соответственно теперь tail = 0.

Функция dequeue() работает следующим образом: мы сохраняем значения элемента на который указывает индекс head во временной переменной temp. Затем увеличиваем head. Здесь также используем операцию взятия остатка, для переноса head в начало массива. Затем возвращаем temp.

Упражнения:

1. Реализовать проверку переполнения очереди. Сделать это лучше всего в функции enqueue(). Здесь также пригодится операция %.
2. Реализовать проверку опустошения очереди в функции dequeue(). Условие, когда очередь пуста указано выше.
3. Внести в класс изменения, чтобы можно было создавать очередь с произовольным количеством элементов.
4. Написать программу, используя очередь с небольшим количеством элементов (5 или даже 3), и отследить значения в массиве с помощью отладчика.