diff options
author | Santo Cariotti <dcariotti24@gmail.com> | 2020-06-20 12:14:47 +0200 |
---|---|---|
committer | Santo Cariotti <dcariotti24@gmail.com> | 2020-06-20 12:14:47 +0200 |
commit | aa62c5c63dd2ce178e8180359ea48c9794a8f735 (patch) | |
tree | e53661795b182a5f88fbd64e0d85401d21950ae2 /I_anno/Programmazione_2 | |
parent | ee95f53250a692a071e82a03091bb2ee3b708cf7 (diff) |
feat: add stack and queue implemented with an array
Diffstat (limited to 'I_anno/Programmazione_2')
-rw-r--r-- | I_anno/Programmazione_2/data_structures/queue_w_array.cc | 66 | ||||
-rw-r--r-- | I_anno/Programmazione_2/data_structures/stack_w_array.cc | 50 |
2 files changed, 116 insertions, 0 deletions
diff --git a/I_anno/Programmazione_2/data_structures/queue_w_array.cc b/I_anno/Programmazione_2/data_structures/queue_w_array.cc new file mode 100644 index 0000000..fb92d68 --- /dev/null +++ b/I_anno/Programmazione_2/data_structures/queue_w_array.cc @@ -0,0 +1,66 @@ +#include<iostream> + +using namespace std; + +template<class H> +class queue { +public: + queue(int n) : _size{n}, _counter{0}, _head{0}, _tail{0} { + _arr = new H[n]; + } + ~queue() { + delete _arr; + } + bool is_empty() { + return _counter == 0; + } + bool is_full() { + return _counter == _size; + } + + queue<H>* enqueue(H x) { + if(!is_full()) { + _arr[_tail] = x; + if(_tail == _size-1) + _tail = 0; + else + ++_tail; + _counter++; + } + + return this; + } + H dequeue() { + if(is_empty()) return -1; + H x = _arr[_head]; + + if(_head == _size-1) + _head = 0; + else + ++_head; + + _counter--; + return x; + } +private: + H* _arr; + int _size; + short _counter; + short _head; + short _tail; +}; + +int main() { + queue<int>* q = new queue<int>{4}; + q->enqueue(5)->enqueue(13)->enqueue(3); + cout << q->dequeue() << '\n'; + q->enqueue(4)->enqueue(6)->enqueue(7); + q->dequeue(); + q->enqueue(7); + + for(int i = 0; i < 6; ++i) { + cout << q->dequeue() << ' '; + } + delete q; + return 0; +} diff --git a/I_anno/Programmazione_2/data_structures/stack_w_array.cc b/I_anno/Programmazione_2/data_structures/stack_w_array.cc new file mode 100644 index 0000000..c20db90 --- /dev/null +++ b/I_anno/Programmazione_2/data_structures/stack_w_array.cc @@ -0,0 +1,50 @@ +#include<iostream> + +using namespace std; + +template<class H> +class stack { +public: + stack(int n) : _size{n}, _top{-1} { + _arr = new H[n]; + } + ~stack() { + delete _arr; + } + bool is_empty() { + return _top == -1; + } + bool is_full() { + return _top == _size-1; + } + stack<H>* push(H x) { + if(!is_full()) { + _arr[++_top] = x; + } + return this; + } + H pop() { + if(is_empty()) + return -1; + _top--; + return _arr[_top+1]; + } +private: + int _size; + H* _arr; + short _top; +}; + +int main() { + stack<int>* s = new stack<int>{7}; + + s->push(15)->push(6)->push(2)->push(9)->push(17)->push(3); + cout << s->pop() << '\n'; + s->push(18)->push(19)->push(12); + + for(int i = 0; i < 7; ++i) + cout << s->pop() << ' '; + + delete s; + return 0; +} |