一 .栈

一.顺序栈的实现

A.栈的定义1.栈是一种特殊的线性表2.栈仅能在线性表的一端进行操作a.栈顶：允许操作的一端b.栈底：不允许操作的一端B.栈的特性后进先出(图示)C.栈的操作1.创建栈2.销毁栈3.清空栈4.进栈5.出栈6.获取栈顶元素7.获取栈的大小D.栈的实现

template 
    
     class Stack:public Object{    public:        virtual void push(const  T&e)=0;//入栈的操作        virtual void pop()=0;//出栈的操作        virtual T top()const =0;//栈顶元素        virtual void clear()=0;//清除        virtual int size()const=0;//栈的大小};
    

栈的顺序实现

E.StaticStack设计要点类模板：1.使用原生数组作为栈的存储空间2.使用模板参数决定栈的最大容量部分代码如下

template 
    
     class StaticStack:public Stack
     
      {    protected:        T m_space[N];//栈的存储空间        int m_top;//栈顶标识        int m_size;//当前栈的大小    public:        StaticStack();//初始化成员变量        int capacity()const;        //..............}
     
    

完整实现代码

#include "Stack.h"#include "Exception.h"namespace MyLib{    template
    
         class StaticStack: public Stack
     
          {    protected:        T m_space[N];//栈存储空间        int m_top;//栈顶元素标识        int m_size;//表示当前栈里面的数据个数    public:        StaticStack()//构造函数初始化成员        {            m_top=-1;            m_size=0;        }        int capacity()const        {            return N;//返回最大存储量        }        void push(const T &e)        {//入栈的操作            if(m_size
      
       0)            {//出栈的操作                m_top--;                m_size--;            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        T top() const        {            if(m_size>0)            {                return m_space[m_top];            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        void clear()        {            m_top=-1;            m_size=0;        }        int size()const        {            return m_size;        }    };}
      
     
    

二.链式栈的实现

A.链式栈的设计要点1.类模板，抽象类Stack的直接子类2.在内部组合使用LinkList类，实现类的链式存储3.知道单链表成员对象的头部进行操作代码实现如下

#include "Stack.h"#include "LinkList.h"namespace MyLib{    template 
    
         class LinkStack:public Stack
     
          {    protected:        LinkList
      
       m_list;    public:        void push(const T&e)        {            m_list.insert(0,e);        }        void pop()        {            if(m_list.length()>0)            {                m_list.remove(0);            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        T top() const        {            if(m_list.length()>0)            {                return m_list.get(0);            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        void clear()        {            m_list.clear();        }        int size() const        {            return m_list.length();        }    };}
      
     
    

二.队列

一.顺序队列的实现

A.队列的特性1.先进先出2.队列是一种特殊的线性表3.队列仅能在线性表的两端进行操作a.队头：取出数据元素的一端b.队尾：插入数据元素的一端B.队列的操作1.创建队列2.销毁队列3.情空队列4.进队列5.出队列6.获取队头元素7.获取队列的长度C.队列的实现

template 
    
     class Queue:public Object{    public:        virtual void add(const T&e)=0;        virtual void remove()=0;        virtual T front()const=0;        virtual void clear()=0;        virtual int length()const=0;};
    

队列的顺序实现

D.StaticQueue设计要点类模板1.使用原生数组作为队列的存储空间2.使用模板参数决定队列的最大容量

template
    
     class StaticQueue:public Queue
     
      {    protected:        T m_space[N];//队列存储空间        int m_front;//队头元素        int m_rear;//队尾元素        int m_length;//队列的长度    public:        StaticQueue();//初始化成员变量        int capacity()const;        //....
     
    

StaticQueue实现要点(循环计数法)

1.关键操作进队列：m_space[m_rear]=e;m_rear=(m_rear+1)%N出队列：m_front=(m_front+1)%N2.队列的状态队空:(m_length==0)&&(m_front==m_rear)队满:(m_length==N)&&(m_front==m_rear)实现代码如下：

#include "Queue.h"#include "Exception.h"//根据存储空间的分配方式可以分为使用原生数组实现的静态队列和使用动态分配的堆空间实现的动态队列。namespace MyLib{    template 
    
         class StaticQueue:public Queue
     
          {    protected:        T m_space[N];//队列的存储空间        int m_front;//队头元素的标识        int m_rear;//队尾元素的标识        int m_length;//队列长度    public:        StaticQueue()        {//初始化成员为0            m_length=0;            m_front=0;            m_rear=0;            //m_space[N]=0;        }        int capacity()const        {            return N;        }        void add(const T&e)        {            if(m_length
      
       0)            {                m_front=(m_front+1)%N;                m_length--;            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        T front()const        {            if(m_length>0)            {                return m_space[m_front];            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        void clear()        {            m_front=0;            m_rear=0;            m_length=0;        }        int length()const        {            return m_length;        }    };}
      
     
    

二.队列的链式存储实现

A.链式队列的设计要点1.类模板，抽象父类Queue的直接子类2.在内部使用链式结构实现元素的存储3.只在链表的头部和尾部进程操作完整的实现代码如下

#include "Queue.h"#include "LinkList.h"#include  
    
     using namespace std;namespace MyLib{    template
     
          class LinkQueue:public Queue
      
           {    protected:        LinkList
       
        m_list;    public:        LinkQueue()        {        }        void add(const T&e)        {            m_list.insert(e);        }        void remove()        {            if(m_list.length()>0)            {                m_list.remove(0);            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        T front() const        {            if(m_list.length()>0)            {                return m_list.get(0);            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        void clear()        {            m_list.clear();        }        int length() const        {            return m_list.length();        }    };}
       
      
     
    

小结：

1.栈是一种特殊的线性表2.栈只允许在线性表的一端进行操作3.StaticStack使用原生数组作为内部存储空间4.StaticStack的最大容量由模板参数决定5.链式栈的实现组合使用了单链表的对象6.在单链表的头部进行操作能够实现高效的入栈和出栈操作7.是一种特殊的线性表，具有先进先出的特性8.队列只允许在线性表的两端进行操作，一端进，一端出9.StaticQueue使用原生数组作为内部存储空间10.StaticQueue的最大容量由模板参数决定11.StaticQueue采用循环计数法提高队列操作的效率