數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列-創(chuàng)新互聯(lián)

一 .棧

一.順序棧的實(shí)現(xiàn)
A.棧的定義
1.棧是一種特殊的線性表
2.棧僅能在線性表的一端進(jìn)行操作
a.棧頂：允許操作的一端
b.棧底：不允許操作的一端
B.棧的特性
后進(jìn)先出(圖示)
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列
C.棧的操作
1.創(chuàng)建棧
2.銷(xiāo)毀棧
3.清空棧
4.進(jìn)棧
5.出棧
6.獲取棧頂元素
7.獲取棧的大小
D.棧的實(shí)現(xiàn)
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列

成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：做網(wǎng)站、網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿(mǎn)足客戶(hù)于互聯(lián)網(wǎng)時(shí)代的潛山網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
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)
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列
E.StaticStack設(shè)計(jì)要點(diǎn)
類(lèi)模板：
1.使用原生數(shù)組作為棧的存儲(chǔ)空間
2.使用模板參數(shù)決定棧的大容量
部分代碼如下

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

完整實(shí)現(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];//棧存儲(chǔ)空間
        int m_top;//棧頂元素標(biāo)識(shí)
        int m_size;//表示當(dāng)前棧里面的數(shù)據(jù)個(gè)數(shù)
    public:
        StaticStack()//構(gòu)造函數(shù)初始化成員
        {
            m_top=-1;
            m_size=0;
        }

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

        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;
        }
    };
}

二.鏈?zhǔn)綏５膶?shí)現(xiàn)
A.鏈?zhǔn)綏５脑O(shè)計(jì)要點(diǎn)
1.類(lèi)模板，抽象類(lèi)Stack的直接子類(lèi)
2.在內(nèi)部組合使用LinkList類(lèi)，實(shí)現(xiàn)類(lèi)的鏈?zhǔn)酱鎯?chǔ)
3.知道單鏈表成員對(duì)象的頭部進(jìn)行操作
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列
代碼實(shí)現(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();
        }
    };
}

二.隊(duì)列

一.順序隊(duì)列的實(shí)現(xiàn)
A.隊(duì)列的特性
1.先進(jìn)先出
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列
2.隊(duì)列是一種特殊的線性表
3.隊(duì)列僅能在線性表的兩端進(jìn)行操作
a.隊(duì)頭：取出數(shù)據(jù)元素的一端
b.隊(duì)尾：插入數(shù)據(jù)元素的一端
B.隊(duì)列的操作
1.創(chuàng)建隊(duì)列
2.銷(xiāo)毀隊(duì)列
3.情空隊(duì)列
4.進(jìn)隊(duì)列
5.出隊(duì)列
6.獲取隊(duì)頭元素
7.獲取隊(duì)列的長(zhǎng)度
C.隊(duì)列的實(shí)現(xiàn)
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列

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;
};

隊(duì)列的順序?qū)崿F(xiàn)
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列
D.StaticQueue設(shè)計(jì)要點(diǎn)
類(lèi)模板
1.使用原生數(shù)組作為隊(duì)列的存儲(chǔ)空間
2.使用模板參數(shù)決定隊(duì)列的大容量

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

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

#include "Queue.h"
#include "Exception.h"
//根據(jù)存儲(chǔ)空間的分配方式可以分為使用原生數(shù)組實(shí)現(xiàn)的靜態(tài)隊(duì)列和使用動(dòng)態(tài)分配的堆空間實(shí)現(xiàn)的動(dòng)態(tài)隊(duì)列。
namespace MyLib
{
    template <typename T,int N>
    class StaticQueue:public Queue<T>
    {
    protected:
        T m_space[N];//隊(duì)列的存儲(chǔ)空間
        int m_front;//隊(duì)頭元素的標(biāo)識(shí)
        int m_rear;//隊(duì)尾元素的標(biāo)識(shí)
        int m_length;//隊(duì)列長(zhǎng)度
    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;
        }
    };
}

二.隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列
A.鏈?zhǔn)疥?duì)列的設(shè)計(jì)要點(diǎn)
1.類(lèi)模板，抽象父類(lèi)Queue的直接子類(lèi)
2.在內(nèi)部使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)元素的存儲(chǔ)
3.只在鏈表的頭部和尾部進(jìn)程操作
數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列
完整的實(shí)現(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.棧只允許在線性表的一端進(jìn)行操作
3.StaticStack使用原生數(shù)組作為內(nèi)部存儲(chǔ)空間
4.StaticStack的大容量由模板參數(shù)決定
5.鏈?zhǔn)綏５膶?shí)現(xiàn)組合使用了單鏈表的對(duì)象
6.在單鏈表的頭部進(jìn)行操作能夠?qū)崿F(xiàn)高效的入棧和出棧操作
7.是一種特殊的線性表，具有先進(jìn)先出的特性
8.隊(duì)列只允許在線性表的兩端進(jìn)行操作，一端進(jìn)，一端出
9.StaticQueue使用原生數(shù)組作為內(nèi)部存儲(chǔ)空間
10.StaticQueue的大容量由模板參數(shù)決定
11.StaticQueue采用循環(huán)計(jì)數(shù)法提高隊(duì)列操作的效率

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

分享題目：數(shù)據(jù)結(jié)構(gòu)--棧與隊(duì)列-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://muchs.cn/article36/ddpepg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、電子商務(wù)、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、微信公眾號(hào)、全網(wǎng)營(yíng)銷(xiāo)推廣、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

網(wǎng)站建設(shè)網(wǎng)站維護(hù)公司