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 0(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 48 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; 66 67 68 69 70 Data Structures and Objects Lab 6 Array Doubing 10 11 12 13 14 15 Recall that one of the big differences between arrays and pointers is that pointers do not get space 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 can deallocate the space in the destructor 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 array fills 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'll add a new variable to keep track of the current size. 66 private: 67 StackType *data; int count, capacity; The capacity must be initialized in the constructor 10 public: Stack(void) { data = new StackType(STACK_SIZE]; capacity = STACK_SIZE; count = ; 15) 68 69 70 71 11 12 13 14 The only other change that needs to be made is in handlinga push onto a fullstack all other actions are unchanged, one of the advantages of this technique. To increase space. do the following: 1. Calculate a new capacity 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 array. 4. Deallocate the current array and point to the new array, If for some reason the memory allocation fails, then an exception is thrown. The resulting code looks like this: 22 void push(const StackType &d) { 23 24 if (count == STACK_SIZE) { 25 int 26 tmpCap = 2 * capacity; 27 StackType 28 *tmpData = new StackType [tmpCap]; if (tmpData == nullptr) throw std::overflow_error("Stack is_full"); for (int i=0;i