[Solved] COEN79-Quiz 4

1. Write the pseudo-code of an algorithm which evaluates a fully parenthesized mathematical expression using stack data structure. (calculator).

2. For the queue class given in Appendix 1 (cf. end of this assignment), implement the copy constructor.

Note that the class uses a dynamic array. Also please note that you should not use the copy function (copy only the valid entries of one array to the new array).

1. template <class Item>
2. queue<Item>::queue (const queue <Item>& source)

3. queue class given in Appendix 1 (cf. end of this assignment), implement the following function, which increases the size of the dynamic array used to store items. Please note that you should not use the copy function (copy only the valid entries of one array to the new array).

4. deque class given in Appendix 2 (cf. end of this assignment), implement the following constructor. The constructor allocates an array of block pointers and initializes all of its entries with NULL. The initial size of the array is init_bp_array_size.

1. template < class Item >
2. deque<Item>::deque( int init_bp_array_size, int init_block_size )
3. {
4. bp_array_size = init_bp_array_size;
5. block_size = init_block_size;

5. deque class given in Appendix 2 (cf. end of this assignment), write the full implementation of the following function.

1. template <class Item>
2. void deque <Item>::pop_front()
3. // Precondition: There is at least one entry in the deque
4. // Postcondition: Removes an item from the front of the deque
5. {
6. assert(!isEmpty());

6. What are the outputs of the following programs?

Appendix 1: queue class declaration:

1. template < class Item >

Appendix 2: deque class declaration:

1. template < class Item > 2. class deque {
2. public:
3. // TYPEDEF
4. static const size_t BLOCK_SIZE = 5; // Number of data items per block
5. // Number of entries in the block of array pointers. The minimum acceptable value is 2 8. static const size_t BLOCKPOINTER_ARRAY_SIZE = 5; 9.
6. typedef std::size_t size_type; 11. typedef Item value_type;
8. deque(int init_bp_array_size = BLOCKPOINTER_ARRAY_SIZE,
9. int initi_block_size = BLOCK_SIZE);
11. deque(const deque & source); 17. ~deque();
13. // CONST MEMBER FUNCTIONS
14. bool isEmpty();
15. value_type front(); value_type back();
17. // MODIFICATION MEMBER FUNCTIONS
18. void operator = (const deque & source);
19. void clear();
20. void reserve();
21. void push_front(const value_type & data);
22. void push_back(const value_type & data);
23. void pop_back(); void pop_front();
25. private:
26. // A pointer to the dynamic array of block pointers value_type** block_pointers;
28. // A pointer to the final entry in the array of block pointers 38. value_type** block_pointers_end;
30. // A pointer to the first block pointer thats now being used 41. value_type** first_bp;
32. // A pointer to the last block pointer thats now being used 44. value_type** last_bp;
34. value_type* front_ptr; // A pointer to the front element of the whole deque 47. value_type* back_ptr; // A pointer to the back element of the whole deque
36. size_type bp_array_size; // Number of entries in the array of block pointers 50. size_type block_size; // Number of entries in each block of items
37. };