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)

相关推荐

  • 用C++实现一个链式栈的实例代码

    自定义一个链式栈,c++语言实现,不足之处,还望指正! 复制代码 代码如下: // MyStack.cpp : 定义控制台应用程序的入口点.//自己构造一个链式栈,具有push(入栈),pop(出栈),top(取得栈顶元素),size(返回栈大小),empty(判断是否为空)等功能#include "stdafx.h"#include <iostream>using namespace std;//构造栈的节点template <class T>struct N

  • C++模板类的用法

    本文实例讲述了C++模板类的用法,分享给大家供大家参考.具体实现方法如下: main.h头文件如下: 复制代码 代码如下: template <class T>  class actioncontainer  {  public:      //构造函数      actioncontainer()      {          m_nRedoPos = 0;          m_nUndoPos = 0;      }      //容器的接口函数      void add(T val

  • C++栈(stack)的模板类实现代码

    本文实例为大家分享了C++栈(stack)的模板类实现代码,供大家参考,具体内容如下 1.基本概念 栈中的元素遵守"先进后出"的原则(LIFO,Last In First Out) 只能在栈顶进行插入和删除操作 压栈(或推入.进栈)即push,将数据放入栈顶并将栈顶指针加一 出栈(或弹出)即pop,将数据从栈顶删除并将栈顶指针减一 栈的基本操作有:pop,push,判断空,获取栈顶元素,求栈大小 2.构造栈 可以使用数组构造栈,也可以使用单向链表构造,我觉得使用单向链表更加灵活方便,下

  • C++类模板与模板类深入详解

    1.在c++的Template中很多地方都用到了typename与class这两个关键字,而且有时候二者可以替换,那么是不是这两个关键字完全一样呢? 事实上class用于定义类,在模板引入c++后,最初定义模板的方法为:template<class T>,这里class关键字表明T是一个类型,后来为了避免class在这两个地方的使用可能给人带来混淆,所以引入了typename这个关键字,它的作用同class一样表明后面的符号为一个类型,这样在定义模板的时候就可以使用下面的方式了:      t

  • C++模板类的用法实例

    本文实例讲述了C++中模板类的用法,分享给大家供大家参考.具体方法如下: //#include "StdAfx.h #ifndef __AFXTLS_H__ #define __AFXTLS_H__ #include <Windows.h> class CSimpleList { public: CSimpleList(int nNextOffset=0); void Construct(int nNextOffset); //接口 BOOL IsEmpty() const; voi

  • 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; //

  • Linux静态链接库与模板类的处理方式

    在阅读本文之前,小编先给大家介绍一篇相关文章:Linux静态链接库使用类模板的快速排序算法 大家首先看下以上的文章对理解下面的知识点会有很大的帮助. 当模板遇到静态链接库会发生什么呢. 我们先按照常规思路去考虑一个静态链接库的步骤: 1.将某些功能提取出来,放进一个cpp文件,并将接口或者对外导出的类放在头文件中 2.gcc -c编译该文件,生成.o 3.ar命令将.o文件打包成.a,即静态链接库 4.编译main函数,并将该静态链接库链接,生成可执行文件. OK,按照这个思路,我们将之前写的快

  • Smarty模板类内部原理实例分析

    本文实例讲述了Smarty模板类内部原理.分享给大家供大家参考,具体如下: 之前在学习ThinkPHP的时候,有接触到Smarty模板类,但是一直不知道其内部实现的原理,博主今天终于知道了其内部原理,其实也挺简单的,然后写了一个迷你版的Smarty模板类,对理解其内部原理有了很大的帮助. 1.迷你版Smarty类 首先上代码,最后再进行讲解. 项目结构图 MiniSmarty类代码(MiniSmarty.class.php) <?php /** * 迷你模板类 */ class MiniSmar

  • C++利用链表模板类实现简易队列

    本文实例为大家分享了C++利用链表模板类实现一个队列的具体代码,供大家参考,具体内容如下 设计思想:MyQueue.h中对模板类进行声明和实现.首先定义结点的结构体,包含数据和指针域两部分.队列类定义中声明和实现了元素入队,出队,打印队首元素和队列等方法. 注意: 1)模板类的声明和定义不能分开(即不能分别放在.h和.cpp文件里). 2)声明新节点时,如果声明的节点是辅助操作的,可以不用new关键字,例如在析构函数中,直接用:Node<T>* temp:定义即可.如果声明一个新节点加入队列,

  • C++ 标准模板类详解

    目录 1 标准模板库 2.泛型编程 总结 1 标准模板库 STL提供了表示容器.迭代器.函数对象和算法的模板. 容器:类似数组存储若干值,切实同质的: 迭代器:遍历容器的对象,类似遍历数组的指针,广义指针: 算法:完成特定的任务: 函数对象:类对象或函数指针. 模板类 vector erase() 删除矢量中给定区间元素.接受两个迭代器参数(该参数定义了要删除的区间),迭代器1指向区间起始处,迭代器2指向区间终止处的后一个位置. // delete first and second elemen

  • Redis使用RedisTemplate模板类的常用操作方式

    目录 一.前言 二.Redis 数据结构简介 三.RedisTemplate对5种数据结构的操作 3.1 String字符串操作 3.2 list数组操作 3.3 Hash结构,map操作 3.4 Set集合操作 四.总结 一.前言 Redis是一个NoSQL(非关系型数据库)数据库之一,key-value存储系统或者说是一个缓存键值对数据库,具有如下特性: 基于内存运行,性能高效 支持分布式,理论上可以无限扩展 key-value存储系统 开源的使用ANSI C语言编写.遵守BSD协议.支持网

随机推荐