Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef _queue_h_
- #define _queue_h_
- #pragma region PresentationAsList
- template <typename T>
- class QueueAsList {
- public:
- QueueAsList();
- ~QueueAsList();
- T pop();
- T front();
- void push(const T& input);
- bool empty();
- private:
- QueueAsList(const QueueAsList& dummy) = delete;
- QueueAsList& operator=(const QueueAsList& dummy) = delete;
- struct Elem {
- Elem* next;
- T data;
- };
- Elem* head;
- Elem* tail;
- };
- template<typename T>
- inline QueueAsList<T>::QueueAsList() {
- head = nullptr;
- tail = nullptr;
- }
- template<typename T>
- inline QueueAsList<T>::~QueueAsList() {
- Elem* curr;
- while (head != nullptr) {
- curr = head;
- head = head->next;
- delete curr;
- }
- }
- template<typename T>
- inline T QueueAsList<T>::pop() {
- if (head == tail) {
- T answer = head->data;
- delete head;
- head = nullptr;
- tail = nullptr;
- return answer;
- }
- Elem* curr = head;
- head = head->next;
- T answer = curr->data;
- delete curr;
- return answer;
- }
- template<typename T>
- inline T QueueAsList<T>::front() {
- return head->data;
- }
- template<typename T>
- inline void QueueAsList<T>::push(const T& input) {
- if (head == nullptr) {
- tail = new Elem;
- head = tail;
- head->next = nullptr;
- head->data = input;
- return;
- }
- tail->next = new Elem;
- tail = tail->next;
- tail->next = nullptr;
- tail->data = input;
- }
- template<typename T>
- inline bool QueueAsList<T>::empty() {
- if (head == nullptr)
- return true;
- return false;
- }
- #pragma endregion
- #pragma region PresentationAsVector
- template <typename T>
- class QueueAsVector {
- public:
- QueueAsVector();
- ~QueueAsVector();
- void push(const T& input);
- bool empty();
- T front();
- T pop();
- private:
- QueueAsVector(const QueueAsVector& dummy) = delete;
- QueueAsVector& operator=(const QueueAsVector& dummy) = delete;
- void decreaseSize();
- T* data;
- int head;
- int tail;
- int cap;
- int numberElem;
- };
- template<typename T>
- inline QueueAsVector<T>::QueueAsVector() {
- data = nullptr;
- }
- template<typename T>
- inline QueueAsVector<T>::~QueueAsVector() {
- delete[] data;
- }
- template<typename T>
- inline void QueueAsVector<T>::push(const T& input) {
- if (data == nullptr) {
- data = new T[5];
- cap = 5;
- numberElem = 1;
- head = tail = 0;
- data[head] = input;
- return;
- }
- if (numberElem == cap) {
- T* newData = new T[cap * 2];
- int curr = head;
- for (int i = 0; i < cap; ++i) {
- if (curr == tail) {
- newData[i] = data[curr];
- break;
- }
- newData[i] = data[curr];
- if (curr == cap - 1)
- curr = -1;
- ++curr;
- }
- newData[cap] = input;
- head = 0;
- tail = cap;
- ++numberElem;
- cap *= 2;
- delete[] data;
- data = newData;
- return;
- }
- if (tail == cap - 1)
- tail = -1;
- ++tail;
- data[tail] = input;
- ++numberElem;
- }
- template<typename T>
- inline bool QueueAsVector<T>::empty() {
- if (numberElem == 0)
- return true;
- return false;
- }
- template<typename T>
- inline T QueueAsVector<T>::front() {
- std::cout << "\n front Current head: " << head << std::endl;
- T answer = data[head];
- return answer;
- }
- template<typename T>
- inline T QueueAsVector<T>::pop() {
- std::cout << "\n pop Current head: " << head << std::endl;
- T answer = data[head];
- if (head == cap - 1)
- head = -1;
- ++head;
- --numberElem;
- decreaseSize();
- return answer;
- }
- template<typename T>
- inline void QueueAsVector<T>::decreaseSize() {
- if (cap < 3)
- return;
- if (cap * 3 / 4 > numberElem) {
- T* newData = new T[cap * 3 / 4];
- int curr = head;
- for (int i = 0;; ++i) {
- if (curr == tail) {
- newData[i] = data[curr];
- break;
- }
- newData[i] = data[curr];
- if (curr == cap - 1)
- curr = -1;
- ++curr;
- }
- head = 0;
- tail = numberElem - 1;
- cap = cap * 3 / 4;
- delete[] data;
- data = newData;
- }
- }
- #pragma endregion
- #endif // !_queue_h_
- #include <iostream>
- //----------------------
- #include <iostream>
- //#include "queue.h"
- int main() {
- /*QueueAsList <int>test;
- test.push(1);
- std::cout << test.front() << std::endl;
- if (!test.empty())
- std::cout << test.pop() << std::endl;
- test.push(2);
- test.push(3);
- if (!test.empty())
- std::cout << test.pop() << std::endl;
- if (!test.empty())
- std::cout << test.pop() << std::endl;*/
- QueueAsVector <int>test;
- int input;
- for (int i = 0; i < 10; ++i) {
- //std::cin >> input;
- for(int i=1;i<=10;++i)
- test.push(i);
- }
- while (!test.empty()) {
- std::cout << test.front() << " " << test.pop() << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement