fork download
copy 
  1. #include <cassert>
  2. #include <iostream>
  3. #include <memory>
  4.  
  5. using namespace std;
  6.  
  7. const int DYNAMIC_ARRAYED_STACK_MIN_CAPACITY = 1;
  8.  
  9. template<class E>
  10. class DynamicArrayedStack {
  11. 	public:
  12. 		DynamicArrayedStack() {
  13.             clear();
  14. 		}
  15.  
  16. 		void clear() {
  17. 			_size = 0;
  18. 			_capacity = DYNAMIC_ARRAYED_STACK_MIN_CAPACITY;
  19. 			_elements.reset(new E[_capacity]);
  20. 		}
  21.  
  22. 		int size() {
  23. 			return _size;
  24. 		}
  25.  
  26. 		bool is_empty() {
  27. 			return _size == 0;
  28. 		}
  29.  
  30. 		E peek() {
  31. 			assert(!is_empty());
  32. 			return _elements[_size - 1];
  33. 		}
  34.  
  35. 		void pop() {
  36. 			assert(!is_empty());
  37. 			_size--;
  38.             if (_capacity > (3 * _size))
  39. 				resize();
  40. 		}
  41.  
  42. 		void push(E x) {
  43. 			if (_size == _capacity)
  44. 				resize();
  45. 			_elements[_size] = x;
  46. 			_size++;
  47. 		}
  48.  
  49. 	private:
  50. 		unique_ptr<E[]> _elements;
  51. 		int _size, _capacity;
  52.  
  53. 		void resize() {
  54. 			_capacity = max(_size * 2, DYNAMIC_ARRAYED_STACK_MIN_CAPACITY);
  55. 			unique_ptr<E[]> new_array(new E[_capacity]);
  56. 			for (int i = 0; i < _size; i++)
  57. 				new_array[i] = _elements[i];
  58. 			_elements.swap(new_array);
  59. 		}
  60. };
  61.  
  62. const int N = 6*1000*1000;	
  63.  
  64. int main() {
  65.  
  66. 	unique_ptr<DynamicArrayedStack<int>> st(new DynamicArrayedStack<int>());
  67. 	for (int i = 1; i <= N; i++) {
  68. 		st->push(i);
  69. 		assert(st->size() == i);
  70. 	}
  71.  
  72. 	assert(st->size() == N);
  73. 	assert(st->peek() == N);
  74.  
  75. 	for (int i = N; i >= 1; i--) {
  76. 		assert(st->size() == i);
  77. 		assert(st->peek() == i);
  78. 		st->pop();
  79. 	}
  80.  
  81. 	return 0;
  82. }
Success #stdin #stdout 0.13s 3888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oXe2t1
DynamicArrayedStack
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!