Раздел «Образование».FIVTLecturesTerm2Lecture05:
<<Лекции ФИВТ, 2-й семестр

Лекция 5. АТД Стек. Постфиксный калькулятор. Реализация очереди с помощью двух стеков

АТД Стек. Постфиксный калькулятор. Реализация очереди с помощью двух стеков. Примеры использования STL.

Код калькулятора, вычисляющего выражение

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>

// нужно самим написать шаблон класса stack
#include "stack" 

using namespace std;

int main() {
  // 1 2 + 3 4 + *
  // 21
  stack<double> s;
  string str;
  while ( cin >> str ) {
    if ( str == "+") {
      s.push_back(s.pop() + s.pop());
    } else if (str == "*") {
      s.push(s.pop() * s.pop());
    } else {
      int x;
      if (sscanf(str.c_str(), "%lf", &x) == 1) {
        s.push(x);
      } else {
        cerr << "Can't parse input string" << endl;
        exit(1);
      };
    }
  }
  cout << s.pop() << endl;
  return 0;
}

Здесь мы предполагаем наличие некоторого пользовательского шаблона класса stack. Роль стека также могут играть стандартные контейнеры vector, list, deque. В контейнере list есть операции добавить и извлечь для обеих концов. Операция pop в контейнере list делается в два приема: сначала s.back(), потом s.pop_back(). Первая возвращает значение вершины стека, не извлекая элемент из стека, вторая — ничего не возвращает, а только извлекает вершину стека:

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>

// нужно самим написать шаблон класса stack
#include "stack" 

using namespace std;

int main() {
  // 1 2 + 3 4 + *
  // 21
  list<double> s;
  string str;
  while ( cin >> str ) {
    if ( str == "+") {
      double a = s.back(); s.pop_back();
      double b = s.back(); s.pop_back();
      s.push_back( a + b );
    } else if (str == "*") {
      double a = s.back(); s.pop_back();
      double b = s.back(); s.pop_back();
      s.push( a * b );
    } else {
      int x;
      if ( sscanf(str.c_str(), "%lf", &x) == 1 ) {
        s.push(x);
      } else {
        cerr << "Can't parse input string" << endl;
        exit(1);
      };
    }
  }
  cout << s.pop() << endl;
  return 0;
}

Задачи и вопросы:

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

Из двух стеков можно сконструировать очередь (контейнеры с функциональностью очереди уже есть в STL, например, list). Амортизационное время выполнения операций enqueue (добавить в конец) и dequeue (извлечь из начала) будет O(1). Худшее время выполнения dequeue линейно завсисит от числа элементов.

На этот раз в роли стека будем использовать контейнер vector.

#include <vector>

using namespace std;

template<typename T>
class queue {
  vector<T> input;
  vector<T> output;
  
public:
  queue() {  };

  void enqueue(T e) {
    input.push_back(e);
  }

  // извлекает и возвращает первый элемент; 
  // проверка на наличие элемента не делается
  T dequeue() {
    if (output.size() == 0) {
      typename vector<T>::iterator it;
      for (it = input.begin(); it != input.end(); ++it) {
        output.push_back(*it);
      }
    }
    T result = output.back();
    output.pop_back();
    return result;
  }
};

int main() {
  queue<int> q;
  q.enqueue(13);
  q.enqueue(13);
  q.enqueue(13);
  q.enqueue(13);
  q.dequeue();
  q.dequeue();
  q.dequeue();
  q.dequeue();
  return 0;
}