c++

queue.h:

#ifndef _QUEUE_H

#define _QUEUE_H

const int32_t

QUEUE_SIZE = 64;

template

class Queue {

public:

Queue(int32_t qSize=QUEUE_SIZE) {

capacity = qSize;

data = new QueueType[capacity];

count = tail = 0;

head = capacity - 1;

}

~Queue() {

delete[] data;

}

void clear() {

count = tail = 0;

head = capacity - 1;

}

int32_t size() { return count; }

bool isEmpty() { return !count; }

void enqueue(QueueType d) {

if (count == capacity)

throw overflow_error("Queue is full");

data[tail] = d;

tail = (tail + 1) % QUEUE_SIZE;

count++;

}

QueueType dequeue() {

if (count == 0)

throw underflow_error("Queue is empty");

head = (head + 1) % QUEUE_SIZE;

count--;

return data[head];

}

private:

int32_t

head, tail,

count,

capacity;

QueueType

*data;

};

#endif

#stack.h:

ifndef _STACK_H

#define _STACK_H

#include

using namespace std;

const int32_t

STACK_SIZE = 64;

template

class Stack {

public:

explicit Stack(int32_t sSize=STACK_SIZE) {

data = new StackType[sSize];

capacity = sSize;

top = 0;

}

~Stack() {

delete[] data;

}

void clear() { top = 0; }

int size() { return top; }

bool isEmpty() { return !top; }

void push(StackType d) {

if (top == capacity)

throw overflow_error("Stack is full");

data[top++] = d;

}

StackType pop() {

if (top == 0)

throw underflow_error("Stack is empty");

return data[--top];

}

StackType peek() {

if (top == 0)

throw underflow_error("Stack is empty");

return data[top-1];

}

private:

StackType

*data;

int32_t

top,

capacity;

};

#endif

Goal Modify the templated Stack and Queue classes to use arrays that grow when full. Motivation Our first versions of the Stack and Queue classes used arrays to hold the data. This has the ad- vantages of speed and simplicity; however, because an array is used, the containers have a fixed size. We could use a linked structure instead. As with an array-based implementation, all of the stack and queue operations still have O(1) run-time. Unlike arrays, linked structures can grow to accom- modate additional data. However, in practice, linked structures are slower than arrays. Having to call memory management functions for each addition and removal slows down access. Array doubling provides a middle ground. Arrays are used for faster access and memory manage- ment functions are called when more space is needed. The trick is to limit the number of times this is done 47 49 50 51 How It Works Consider our current Stack template. Note that it declares an array for holding data: private: StackType data[STACK_SIZE); int count; Since both arrays and pointers can be subscripted, we could replace the array with a pointer: private: StackType data; int count; 06 67 68 69 70 11 12 13 14 15 Recall that one of the big differences between arrays and pointers is that pointers do not get spoce to be used like an array, we have to provide that separately. To do this, we'l need to allocate the space in the constructor before we start adding data. We con deallocate the space in the destructor 10 public: Stack(void) { data = new StackType [STACK_SIZE); count = 0; } -Stack(void) { delete[] data; } Now, the Stack class works just as it did initially, including the possibility of filing and throwing ex- ceptions. However, the current approach gives us another choice of action when the amoy fils - we can create a larger array To begin, we need to keep track of how large the current array is. Initially, this is just the STACK_SIZE constant, however, over time, the array may increase in size multiple times, so we't add a new variable to keep track of the current size 66 private: StackType data; int count, capacity: The capacity must be initialized in the constructor: 10 public: Stack(void) { data = new StackType(STACK_SIZE); 13 capacity = STACK_SIZE; count = 0; 15) 67 68 80 70 71 11 12 14 The only other change that needs to be made is in handlinga push onto a ful stock all other actions are unchanged, one of the advantages of this technique. To increase space. do the following: 1. Calculate a new copacity that is twice as large as the current capacity 2. Dynamically allocate a new array with the new capacity as the number of elements 3. Copy all elements from the current array to the front of the new andy 4. Deallocate the current array and point to the new ortay. If for some reason the memory allocation fails, then an exception is thrown. int The resulting code looks like this: 22 void push(const StackType id) { ++ (count -- STACK_SIZE) { tmpcap - 2. capacity: StackType tmppata - new StackType(tmpcap]; if (tmpData = nullptr) throw std::overflow_error("Stack is full); for (int 1-0;i