數(shù)據(jù)結(jié)構(gòu)--棧與隊列

一 .棧

一.順序棧的實現(xiàn)
A.棧的定義
1.棧是一種特殊的線性表
2.棧僅能在線性表的一端進行操作
a.棧頂：允許操作的一端
b.棧底：不允許操作的一端
B.棧的特性
后進先出(圖示)

C.棧的操作
1.創(chuàng)建棧
2.銷毀棧
3.清空棧
4.進棧
5.出棧
6.獲取棧頂元素
7.獲取棧的大小
D.棧的實現(xiàn)

template <typename T>
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;//棧的大小
};

棧的順序?qū)崿F(xiàn)

E.StaticStack設(shè)計要點
類模板：
1.使用原生數(shù)組作為棧的存儲空間
2.使用模板參數(shù)決定棧的最大容量
部分代碼如下

template <typename T,int N>
class StaticStack:public Stack<T>
{
    protected:
        T m_space[N];//棧的存儲空間
        int m_top;//棧頂標識
        int m_size;//當前棧的大小
    public:
        StaticStack();//初始化成員變量
        int capacity()const;
        //..............
}

完整實現(xiàn)代碼

#include "Stack.h"
#include "Exception.h"

namespace MyLib
{
    template<typename T,int N>
    class StaticStack: public Stack<T>
    {
    protected:
        T m_space[N];//棧存儲空間
        int m_top;//棧頂元素標識
        int m_size;//表示當前棧里面的數(shù)據(jù)個數(shù)
    public:
        StaticStack()//構(gòu)造函數(shù)初始化成員
        {
            m_top=-1;
            m_size=0;
        }

        int capacity()const
        {
            return N;//返回最大存儲量
        }

        void push(const T &e)
        {//入棧的操作
            if(m_size<N)
            {
                m_space[m_top+1]=e;
                m_top++;
                m_size++;
            }
            else
            {
                THROW_EXCEPTION(InvalidOperationException,"...");
            }
        }

        void pop()
        {
            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;
        }
    };
}

二.鏈式棧的實現(xiàn)
A.鏈式棧的設(shè)計要點
1.類模板，抽象類Stack的直接子類
2.在內(nèi)部組合使用LinkList類，實現(xiàn)類的鏈式存儲
3.知道單鏈表成員對象的頭部進行操作

代碼實現(xiàn)如下

#include "Stack.h"
#include "LinkList.h"
namespace MyLib
{
    template <typename T>
    class LinkStack:public Stack<T>
    {
    protected:
        LinkList<T>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();
        }
    };
}

二.隊列

一.順序隊列的實現(xiàn)
A.隊列的特性
1.先進先出

2.隊列是一種特殊的線性表
3.隊列僅能在線性表的兩端進行操作
a.隊頭：取出數(shù)據(jù)元素的一端
b.隊尾：插入數(shù)據(jù)元素的一端
B.隊列的操作
1.創(chuàng)建隊列
2.銷毀隊列
3.情空隊列
4.進隊列
5.出隊列
6.獲取隊頭元素
7.獲取隊列的長度
C.隊列的實現(xiàn)

template <typename T>
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;
};

隊列的順序?qū)崿F(xiàn)

D.StaticQueue設(shè)計要點
類模板
1.使用原生數(shù)組作為隊列的存儲空間
2.使用模板參數(shù)決定隊列的最大容量

template<typename T,int  N>
class StaticQueue:public Queue<T>
{
    protected:
        T m_space[N];//隊列存儲空間
        int m_front;//隊頭元素
        int m_rear;//隊尾元素
        int m_length;//隊列的長度
    public:
        StaticQueue();//初始化成員變量
        int capacity()const;
        //....

StaticQueue實現(xiàn)要點(循環(huán)計數(shù)法)
1.關(guān)鍵操作
進隊列：m_space[m_rear]=e;m_rear=(m_rear+1)%N
出隊列：m_front=(m_front+1)%N
2.隊列的狀態(tài)
隊空:(m_length==0)&&(m_front==m_rear)
隊滿:(m_length==N)&&(m_front==m_rear)
實現(xiàn)代碼如下：

#include "Queue.h"
#include "Exception.h"
//根據(jù)存儲空間的分配方式可以分為使用原生數(shù)組實現(xiàn)的靜態(tài)隊列和使用動態(tài)分配的堆空間實現(xiàn)的動態(tài)隊列。
namespace MyLib
{
    template <typename T,int N>
    class StaticQueue:public Queue<T>
    {
    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<N)
            {
                m_space[m_rear]=e;
                m_rear=(m_rear+1)%N;
                m_length++;
            }
            else
            {
                THROW_EXCEPTION(InvalidOperationException,"...");
            }
        }

        void remove()
        {
            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;
        }
    };
}

二.隊列的鏈式存儲實現(xiàn)

A.鏈式隊列的設(shè)計要點
1.類模板，抽象父類Queue的直接子類
2.在內(nèi)部使用鏈式結(jié)構(gòu)實現(xiàn)元素的存儲
3.只在鏈表的頭部和尾部進程操作

完整的實現(xiàn)代碼如下

#include "Queue.h"
#include "LinkList.h"
#include  <iostream>

using namespace std;

namespace MyLib
{
    template<typename T>
    class LinkQueue:public Queue<T>
    {
    protected:
        LinkList<T>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();
        }
    };
}

小結(jié)：
1.棧是一種特殊的線性表
2.棧只允許在線性表的一端進行操作
3.StaticStack使用原生數(shù)組作為內(nèi)部存儲空間
4.StaticStack的最大容量由模板參數(shù)決定
5.鏈式棧的實現(xiàn)組合使用了單鏈表的對象
6.在單鏈表的頭部進行操作能夠?qū)崿F(xiàn)高效的入棧和出棧操作
7.是一種特殊的線性表，具有先進先出的特性
8.隊列只允許在線性表的兩端進行操作，一端進，一端出
9.StaticQueue使用原生數(shù)組作為內(nèi)部存儲空間
10.StaticQueue的最大容量由模板參數(shù)決定
11.StaticQueue采用循環(huán)計數(shù)法提高隊列操作的效率