Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- //#include <ctime>
- using namespace std;
- template <typename T>
- class List {
- public:
- List() : size_(0), head_(nullptr), last_(nullptr) {}
- List(const List& other) : size_(0), head_(nullptr), last_(nullptr) {
- Node* temp = other.last_;
- while (temp != nullptr) {
- push_front(temp->value);
- temp = temp->prev;
- }
- }
- List(List&& other) : size_(other.size_), head_(other.head_), last_(other.last_) {
- other.head_ = other.last_ = nullptr;
- }
- List& operator=(const List& other) {
- if (this != &other) {
- clear();
- Node* temp = other.last_;
- while (temp != nullptr) {
- push_front(temp->value);
- temp = temp->prev;
- }
- }
- return *this;
- }
- List& operator=(List&& other) {
- if (this != &other) {
- clear();
- size_ = other.size_;
- head_ = other.head_;
- last_ = other.last_;
- other.head_ = other.last_ = nullptr;
- }
- return *this;
- }
- void push_front(const T& value) {
- if (size_ == 0) {
- last_ = head_ = new Node{ value, nullptr, nullptr };
- size_++;
- return;
- }
- Node* temp = new Node{ value, head_, nullptr };
- head_->prev = temp;
- head_ = temp;
- size_++;
- }
- void push_back(const T& value) {
- if (size_ == 0) {
- last_ = head_ = new Node{ value, nullptr, nullptr };
- size_++;
- return;
- }
- Node* temp = new Node{ value, nullptr, last_ };
- last_->next = temp;
- last_ = temp;
- size_++;
- }
- void pop_front() {
- if (size_ > 0) {
- if (size_ == 1) {
- delete head_;
- last_ = head_ = nullptr;
- size_--;
- return;
- }
- Node* temp = head_;
- head_ = head_->next;
- delete temp;
- head_->prev = nullptr;
- size_--;
- }
- }
- void pop_back() {
- if (size_ > 0) {
- if (size_ == 1) {
- delete head_;
- last_ = head_ = nullptr;
- size_--;
- return;
- }
- Node* temp = last_;
- last_ = last_->prev;
- delete temp;
- last_->next = nullptr;
- size_--;
- }
- }
- void insert(const int index, const T& value) {
- if (index == 0) {
- push_front(value);
- return;
- }
- if (index == size_) {
- push_back(value);
- return;
- }
- if (index > 0 && index < size_) {
- Node* temp = head_;
- for (int i = 0; i < index - 1; i++) {
- temp = temp->next;
- }
- Node* buf = new Node{ value, temp->next, temp };
- temp->next->prev = buf;
- temp->next = buf;
- size_++;
- }
- }
- void erase(const int index) {
- if (index == 0) {
- pop_front();
- return;
- }
- if (index == size_ - 1) {
- pop_back();
- return;
- }
- if (index > 0 && index < size_ - 1) {
- Node* temp = head_;
- for (int i = 0; i < index - 1; i++) {
- temp = temp->next;
- }
- Node* buf = temp->next->next;
- delete temp->next;
- temp->next = buf;
- buf->prev = temp;
- size_--;
- }
- }
- T& operator[] (const int index) {
- if (index >= 0 && index < size_) {
- Node* temp = head_;
- for (int i = 0; i < index; i++) {
- temp = temp->next;
- }
- return temp->value;
- }
- }
- const T& operator[] (const int index) const {
- if (index >= 0 && index < size_) {
- Node* temp = head_;
- for (int i = 0; i < index; i++) {
- temp = temp->next;
- }
- return temp->value;
- }
- }
- bool operator==(const List& other) const {
- if (size_ != other.size_) {
- return false;
- }
- Node* temp = head_;
- Node* other_temp = other.head_;
- while (temp != nullptr) {
- if (temp->value != other_temp->value) {
- return false;
- }
- temp = temp->next;
- other_temp = other_temp->next;
- }
- return true;
- }
- bool operator!=(const List& other) const {
- return !(*this == other);
- }
- int find(const T& value) const {
- int index = 0;
- Node* temp = head_;
- while (temp != nullptr && temp->value != value) {
- temp = temp->next;
- index++;
- }
- if (temp != nullptr) {
- return index;
- }
- return -1;
- }
- T& front() {
- if (head_ != nullptr) {
- return head_->value;
- }
- }
- const T& front() const {
- if (head_ != nullptr) {
- return head_->value;
- }
- }
- T& back() {
- if (last_ != nullptr) {
- return last_->value;
- }
- }
- const T& back() const {
- if (last_ != nullptr) {
- return last_->value;
- }
- }
- void print() const {
- Node* temp = head_;
- while (temp != nullptr) {
- cout << temp->value << " ";
- temp = temp->next;
- }
- cout << endl;
- }
- int size() const {
- return size_;
- }
- void clear() {
- while (head_ != nullptr) {
- pop_front();
- }
- }
- ~List() {
- clear();
- }
- private:
- struct Node { // двусвязный список состоит из узлов
- T value; // узел хранит информативную часть
- Node* next; // указатель на следующий узел в списке
- Node* prev; // указатель на предыдущий узел
- };
- int size_;
- Node* head_;
- Node* last_;
- };
- template <typename T>
- class Queue {
- public:
- void Push(const T& element) {
- elements_.push_back(element);
- }
- void Pop() {
- elements_.pop_front();
- }
- const T& Back() const {
- return elements_.back();
- }
- T& Back() {
- return elements_.back();
- }
- const T& Front() const {
- return elements_.front();
- }
- T& Front() {
- return elements_.front();
- }
- void Print() const {
- elements_.print();
- }
- int Size() const {
- return elements_.size();
- }
- bool IsEmpty() const {
- return elements_.size() == 0;
- }
- private:
- List<T> elements_;
- };
- int main() {
- Queue<int> queue;
- int start_time = clock();
- for (int i = 0; i < 200000; ++i) { // для замеров 200000 ставить
- queue.Push(i);
- //queue.Print(); // для замеров закомментировать
- }
- cout << endl;
- while (!queue.IsEmpty()) {
- //queue.Print(); // для замеров закомментировать
- queue.Pop();
- }
- cout << endl;
- int end_time = clock();
- cout << end_time - start_time << " milliseconds" << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement