当前位置:编程学习 > C/C++ >>

栈的两种C++实现

 

栈是应用最广泛的数据结构之一,很有必要对其进行一些总结。

 

栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈的顶(top),它是后进先出(LIFO)的。对栈的基本操作只有push(进栈)和pop(出栈)两种,前者相当于插入,后者相当于删除最后的元素。

 

栈本质上是一种受限制的表,所以可以使用任何一种表的形式来实现它,最常用的是使用链表和数组。

 

使用链表的特点:不需要指定其大小,不会浪费空间;进栈和出栈涉及到动态内存的申请释放,时间花销大;

 

使用数组的特点:需要指定其大小,有可能浪费空间,也可能空间不够用;进栈和出栈不涉及动态内存的申请释放,因此时间上几乎没有花销;另外支持随机存取。

 

 

 

 

结论:一般使用链表是首选,除非满足两个条件:1.对运行时的效率要求极高;2.能够预知栈需要的空间大小。

 

 

 

 下面是利用单链表实现的栈:

 

/*stack.h  (slist.h is the heaher file of single list class SList)*/ 

#include "slist.h"  

 

template<typename T> 

class Stack 

public: 

    Stack(); 

    Stack(const T& initdata); 

    ~Stack(); 

public: 

    int IsEmpty() const; 

    void MakeEmpty();//清空。  

    int GetCount() const; 

    //void DisposeStack();//清空。对于用链表实现的Stack,这两个清空的含义相同,对于用数组实现的,两者含义不一样。  

    int Push(T data); 

    int Pop(T *data = NULL); 

    int Top(T *data) const; 

 

private: 

     SList<T> slist; 

}; 

 

 

template<typename T> 

inline Stack<T>::Stack():slist() 

 

template<typename T> 

inline Stack<T>::Stack(const T& initdata):slist(initdata) 

 

template<typename T> 

inline Stack<T>::~Stack() 

 

template<typename T> 

inline int Stack<T>::IsEmpty() const 

    return slist.IsEmpty(); 

 

template<typename T> 

inline void Stack<T>::MakeEmpty() 

    slist.RemoveAll(); 

 

template<typename T> 

inline int Stack<T>::GetCount() const 

    return slist.GetCount(); 

/*template<typename T>

inline void Stack<T>::DisposeStack()

{

    slist.RemoveAll();

}*/ 

 

template<typename T> 

inline int Stack<T>::Push(T data) 

    return slist.AddHead(data); 

 

template<typename T> 

inline int Stack<T>::Pop(T *data) 

    if (IsEmpty()) 

        return 0; 

 

    if (data) 

        Top(data); 

 

    slist.RemoveHead(); 

    return 1; 

 

template<typename T> 

inline int Stack<T>::Top(T *data) const 

    ASSERT(data); 

 

    if (IsEmpty()) 

        return 0; 

 

    *data = slist.GetHead(); 

    return 1; 

 

 

 

 

下面是利用数组实现的栈:

 

/*stackarray.h*/

 

#include <assert.h>

 

const int EmptyTOS=-1;

const int MinStackSize=5;

const int MaxStackSize=500;

 

 

template<typename T>

class StackArray

{

public:

       StackArray(int maxsize=MaxStackSize);

       ~StackArray();

public:

       int IsEmpty() const;

       void MakeEmpty();

       int GetCount() const;

       int IsFull();

       int Resize(int newmaxsize);//change the capacity.

       int Push(const T& data);

       int Pop(T *data = NULL);

       int Top(T *data) const;

private:

       void DisposeStack();//释放数组所占的内存,即栈被销毁.

private:

       int capacity;

       int tos;//Top of stack for now.

       T* array;

};

 

template<typename T>

inline StackArray<T>::StackArray(int maxsize):capacity(maxsize),tos(EmptyTOS),array(NULL)

{

       ASSERT(capacity>=MinStackSize);

      

       try

       {

              array=new T[capacity];

       }

       catch(std::bad_alloc&)

       {

       }

}

 

template<typename T>

inline StackArray<T>::~StackArray()

{

 

       DisposeStack();

}

 

template<typename T>

inline void StackArray<T>::DisposeStack()

{

       capacity=0;

       tos=EmptyTOS;

       if(array)

       {

              delete [] array;

       }

}

 

template<typename T>

inline int StackArray<T>::IsEmpty() const

{

       return EmptyTOS==tos;

}

 

 

template<typename T>

inline void StackArray<T>::MakeEmpty()

{

       tos=EmptyTOS;

}

 

template<typename T>

inline int StackArray<T>::GetCount() const

{

      

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,