Стек и очередь. Реализация с помощью массива.

Цикл статьей для подготовки к экзамену по предмету “Алгоритмы и структуры данных” (АиСД).

Определение. Стек (англ. stack — стопка; читается как “стэк”) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

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

Из чего состоит стек?

На рисунке видно, что стек состоит из ячеек, которые представлены в виде структуры данных, в которой находятся данные и указатель типа структуры на следующий элемент. Последний элемент указывает на null.

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

Реализация на массиве. Стек состоит из цепи элементов с обозначением [s1…s.top]. s1 — это начальный элемент в очереди, s.top — последний. Если s.top равен нулю, то такой стек считается пустым. Протестировать на наличие пустых элементов можно с помощью команды stackEmpty. Если данные будут сниматься с пустого стека, то это может приводить к ошибке.

#include <iostream>
#include <cstdlib>
using namespace std;
 
// Определяем емкость stack по умолчанию
#define SIZE 10
 
// Класс для представления stack
class Stack
{
    int *arr;
    int top;
    int capacity;
 
public:
    Stack(int size = SIZE);         // конструктор
    ~Stack();                       // деструктор
 
    void push(int);
    int pop();
    int peek();
 
    int size();
    bool isEmpty();
    bool isFull();
};
 
// Конструктор для инициализации stack
Stack::Stack(int size)
{
    arr = new int[size];
    capacity = size;
    top = -1;
}
 
// Деструктор для освобождения памяти, выделенной для stack
Stack::~Stack() {
    delete[] arr;
}
 
// Вспомогательная функция для добавления элемента `x` в stack
void Stack::push(int x)
{
    if (isFull())
    {
        cout << "Overflow\nProgram Terminated\n";
        exit(EXIT_FAILURE);
    }
 
    cout << "Inserting " << x << endl;
    arr[++top] = x;
}
 
// Вспомогательная функция для извлечения верхнего элемента из stack
int Stack::pop()
{
    // проверка на опустошение stack
    if (isEmpty())
    {
        cout << "Underflow\nProgram Terminated\n";
        exit(EXIT_FAILURE);
    }
 
    cout << "Removing " << peek() << endl;
 
    // уменьшаем размер stack на 1 и (необязательно) возвращаем извлеченный элемент
    return arr[top--];
}
 
// Вспомогательная функция для возврата верхнего элемента stack
int Stack::peek()
{
    if (!isEmpty()) {
        return arr[top];
    }
    else {
        exit(EXIT_FAILURE);
    }
}
 
// Вспомогательная функция для возврата размера stack
int Stack::size() {
    return top + 1;
}
 
// Вспомогательная функция для проверки, пуст stack или нет
bool Stack::isEmpty() {
    return top == -1;               // или return size() == 0;
}
 
// Вспомогательная функция для проверки, заполнен ли stack или нет
bool Stack::isFull() {
    return top == capacity - 1;     // или return size() == capacity;
}
 
int main()
{
    Stack pt(3);
 
    pt.push(1);
    pt.push(2);
 
    pt.pop();
    pt.pop();
 
    pt.push(3);
 
    cout << "The top element is " << pt.peek() << endl;
    cout << "The stack size is " << pt.size() << endl;
 
    pt.pop();
 
    if (pt.isEmpty()) {
        cout << "The stack is empty\n";
    }
    else {
        cout << "The stack is not empty\n";
    }
 
    return 0;
}

Очередь

Определение. Очередь – абстрактная структур данных, подчиняющаяся принципу FIFO — Firts In First Out («первый пришел — первый вышел»). Первый элемент в очереди выходит первым. 

Реализация

// Реализация очередей в C++

#include <iostream>
#define SIZE 5

using namespace std;

class Queue {
   private:
  int items[SIZE], front, rear;

   public:
  Queue() {
    front = -1;
    rear = -1;
  }

  bool isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    return false;
  }

  bool isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  void enQueue(int element) {
    if (isFull()) {
      cout << "Очередь заполнена";
    } else {
      if (front == -1) front = 0;
      rear++;
      items[rear] = element;
      cout << endl
         << "Добавлено значение " << element << endl;
    }
  }

  int deQueue() {
    int element;
    if (isEmpty()) {
      cout << "Очередь пуста" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } /* Внутри Q только один элемент, поэтому очередь сбрасывается
        в начальное состояние после удаления последнего элемента */
      else {
        front++;
      }
      cout << endl
         << "Удален элемент -> " << element << endl;
      return (element);
    }
  }

  void display() {
    /* Функция выводит в консоль элементы очереди */
    int i;
    if (isEmpty()) {
      cout << endl
         << "Пустая очередь" << endl;
    } else {
      cout << endl
         << "Индекс FRONT -> " << front;
      cout << endl
         << "Элементы -> ";
      for (i = front; i <= rear; i++)
        cout << items[i] << "  ";
      cout << endl
         << "Индекс REAR-> " << rear << endl;
    }
  }
};

int main() {
  Queue q;

  // функцию deQueue нельзя применять к пустой очереди
  q.deQueue();

  // Добавляем 5 элементов
  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);

  // Шестой элемент добавить нельзя — очередь заполнена
  q.enQueue(6);

  q.display();

  // Функция deQueue удаляет первый элемент — 1
  q.deQueue();

  // Теперь внутри очереди 4 элемента
  q.display();

  return 0;
}