数据结构应该活学活用，定义的数据可以不一样，可以通过增加数据开源表示成很多种含义 /***********栈的链式实现(调试结束)*************/
栈是一种简化的链表 template class StackNode { public: Type data; StackNode *next; StackNode() :data(Type()), next(nullptr){} StackNode(Type d, StackNode *n = nullptr) :data(d), next(n){} }; template class Stack { private: StackNode *top;//头节点指针 StackNode *tail; int length; public: Stack(); ~Stack(); bool isEmpty(); bool Push(const Type &x); bool Pop(Type &x); Type GetTop(); void ShowStack() const; }; template Stack::~Stack() { cout << “析构函数” << endl; StackNode *move = this->top; StackNode *tmp = this->top; while (move != nullptr) { move = move->next; delete tmp; tmp = move; } } template Stack::Stack() { cout << “构造函数(生成一个头节点)” << endl; this->top = this->tail = new StackNode(); this->length = 0; } template bool Stack::isEmpty() { return this->length == 0;//或者判断this->next==nullptr } template bool Stack::Push(const Type &x) { StackNode *add = new StackNode(x);//要添加的节点 if (add == nullptr) return false; this->tail->next = add; this->tail = add; this->length++; return true; } template bool Stack::Pop(Type &x) { if (this->top == this->tail) { cout << “栈为空，没有元素可以弹出” << endl; return false; } x = this->tail->data; this->length–; StackNode *move = this->top; while (move->next != this->tail) move = move->next; delete this->tail; this->tail = move; this->tail->next = nullptr;//注意这句话 cout << “元素” << x << “已经出栈” << endl; return true; } template Type Stack::GetTop() { if (this->length == 0) { cout << “链表为空，无法获取当前元素” << endl; return 0; } return this->tail->data; } template void Stack::ShowStack() const { if (this->length == 0) { cout << “栈为空，无法输出元素” << endl; return; } //正着输出 StackNode *move = this->top->next; while (move != nullptr) { cout << move->data << ” “; move = move->next; } cout << endl; } //栈测试程序 int main() { Stack st; for (int i = 0; i < 20; i++) st.Push(i + 1); st.ShowStack(); int a; for (int i = 0; i < 10; i++) { st.Pop(a); //cout << a << ” “; } st.ShowStack(); return 0; } /***********队列的链式实现形式(调试成功)*************/ //队列节点类 template class QueueNode { public: Type data; QueueNode *next; QueueNode() :data(Type()), next(nullptr){} QueueNode(Type d, QueueNode *n=nullptr) :data(d), next(n){} }; //队列类 template class Queue { private: QueueNode *front;//队首指针 QueueNode *rear;//队尾指针 int length;//队列长度 public: Queue(); ~Queue(); bool isEmpty(){ return this->length == 0; } int size() const{ return this->length; } Type gethead(){ return this->front->data; } bool push_back(const Type &x); bool pop_front(); void show_queue() const; }; //构造函数 template Queue::Queue() { cout << “构造函数，创建一个头节点” << endl; this->front = this->rear = new QueueNode();//创建一个头节点 this->length = 0; } //析构函数 template Queue::~Queue() { cout << “析构函数” << endl; QueueNode *denode = this->front; QueueNode *movenode = this->front; while (movenode != nullptr) { movenode = movenode->next; cout << “节点” << denode->data << “被删除” << endl; delete denode; denode = movenode; } cout << endl; } //插入元素到队尾 template bool Queue::push_back(const Type &x) { QueueNode *add = new QueueNode(x); if (add == nullptr) return false; this->length++; this->rear->next = add; this->rear = add; return true; } //删除队首元素 template bool Queue::pop_front() { if (this->length == 0) { cout << “队列已空，无法删除元素” << endl; return false; } QueueNode *popnode = this->front->next; this->front->next = popnode->next; if (this->length == 1) this->rear = this->front; delete popnode; this->length–; return true; } //输出队列 template void Queue::show_queue() const { if (this->length == 0) { cout << “队列为空，无法输出” << endl; return; } QueueNode *move = this->front->next; while (move != nullptr) { cout << move->data << ” “; move = move->next; } cout << endl; } int main() { Queue queue; for (int i = 0; i < 10; i++) queue.push_back(i + 1); for (int i = 0; i < 5; i++) queue.pop_front(); queue.show_queue(); return 0; }
