C++使用模板类实现链式栈
本文实例为大家分享了C++使用模板类实现链式栈的具体代码,供大家参考,具体内容如下
一、实现程序:
1.Stack.h
#ifndef Stack_h #define Stack_h template <class T> class Stack { public: Stack(){}; // 构造函数 void Push(const T x); // 新元素进栈 bool Pop(); // 栈顶元素出栈 virtual bool getTop(T &x) const = 0; // 读取栈顶元素,由x返回 virtual bool isEmpty() const = 0; // 判断栈空否 // virtual bool isFull() const = 0; // 判断栈满否,因为链式栈不存在不满的情况 virtual int getSize() const = 0; // 计算栈中元素个数 }; #endif /* Stack_h */
2.LinkedStack.h
#ifndef LinkedStack_h #define LinkedStack_h #include <iostream> #include "Stack.h" using namespace std; template <class T> struct LinkNode { T data; LinkNode<T> *link; }; //类的前置声明 template <class T> class LinkedStack; //友元函数的声明 template <class T> ostream& operator<<(ostream& out, LinkedStack<T>& s); template <class T> class LinkedStack: public Stack<T> { public: LinkedStack(); // 构造函数 ~LinkedStack();// 析构函数 void Push(const T x); // 进栈 bool Pop(); // 出栈 bool getTop(T &x) const; // 读取栈顶元素 bool isEmpty()const; // 判断栈是否为空 int getSize()const; // 求栈的元素个数 void makeEmpty(); // 清空栈的内容 friend ostream& operator << <T>(ostream& out, LinkedStack<T>& s); // 重载输出函数 private: LinkNode<T> *top; // 栈顶指针,即链头指针 }; template <class T> LinkedStack<T>::LinkedStack() { // 构造函数,置空栈 top = new LinkNode<T>(); // 引入头指针:不存放数据 top->link = NULL; } template <class T> LinkedStack<T>::~LinkedStack() { // 析构函数,释放内存空间 makeEmpty(); } template <class T> void LinkedStack<T>::Push(const T x) { // 进栈:将元素值x插入到链式栈的栈顶,即链头 LinkNode<T> *newNode = new LinkNode<T>(); // 创建包含x的新结点 if(newNode == NULL) { cerr << "内存空间分配失败!" << endl; exit(1); } newNode->data = x; newNode->link = top->link; // 指向头指针的下一个结点:即栈中第一个存放有效数据的结点 top->link = newNode; // 头指针往前移 } template <class T> bool LinkedStack<T>::Pop() { // 出栈:删除栈顶结点 if(isEmpty()) return false; // 栈空,不出栈 LinkNode<T> *p = top->link; // 暂存栈顶元素 top->link = p->link; // 栈顶指针退到新的栈顶位置 delete p; p = NULL; return true; } template <class T> bool LinkedStack<T>::getTop(T &x) const { // 读取栈顶元素 if(isEmpty()) return false; x = top->link->data; // 栈不空,返回栈顶元素的值。这里top为头指针,所以栈顶元素为:top->link return true; } template <class T> bool LinkedStack<T>::isEmpty()const { // 判断栈是否为空 if(top->link == NULL) // 栈为空 return true; return false; } template <class T> int LinkedStack<T>::getSize()const { // 求栈的元素个数 int len = 0; LinkNode<T> *current = top->link; while(current != NULL) { len++; current = current->link; } return len; } template <class T> void LinkedStack<T>::makeEmpty() { // 清空栈的内容 LinkNode<T> *current = top->link; while(current != NULL) { top->link = current->link; // 保存链式栈准备要删除的结点的下一个结点,防止丢失 delete current; // 释放 current = NULL; // 先指向空 current = top->link; // 再指向剩下链表的首结点 } } template <class T> ostream& operator<<(ostream& out, LinkedStack<T>& s) { // 重载输出函数 LinkNode<T> *current = s.top->link; while(current != NULL) { out << current->data << " "; current = current->link; } return out; } #endif /* LinkedStack_h */
3.main.cpp
#include "LinkedStack.h" using namespace std; int main(int argc, const char * argv[]) { int n, x, choice, len; // val存储值,choose存储用户的选择 bool finished = false; LinkedStack<int> L; // 对象 while(!finished) { cout << "1:建栈:" << endl; cout << "2:进栈" << endl; cout << "3:出栈:" << endl; cout << "4:读取栈顶元素:" << endl; cout << "5:栈是否为空:" << endl; cout << "6:栈中的元素个数:" << endl; cout << "7:清空栈的内容:" << endl; cout << "8:输出栈中元素的值:" << endl; cout << "9:退出" << endl; cout << "请输入你的选择[1-9]:" << endl; cin >> choice; switch(choice) { case 1: cout << "请输入要进栈的数的个数:"; cin >> n; cout << "请输入要进栈的数(以空格隔开):" << endl; for(int i=0; i < n; i++) { cin >> x; L.Push(x); } break; case 2: cout << "请输入要进栈的数:"; cin >> x; L.Push(x); break; case 3: if(L.Pop()) cout << "出栈成功!" << endl; else cout << "栈为空!" << endl; break; case 4: if(L.getTop(x)) cout << "栈顶元素的值为:" << x << endl; else cout << "栈为空!" << endl; break; case 5: if(L.isEmpty()) cout << "栈为空!" << endl; else cout << "栈不为空!" << endl; break; case 6: len = L.getSize(); cout << "栈中的元素个数为:" << len << endl; break; case 7: L.makeEmpty(); // 清空栈 break; case 8: if(L.isEmpty()) cout << "栈为空!" << endl; else cout << L << endl; break; case 9: finished = true; break; default: cout << "输入错误,请重新输入!" << endl; } // switch } // while return 0; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
赞 (0)