Реализовать классы «стек» и «очередь» наследованием от базового класса «двусвязный список» - C++ - Ответ 2422882

@lemegeton · 24.01.2012, 19:06

Сообщение от ms.sv02

и что же мне теперь делать... что совсем ничего нельзя сделать?

Ну не надо так сразу отчаиваться. Что-нибудь да можно сделать.

Вот, например,

шаблонный класс двусвязного списка.

C++

#include <cstddef>
 
struct ListNodeBase {
  ListNodeBase() : prev(this), next(this) {}
  ListNodeBase(ListNodeBase *prev_, ListNodeBase *next_) : prev(prev_), next(next_) {
    prev->next = next->prev = this;
  }
  virtual ~ListNodeBase() {
    prev->next = next;
    next->prev = prev;
  }
  ListNodeBase *prev, *next;
};
 
template <class T>
struct ListNode : public ListNodeBase {
  ListNode(ListNodeBase *prev_, ListNodeBase *next_, const T &data_)
    : ListNodeBase(prev_, next_), data(data_) {}
  T data;
};
 
class ListIteratorBase {
 public:
  ListIteratorBase() : node_(NULL) {}
  ListIteratorBase(ListNodeBase *node) : node_(node) {}
  void increase() { node_=node_->next; }
  void decrease() { node_=node_->prev; }
  bool operator==(const ListIteratorBase &other) {
    return node_ == other.node_;
  }
  bool operator!=(const ListIteratorBase &other) {
    return !operator==(other);
  }
  ListNodeBase *node_;
};
 
template <class T, class R, class P>
class ListIterator : public ListIteratorBase {
 public:
  typedef ListIterator<T, T&, T*>             Iterator;
  typedef ListIterator<T, const T&, const T*> ConstIterator;
  typedef ListIterator<T, R, P>               Self;
  typedef T                                   ValueType;
  typedef R                                   ReferenceType;
  typedef P                                   PointerType;
  typedef ListNode<ValueType>                 Node;
  
  ListIterator() : ListIteratorBase() {}
  ListIterator(ListNodeBase *node) : ListIteratorBase(node) {}
  ListIterator(const Iterator &other) : ListIteratorBase(other.node_) {}
 
  ReferenceType operator*() const { return static_cast<Node*>(node_)->data; }
  ReferenceType operator->() const { return operator*(); }
  Self &operator++() {
    increase();
    return *this;
  }
  Self &operator--() {
    decrease();
    return *this;
  }
  Self operator++(int) {
    Self result(*this);
    increase();
    return result;
  }
  Self operator--(int) {
    Self result(*this);
    decrease();
    return result;
  }
  Self operator+(size_t n) {
    Self result(*this);
    while (n-- > 0) result.increase();
    return result;
  }
  Self operator-(size_t n) {
    Self result(*this);
    while (n-- > 0) result.decrease();
    return result;
  }
};
 
template <class T>
class List {
 public:
  typedef T             ValueType;
  typedef T&            ReferenceType;
  typedef const T&      ConstReferenceType;
  typedef T*            PointerType;
  typedef const T*      ConstPointerType;
  typedef ListNode<T>   Node;
  typedef ListIterator<T, T&, T*>             Iterator;
  typedef ListIterator<T, const T&, const T*> ConstIterator;
 
  List() : base_() {}
  List(const List &other) : base_() {
    insert(begin(), other.begin(), other.end());
  }
  ~List() { clear(); }
  List &operator=(const List &other) {
    if (this != &other) {
      clear();
      insert(begin(), other.begin(), other.end());
    }
    return *this;
  }
  Iterator begin() { return base_.next; }
  ConstIterator begin() const { return base_.next; }
  Iterator end() { return &base_; }
  ConstIterator end() const { return const_cast<ListNodeBase*>(&base_); }
  bool isEmpty() const { return &base_ == base_.next; }
  void clear() {
    while (!isEmpty()) {
      ListNodeBase *next = base_.next->next;
      delete base_.next;
      base_.next = next;
    }
  }
  size_t size() {
    size_t result = 0;
    for (Iterator i = begin(); i != end(); ++i) ++result;
    return result;
  }
  ReferenceType front() { return *begin(); }
  ConstReferenceType front() const { return *begin(); }
  ReferenceType back() { return *(--end()); }
  ConstReferenceType back() const { return *(--end()); }
 
  void pushBack(ConstReferenceType value) {
    new Node(base_.prev, &base_, value);
  }
  void pushFront(ConstReferenceType value) {
    new Node(&base_, base_.next, value);
  }
  ValueType popFront() {
    ValueType value = *begin();
    erase(begin());
    return value;
  }
  ValueType popBack() {
    ValueType value = *(--end());
    erase(--end());
    return value;
  }
  Iterator insert(Iterator before, ConstReferenceType value) {
    return new Node(before.node_->prev, before.node_, value);
  }
  template <class IteratorType>
  Iterator insert(Iterator before, IteratorType first, IteratorType last) {
    while (first != last)
      before = insert(before, *(first++)) + 1;
    return before;
  }
  void erase(Iterator what) {
    delete what.node_;
  }
 private:
  ListNodeBase base_;
};

В общем-то, он уже все умеет, что нужно двум финальным классам из задания: pushBack, pushFront, popBack и popFront.

Добавлено через 12 минут
Вот так правильно создавать классы стека и очереди на основе списка:

C++

#include <iostream>
#include "List.hpp" // предположим, тут наш контейнер двусвязного списка
 
template <class T, class Container = List<T> >
class Stack {
 public:
  Stack() : container() {}
  void push(const T &value) {
    container.pushBack(value);
  }
  T pop() {
    return container.popBack();
  }
  size_t size() const {
    return container.size();
  }
  void clear() {
    container.clear();
  }
  bool isEmpty() {
    return container.isEmpty();
  }
  const T &top() {
    return container.back();
  }
 private:
  Container container;
};
 
template <class T, class Container = List<T> >
class Queue {
 public:
  Queue() : container() {}
  void enqueue(const T &value) {
    container.pushBack(value);
  }
  T dequeue() {
    return container.popFront();
  }
  size_t size() const {
    return container.size();
  }
  void clear() {
    container.clear();
  }
  bool isEmpty() {
    return container.isEmpty();
  }
  const T &top() {
    return container.front();
  }
 private:
  Container container;
};
 
 
int main(int argc, char *argv[]) {
  Stack<int> stack;
  for (int i = 0; i < 10; ++i)
    stack.push(i);
  while (!stack.isEmpty())
    std::cout << stack.pop() << std::endl;
  std::cout << std::endl;
 
  Queue<int> queue;
  for (int i = 0; i < 10; ++i)
    queue.enqueue(i);
  while (!queue.isEmpty())
    std::cout << queue.dequeue() << std::endl;  
  std::cout << std::endl;
}

Вернуться к обсуждению:
Реализовать классы «стек» и «очередь» наследованием от базового класса «двусвязный список» C++

Другие темы раздела
C++ Строки. Задача по С++ https://www.cyberforum.ru/ cpp-beginners/ thread433621.html Преобразовать строку так, чтобы буквы каждого слова в ней были отсортированы по возрастанию.	Строки и бинарные файлы C++ Программа читает из бинарного файла и выводит содержимое на экран. Потом можно добавить 1 элемент в любую ячейку. Проблема в том, что при выводе на экран, оно выводит 1 первый символ строки, а затем каракули. Вот код самой проги: #include<stdio.h> #include<stdlib.h> // Функции int getFileSize(FILE f); int getElementAtPosition(int ,FILE ); void setFileElements(int ,char...
C++ Перевод из Delphi в c++ Помогите перевести код в с++ unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, md5, jpeg, ExtCtrls; type https://www.cyberforum.ru/ cpp-beginners/ thread433610.html	C++ полуторный тариф люди подскажите как дописать код задачи на си. есть фирма, которая выплачивает своим сотрудникам за первые 40 часов работы обычную зарплату, и полуторную зарплату за время отработанное сверх 40 часов. как записать это самое время после 40 часов, и ставку которую нужно будет заплатить. начало моего кода: Код: https://www.cyberforum.ru/ cpp-beginners/ thread433604.html
функция C++ Добрый день, на что ругается функция?? #include <iostream> #include <iomanip> #include <cmath> #include <conio.h> using namespace std; void sum(double *m,int n) { int i,t; double sum=0.0;	C++ Помогите,нужно составить программу вычисления задачи.. https://www.cyberforum.ru/ cpp-beginners/ thread433591.html Вычислить растояние между двумя точками с координатами (Х1,у1) и (х2,у2) координаты вводятся с клавиатуры..
C++ Есть бесконечный цикл в программе и она поэтому занимает процессор, как это исправить? НАписал себе напоминалку, а она жрёт процессор (~~ 45%); код упростил для понятности #include <stdio.h> #include <windows.h> #include <ctime> using namespace std; int main() { https://www.cyberforum.ru/ cpp-beginners/ thread433576.html	C++ Вычислить сумму ряда. День добрый. Помогите пожалуйста написать програмку. Вот задание. http://s006.***********/i214/1201/83/a86d4a6e9fe2.jpg
C++ Написать алгоритм, чтобы каждый квадрат возрастал на одинаковую величину Нужно написать алгоритм чтобы каждый квадрат возрастал на одинаковую величину, ну и уменьшался тоже. Прошу помощи не в написании программы, а в написании этого алгоритма. Т. е. по сути вставка символа "-" и "\|" в каждый квадрат. --------------------------------- \| \| \| \| \| n \| \| \| \| \| \| \|... https://www.cyberforum.ru/ cpp-beginners/ thread433542.html	C++ iterators & file https://www.cyberforum.ru/ cpp-beginners/ thread433531.html можно ли считывать итераторами с файла типу так: #include <iostream> #include <fstream> #include <iterator> #include <vector> #include <algorithm> int main() { std::vector<int> v;
Ошибка: "variable is being used without being initializied" C++ Доброго времени суток !!! #include <math.h> #include <sys/timeb.h> #include <iostream> using namespace std; #define n 4 //#define x01 0.21878104 //#define x02 30121 #define ConstL 805 #define g 16	C++ Не совсем змейка Доброго времени суток! Пожалуйста помогите решить задачу: Входные данные: 4 1 3 6 10 2 5 9 13 4 8 12 15 7 11 14 16 Выходные данные: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 https://www.cyberforum.ru/ cpp-beginners/ thread433526.html

	24.01.2012, 19:06