一、思维导图
二、myStack
#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
typedef int datatype;
using namespace std;
class myStack
{
private:
datatype *data;
size_t size;
size_t capacity;
public:
myStack():size(0),capacity(5){ //无参构造
data = new datatype [5];
}
myStack(size_t cap) //有参构造
{
data = new datatype[cap];
capacity = cap;
size = 0;
}
myStack(const myStack& other){ //拷贝构造
if(this != &other)
{
delete [] this->data;
this->size = other.size;
this->capacity = other.capacity;
this->data = new datatype[this->capacity];
for(size_t i=0;i<this->size;i++)
{
this->data[i] = other.data[i];
}
}
}
virtual ~myStack() //虚析构函数
{
delete []data;
}
myStack& operator=(const myStack& other); //运算符重载
void expend(); //二倍扩容
datatype& top(); //访问栈顶元素
bool empty(); //检查是否为空
size_t get_size(); //获取元素个数
myStack& push(datatype element); //向栈顶插入元素
myStack& pop(); //删除栈顶元素
};
#endif // MYSTACK_H
#include"myStack.h"
myStack& myStack::operator=(const myStack& other)
{
if (this != &other)
{
while (this->capacity < other.capacity) {
this->expend();
}
for (size_t i = 0; i < other.size; ++i) {
this->data[i] = other.data[i];
}
size = other.size;
}
return *this;
}
void myStack::expend()
{
datatype* Temp = new datatype [capacity*2];
for (size_t i = 0; i < capacity; ++i) {
Temp[i] = data[i];
}
delete [] data;
data = Temp;
capacity *= 2;
}
datatype& myStack::top()
{
return this->data[size-1];
}
bool myStack::empty()
{
return (this->size == 0);
}
size_t myStack::get_size()
{
return this->size;
}
myStack& myStack::push(datatype element)
{
if( capacity== (size+1)){
//扩容
this->expend();
}
this->data[size] = element;
size++;
return *this;
}
myStack& myStack::pop()
{
size--;
return *this;
}
#include"myStack.h"
int main()
{
cout<<"*********有参构造，push1,2,3,4,5**************"<<endl;
myStack stk1(2);
stk1.push(1);stk1.push(2);stk1.push(3);stk1.push(4);stk1.push(5);
cout<<"************* top ***********"<<endl;
datatype element = stk1.top();
cout<<"top1 = "<<element<<endl;
cout<<"*********拷贝构造，top**************"<<endl;
myStack stk2(stk1);
element = stk2.top();
cout<<"top2 = "<<element<<endl;
cout<<"********* pop ***********"<<endl;
stk2.pop();
element = stk2.top();
cout<<"top2 = "<<element<<endl;
cout<<"****************************"<<endl;
return 0;
}
三、myQueue
#ifndef MYQUEUE_H
#define MYQUEUE_H
#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
typedef int datatype;
using namespace std;
class myQueue
{
private:
datatype *data;
size_t frontIndex;
size_t backIndex;
size_t capacity;
public:
myQueue():frontIndex(0),backIndex(0),capacity(5){ //无参构造
data = new datatype [5];
}
myQueue(size_t cap):frontIndex(0),backIndex(0) //有参构造 //有参构造
{
data = new datatype[cap];
capacity = cap;
}
myQueue(const myQueue& other){ //拷贝构造
if(this != &other)
{
capacity = other.capacity;
data = new datatype[capacity];
frontIndex = other.frontIndex;
backIndex = other.backIndex;
memcpy(data, other.data, capacity * sizeof(datatype));
}
}
virtual ~myQueue() //虚析构函数
{
delete []data;
}
myQueue& operator=(const myQueue other); //运算符重载
void expend(); //二倍扩容
datatype& front(); //访问队首元素
datatype& back(); //访问队尾元素
bool empty(); //检查是否为空
size_t get_size(); //获取元素个数
myQueue& push(datatype element); //向栈顶插入元素
myQueue& pop(); //删除栈顶元素
};
#endif // MYSTACK_H
#endif // MYQUEUE_H
#include"myQueue.h"
myQueue& myQueue::operator=(const myQueue other)
{
// 检查自赋值
if (this == &other) {
return *this;
}
// 释放原有内存
delete[] data;
// 分配新内存并复制数据
capacity = other.capacity;
frontIndex = other.frontIndex;
backIndex = other.backIndex;
data = new datatype[capacity];
memcpy(data, other.data, capacity * sizeof(datatype));
return *this;
}
void myQueue::expend()
{
size_t newCapacity = capacity * 2;
// 分配新内存并复制原有数据
datatype* newData = new datatype[newCapacity];
memcpy(newData, data, capacity * sizeof(datatype));
// 释放原有内存并将指针指向新内存
delete[] data;
data = newData;
// 更新容量
capacity = newCapacity;
}
datatype& myQueue::front()
{
return data[frontIndex];
}
datatype& myQueue::back()
{
return data[backIndex-1];
}
bool myQueue::empty()
{
return (frontIndex == backIndex);
}
size_t myQueue::get_size()
{
return (backIndex - frontIndex);
}
myQueue& myQueue::push(datatype element)
{
if(capacity == (backIndex+1))
{
//扩容
this->expend();
}
this->data[backIndex] = element;
this->backIndex++;
return *this;
}
myQueue& myQueue::pop()
{
if (empty()) {
throw std::runtime_error("Queue is empty");
}
frontIndex++;
return *this;
}
#include "myQueue.h"
using namespace std;
int main()
{
cout << "*********无参构造，push1,2,3,4,5**************" << endl;
myQueue q1;
q1.push(1).push(2).push(3).push(4).push(5);
cout << "************* front ***********" << endl;
datatype element = q1.front();
cout << "front1 = " << element << endl;
cout << "*********有参构造,back**************" << endl;
myQueue q2(10);
q2.push(6).push(7).push(8).push(9).push(10);
element = q2.back();
cout << "back2 = " << element << endl;
cout << "*********拷贝构造，pop**************" << endl;
myQueue q3(q2);
q3.pop();
element = q3.front();
cout << "front3 = " << element << endl;
cout << "****************************" << endl;
return 0;
}
