基于Array和Stack 实现的类ArrayStack代码
#ifndef DATASTRUCTURE_ARRAYSTACK_H #define DATASTRUCTURE_ARRAYSTACK_H #include "Array.h" #include "Stack.h"//包括之前的两个类 template<class T> class ArrayStack : public Stack<T> { public: ArrayStack(int capacity) { array = new Array<T>(capacity); } ArrayStack() { array = new Array<T>(); } ~ArrayStack() { //问题？ delete[] array; array = nullptr; } int getSize() { return array->getSize(); } int getCapacity(){ return array->getCapacity(); } T pop() { return array->removeLast(); } T peek() { return array->getLast(); } void push(T e) { array->addLast(e); } bool isEmpty() { return array->isEmpty(); } /** * 打印数组的所有元素 */ void print() { std::cout << "Stack: size = " << array->getSize() << ", capacity = " << array->getCapacity() << std::endl; std::cout << "bottom "; array->toPrint(); std::cout << " top" << std::endl; } private: Array<T> *array; }; #endif //DATASTRUCTURE_ARRAYSTACK_H动态数组Array的代码
#include <iostream> #include <cassert> template<class T> class Array { private: T *data; int size; int capacity; void resize(int newCapacity){ T *newData = new T[newCapacity]; for (int i = 0; i < size; ++i) { newData[i] = data[i]; } data = newData; capacity = newCapacity; } public: Array(int capacity) { data = new T[capacity]; size = 0; this->capacity = capacity; } Array() { data = new T[5]; size = 0; capacity = 5; } int getCapacity() { return capacity; } int getSize() { return size; } bool isEmpty() { return size == 0; } void add(int index, T e) { assert(index >= 0 && index <= size); if (size == capacity) { resize(2 * capacity); } for (int i = size - 1; i >= index; --i) { data[i + 1] = data[i]; } data[index] = e; size++; } void addFirst(T e) { add(0, e); } void addLast(T e) { add(size, e); } T get(int index) { assert(index >= 0 && index < size); return data[index]; } T getLast(){ return get(size-1); } T getFirst(){ return get(0); } void set(int index, T e) { assert(index >= 0 && index < size); data[index] = e; } bool contains(T e) { for (int i = 0; i < size; ++i) { if (data[i] == e) { return true; } } return false; } int find(T e) { for (int i = 0; i < size; ++i) { if (data[i] == e) { return i; } } return -1; } T remove(int index) { assert(index >= 0 && index < size); T ret = data[index]; for (int i = index + 1; i < size; ++i) { data[i - 1] = data[i]; } size--; if (size == capacity / 4 && capacity / 2 != 0){ resize(capacity / 2); } return ret; } T removeFirst() { return remove(0); } T removeLast() { return remove(size - 1); } void removeElement(T e) { int index = find(e); if (index != -1) { remove(index); } } /** * 打印数组的所有元素 */ void print() { std::cout << "Array: size = " << size << ", capacity = " << getCapacity() << std::endl; toPrint(); } void toPrint() { std::cout << "["; for (int i = 0; i < size; ++i) { std::cout << data[i]; if (i != size - 1) { std::cout << ", "; } } std::cout << "]"; } };