C++Stack栈类模版实例详解

1.栈的介绍

栈的实现方式分为3种

• 基于静态数组实现,内部预设一个很大的数组对象, 实现简单，缺点是空间受限。
• 基于动态数组实现,内部预设一个容量值,然后分配一段内存空间数组,如果入栈大于默认容量值时,则再次扩大分配新的内存数组,并将旧数组拷贝至新数组及释放旧数组.
• 基于双向循环链表实现

栈的函数需要实现如下所示:

• T pop() :出栈并返回栈顶元素
• voidpush(const T &t) :入栈
• const T & top() const :获取const类型栈顶元素
• T &top() :获取栈顶元素
• int length() const:获取数量(父类已经实现)void clear():清空栈(父类已经实现)

本章,我们实现的栈基于动态数组实现,它的父类是我们之前实现的Vector类：

C++动态数组模版类Vector实例详解

所以代码实现会非常简单.

2.栈实现

代码如下所示:

#ifndef Stack_H
#define Stack_H
#include "throw.h"
// throw.h里面定义了一个ThrowException抛异常的宏,如下所示:
//#include <iostream>
//using namespace std;
//#define ThrowException(errMsg)  {cout<<__FILE__<<" LINE"<<__LINE__<<": "<<errMsg<<endl; (throw errMsg);}
#include "Vector.h"
template<class T>
class Stack : public Vector<T>
{
public:
  T pop()
  {
      if(Vector<T>::isEmpty()) {        // 如果栈为空,则抛异常
          ThrowException("Stack is empty ...");
      }
      T t = Vector<T>::data()[Vector<T>::length() - 1];
      Vector<T>::resize(Vector<T>::length() - 1);
      return  t;
  }
  // 入栈,实际就是append尾部添加成员
  void push(const T &t)
  {
      Vector<T>::append(t);
  }
  T &top()
  {
      if(Vector<T>::isEmpty()) {
          ThrowException("Stack is empty ...");
      }
      return Vector<T>::data()[Vector<T>::length() - 1];
  }
  const T &top() const
  {
      if(Vector<T>::isEmpty()) {
          ThrowException("Stack is empty ...");
      }
      return Vector<T>::data()[Vector<T>::length() - 1];
  }
};
#endif // Stack_H

3.代码测试

int main(int argc, char *argv[])
{
  Stack<int> stack;
  cout<<"******* current length:"<<stack.length()<<endl;
  for(int i = 0; i < 5; i++) {
      cout<<"stack.push:"<<i<<endl;
      stack.push(i);
  }
  cout<<"******* current length:"<<stack.length()<<endl;
  while(!stack.isEmpty()) {
      cout<<"stack.pop:"<<stack.pop()<<endl;
  }
  return 0;
}

运行打印:

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注编程宝库的更多内容!

 strlenstrlen头文件＃include <string.h>格式size_t strlen( const char* str)功能计算字符串长度返回值返回字符串的长度//s ...