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

本文貼出隊(duì)列爱咬、棧 的模板類代碼，可以直接調(diào)用份汗，如有需要可進(jìn)行相應(yīng)的修改盈电。
文中代碼均已在VS2015上測(cè)試，空指針均為nullptr（C++11）杯活。參考來(lái)源：慕課網(wǎng)

隊(duì)列

FIFO（First In First Out）先進(jìn)先出
隊(duì)頭挣轨，隊(duì)尾

普通隊(duì)列

環(huán)形隊(duì)列：充分利用內(nèi)存空間

示例（環(huán)形隊(duì)列）：

#ifndef MYQUEUE_H
#define MYQUEUE_H
/****************************/
/*環(huán)形隊(duì)列C++類[MyQueue.h]  */
/****************************/
class MyQueue
{
public:
    MyQueue(int queueCapacity);//InitQueue(&Q)創(chuàng)建隊(duì)列
    virtual ~MyQueue();//DestroyQueue(&Q)銷毀隊(duì)列
    void ClearQueue();//ClearQueue(&Q)清空隊(duì)列
    bool QueueEmpty()const;//QueueEmpty(Q)判空隊(duì)列
    bool QueueFull() const;//判滿隊(duì)列
    int QueueLength()const;//QueueLength(Q)隊(duì)列長(zhǎng)度
    bool EnQueue(int element);//EnQueue(&Q,element)新元素入隊(duì)
    bool DeQueue(/*int &element*/);//DeQueue(&Q,&element)首元素出隊(duì)
    void QueueTraverse();//QueueTraverse(Q,visit())遍歷隊(duì)列
private:
    int *m_pQueue;//隊(duì)列數(shù)組指針
    int m_iQueueLen;//隊(duì)列元素個(gè)數(shù)
    int m_iQueueCapacity;//隊(duì)列數(shù)組容量
    int m_iHead;
    int m_iTail;
};
#endif


/******************************/
/*環(huán)形隊(duì)列C++實(shí)現(xiàn)[MyQueue.cpp]*/
/******************************/
#include "MyQueue.h"
#include <iostream>
using namespace std;
MyQueue::MyQueue(int queueCapacity)
{
    m_iQueueCapacity = queueCapacity;
    //ClearQueue();
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLen = 0;
    m_pQueue = new int[m_iQueueCapacity];
}

MyQueue::~MyQueue()
{
    delete[]m_pQueue;
    m_pQueue = nullptr;
}

void MyQueue::ClearQueue()
{
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLen = 0;
}

bool MyQueue::QueueEmpty() const
{
    //return m_iQueueLen == 0 ? true : false;
    if (m_iQueueLen == 0)
    {
        return true;
    } 
    else
    {
        return false;
    }
}

bool MyQueue::QueueFull() const
{
    if (m_iQueueLen == m_iQueueCapacity)
    {
        return true;
    }
    return false;
}

int MyQueue::QueueLength() const
{
    return m_iQueueLen;
}

bool MyQueue::EnQueue(int element)
{
    if (QueueFull())
    {
        return false;
    }
    else 
    {
        m_pQueue[m_iTail] = element;
        m_iTail++;
        m_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLen++;
        return true;
    }
}

bool MyQueue::DeQueue(/*int & element*/)
{
    if (QueueEmpty())
    {
        return false;
    }
    else
    {
        /*element = m_pQueue[m_iHead];*/
        m_iHead++;
        m_iHead = m_iHead % m_iQueueCapacity;
        m_iQueueLen--;
        return true;
    }
    
}

void MyQueue::QueueTraverse()
{
    for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++)
    {
        cout << m_pQueue[i%m_iQueueCapacity]<<" ";
    }
    cout << endl;
}


/******************************/
/*環(huán)形隊(duì)列使用實(shí)例[Main.cpp]  */
/******************************/
#include"MyQueue.h"
#include <iostream>
using namespace std;

int main()
{
    MyQueue *p = new MyQueue(4);
    p->EnQueue(10);
    p->EnQueue(12);
    p->EnQueue(14);
    p->EnQueue(18);
    p->EnQueue(20);
    cout << p->QueueEmpty() << endl;
    cout << p->QueueFull() << endl;
    cout << p->QueueLength() << endl;
    p->QueueTraverse();
    p->DeQueue();
    p->QueueTraverse();
    p->EnQueue(200);
    p->QueueTraverse();
    p->ClearQueue();
    p->QueueTraverse();
    p->EnQueue(500);
    p->QueueTraverse();
    delete p;
    p = nullptr;
    return 0;
}

棧

LIFO（Last In First Out）后進(jìn)先出

棧頂

示例：

#ifndef MYSTACK_H
#define MYSTACK_H
/****************************/
/*棧C++類[MyStack.h]        */
/****************************/
class MyStack
{
public:
    MyStack(int size);
    ~MyStack();
    bool stackEmpty();
    bool stackFull();
    void clearStack();
    int stackLength();
    bool push(char elem);
    bool pop(char &elem);
    void stackTraverse(bool isFromBottom);

private:
    char *m_pBuffer;
    int m_iTop;
    int m_iSize;
};
#endif


/******************************/
/*棧C++實(shí)現(xiàn)[MyStack.cpp]      */
/******************************/
#include "MyStack.h"
#include <iostream>
using namespace std;
MyStack::MyStack(int size)
{
    m_iSize = size;
    m_pBuffer = new char[size];
    m_iTop = 0;
}

MyStack::~MyStack()
{
    delete[]m_pBuffer;
    m_pBuffer = nullptr;
}

bool MyStack::stackEmpty()
{
    if (0 == m_iTop)
    {
        return true;
    }
    return false;
}

bool MyStack::stackFull()
{
    if (m_iTop == m_iSize)
    {
        return true;
    }
    return false;
}

void MyStack::clearStack()
{
    m_iTop = 0;
}

int MyStack::stackLength()
{
    return m_iTop;
}

bool MyStack::push(char elem)
{
    if (stackFull())
    {
        return false;
    }
    m_pBuffer[m_iTop] = elem;
    m_iTop++;
    return true;
}

bool MyStack::pop(char &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;
    elem = m_pBuffer[m_iTop];
    return true;
}

void MyStack::stackTraverse(bool isFromBottom)
{
    if (isFromBottom)
    {
        for (int i = 0; i < stackLength(); i++)
        {
            cout << m_pBuffer[i] << " ";
        }
        cout << endl;
    }
    else
    {
        for (int i = stackLength()-1; i >=0; i--)
        {
            cout << m_pBuffer[i] << " ";
        }
        cout << endl;
    }
}


/******************************/
/*棧使用實(shí)例[Main.cpp]        */
/******************************/
#include"MyStack.h"
#include <iostream>
using namespace std;

int main()
{
    MyStack *p = new MyStack(3);
    cout << p->stackEmpty() << endl;
    cout << p->stackFull() << endl;
    cout << p->stackLength() << endl;
    p->push('c');p->push('+');p->push('+');
    p->stackTraverse(1);
    char elem = NULL;
    p->pop(elem);
    p->stackTraverse(0);
    p->clearStack();
    p->stackTraverse(0);
    return 0;
}

進(jìn)階

環(huán)形隊(duì)列模板類（注意，模板類 不支持頭文件與cpp文件分離）

#ifndef MYQUEUE_H
#define MYQUEUE_H
#include <iostream>
using namespace std;
/********************/
/*環(huán)形隊(duì)列C++實(shí)現(xiàn)     */
/********************/
template<class T>
class MyQueue
{
public:
    MyQueue(int queueCapacity);//InitQueue(&Q)創(chuàng)建隊(duì)列
    virtual ~MyQueue();//DestroyQueue(&Q)銷毀隊(duì)列
    void ClearQueue();//ClearQueue(&Q)清空隊(duì)列
    bool QueueEmpty()const;//QueueEmpty(Q)判空隊(duì)列
    bool QueueFull() const;//判滿隊(duì)列
    int QueueLength()const;//QueueLength(Q)隊(duì)列長(zhǎng)度
    bool EnQueue(T element);//EnQueue(&Q,element)新元素入隊(duì)
    bool DeQueue(/*int &element*/);//DeQueue(&Q,&element)首元素出隊(duì)
    void QueueTraverse();//QueueTraverse(Q,visit())遍歷隊(duì)列

private:
    T *m_pQueue;//隊(duì)列數(shù)組指針
    int m_iQueueLen;//隊(duì)列元素個(gè)數(shù)
    int m_iQueueCapacity;//隊(duì)列數(shù)組容量
    int m_iHead;
    int m_iTail;
};

template<class T>
MyQueue<T>::MyQueue(int queueCapacity)
{
    m_iQueueCapacity = queueCapacity;
    //ClearQueue();
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLen = 0;
    m_pQueue = new T[m_iQueueCapacity];
}
template<class T>
MyQueue<T>::~MyQueue()
{
    delete[]m_pQueue;
    m_pQueue = nullptr;
}
template<class T>
void MyQueue<T>::ClearQueue()
{
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLen = 0;
}
template<class T>
bool MyQueue<T>::QueueEmpty() const
{
    //return m_iQueueLen == 0 ? true : false;
    if (m_iQueueLen == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
template<class T>
bool MyQueue<T>::QueueFull() const
{
    if (m_iQueueLen == m_iQueueCapacity)
    {
        return true;
    }
    return false;
}
template<class T>
int MyQueue<T>::QueueLength() const
{
    return m_iQueueLen;
}
template<class T>
bool MyQueue<T>::EnQueue(T element)
{
    if (QueueFull())
    {
        return false;
    }
    else
    {
        m_pQueue[m_iTail] = element;
        m_iTail++;
        m_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLen++;
        return true;
    }
}
template<class T>
bool MyQueue<T>::DeQueue(/*T & element*/)
{
    if (QueueEmpty())
    {
        return false;
    }
    else
    {
        /*element = m_pQueue[m_iHead];*/
        m_iHead++;
        m_iHead = m_iHead % m_iQueueCapacity;
        m_iQueueLen--;
        return true;
    }

}
template<class T>
void MyQueue<T>::QueueTraverse()
{
    for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++)
    {
        cout << m_pQueue[i%m_iQueueCapacity] << " ";
    }
    cout << endl;
}

#endif// !MYQUEUE_H

棧模板類（注意轩猩，模板類 不支持頭文件與cpp文件分離）

#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using namespace std;

template<typename T>
class MyStack
{
public:
    MyStack(int size);
    ~MyStack();
    bool stackEmpty();
    bool stackFull();
    void clearStack();
    int stackLength();
    bool push(T elem);
    bool pop(T &elem);
    void stackTraverse(bool isFromBottom);

private:
    T *m_pBuffer;
    int m_iTop;
    int m_iSize;
};

template<typename T>
MyStack<T>::MyStack(int size)
{
    m_iSize = size;
    m_pBuffer = new T[size];
    m_iTop = 0;
}
template<typename T>
MyStack<T>::~MyStack()
{
    delete[]m_pBuffer;
    m_pBuffer = nullptr;
}
template<typename T>
bool MyStack<T>::stackEmpty()
{
    if (0 == m_iTop)
    {
        return true;
    }
    return false;
}
template<typename T>
bool MyStack<T>::stackFull()
{
    if (m_iTop == m_iSize)
    {
        return true;
    }
    return false;
}
template<typename T>
void MyStack<T>::clearStack()
{
    m_iTop = 0;
}
template<typename T>
int MyStack<T>::stackLength()
{
    return m_iTop;
}
template<typename T>
bool MyStack<T>::push(T elem)
{
    if (stackFull())
    {
        return false;
    }
    m_pBuffer[m_iTop] = elem;
    m_iTop++;
    return true;
}
template<typename T>
bool MyStack<T>::pop(T &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;
    elem = m_pBuffer[m_iTop];
    return true;
}
template<typename T>
void MyStack<T>::stackTraverse(bool isFromBottom)
{
    if (isFromBottom)
    {
        for (int i = 0; i < stackLength(); i++)
        {
            cout << m_pBuffer[i] << " ";
        }
        cout << endl;
    }
    else
    {
        for (int i = stackLength() - 1; i >= 0; i--)
        {
            cout << m_pBuffer[i] << " ";
        }
        cout << endl;
    }
}

#endif // !MYSTACK_H

棧應(yīng)用之進(jìn)制轉(zhuǎn)換

十進(jìn)制轉(zhuǎn)換二進(jìn)制卷扮，八進(jìn)制，十六進(jìn)制均践。
原理：短除法晤锹，將余數(shù)push進(jìn)棧，然后pop出棧彤委。
方案一：main.cpp

#include "MyStack.h"
#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16

int main()
{
    char num[] = "0123456789ABCDEF";
    MyStack<char> *p = new MyStack<char>(30);
    int N = 2016;
    int mod = 0;
    while (N != 0)
    {
        mod = N % HEXADECIMAL;
        p->push(num[mod]);
        N = N / HEXADECIMAL;
    }
    p->stackTraverse(false);
    return 0;
}

方案二：main.cpp

#include "MyStack.h"
#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16

int main()
{
    char num[] = "0123456789ABCDEF";
    MyStack<int> *p = new MyStack<int>(30);
    int N = 2016;
    int mod = 0;
    while (N != 0)
    {
        mod = N % HEXADECIMAL;
        p->push(mod);
        N = N / HEXADECIMAL;
    }
    int elem = 0;
    while(!p->stackEmpty())
    {
        p->pop(elem);
        cout << num[elem];
    }
    return 0;
}

棧應(yīng)用之括號(hào)匹配

任意輸入一組括號(hào)鞭铆，判斷括號(hào)是否匹配。[()]焦影、[()()]车遂、[[()]]

main.cpp

/**只限輸入[]()字符進(jìn)行檢測(cè)*/
#include "MyStack.h"
#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16

int main(void)
{
    MyStack<char> *pOrig = new MyStack<char>(30);
    MyStack<char> *pNeed = new MyStack<char>(30);
    char str[] = "[()]]";
    char currentNeed = 0;
    for(int i = 0;i < strlen(str);i++)
    {
        if (str[i] != currentNeed)
        {
            pOrig->push(str[i]);
            switch (str[i])
            {
            case '[':
                if (currentNeed != 0)
                {
                    pNeed->push(currentNeed);
                }
                currentNeed = ']';
                break;
            case '(':
                if (currentNeed != 0)
                {
                    pNeed->push(currentNeed);
                }
                currentNeed = ')';
                break;
            default:
                cout << "字符串不匹配" << endl;
                return 0;
            }
        }
        else
        {
            char elem;
            pOrig->pop(elem);
            if (!pNeed->pop(currentNeed))
            {
                currentNeed = 0;
            };
        }
    }
    if (pOrig->stackEmpty())
    {
        cout << "匹配"<<endl;
    }
    else
    {
        cout <<"不匹配"<< endl;
    }
    return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市斯辰，隨后出現(xiàn)的幾起案子舶担，更是在濱河造成了極大的恐慌，老刑警劉巖彬呻，帶你破解...
    沈念sama閱讀 221,430評(píng)論 6贊 515
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件衣陶，死亡現(xiàn)場(chǎng)離奇詭異柄瑰，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)剪况，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,406評(píng)論 3贊 398
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)教沾，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人译断，你說(shuō)我怎么就攤上這事授翻。” “怎么了孙咪？”我有些...
    開(kāi)封第一講書(shū)人閱讀 167,834評(píng)論 0贊 360
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵堪唐，是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我该贾，道長(zhǎng)，這世上最難降的妖魔是什么捌臊？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 59,543評(píng)論 1贊 296
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任杨蛋，我火速辦了婚禮，結(jié)果婚禮上理澎，老公的妹妹穿的比我還像新娘逞力。我一直安慰自己，他們只是感情好糠爬，可當(dāng)我...
    茶點(diǎn)故事閱讀 68,547評(píng)論 6贊 397
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布寇荧。 她就那樣靜靜地躺著，像睡著了一般执隧。 火紅的嫁衣襯著肌膚如雪揩抡。 梳的紋絲不亂的頭發(fā)上，一...
    開(kāi)封第一講書(shū)人閱讀 52,196評(píng)論 1贊 308
  • 城市分裂傳說(shuō)
    那天镀琉，我揣著相機(jī)與錄音峦嗤，去河邊找鬼。 笑死屋摔，一個(gè)胖子當(dāng)著我的面吹牛烁设，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播钓试，決...
    沈念sama閱讀 40,776評(píng)論 3贊 421
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼装黑，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了弓熏？” 一聲冷哼從身側(cè)響起恋谭，我...
    開(kāi)封第一講書(shū)人閱讀 39,671評(píng)論 0贊 276
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎挽鞠，沒(méi)想到半個(gè)月后箕别，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體铜幽，經(jīng)...
    沈念sama閱讀 46,221評(píng)論 1贊 320
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,303評(píng)論 3贊 340
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年串稀，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了除抛。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,444評(píng)論 1贊 352
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡母截，死狀恐怖到忽，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情清寇，我是刑警寧澤喘漏，帶...
    沈念sama閱讀 36,134評(píng)論 5贊 350
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站华烟，受9級(jí)特大地震影響翩迈，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜盔夜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,810評(píng)論 3贊 333
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一负饲、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧喂链，春花似錦返十、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,285評(píng)論 0贊 24
  • 一樁弒父案洞坑，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至蝇率，卻和暖如春迟杂，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背本慕。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,399評(píng)論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工逢慌， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人间狂。 一個(gè)月前我還...
    沈念sama閱讀 48,837評(píng)論 3贊 376
  • 代替公主和親
    正文 我出身青樓攻泼，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親鉴象。 傳聞我的和親對(duì)象是個(gè)殘疾皇子忙菠，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,455評(píng)論 2贊 359

推薦閱讀更多精彩內(nèi)容

  • Android 自定義View的各種姿勢(shì)1 Activity的顯示之ViewRootImpl詳解 Activity...
    passiontim閱讀 172,277評(píng)論 25贊 707
  • Spring Cloud為開(kāi)發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見(jiàn)模式的工具（例如配置管理，服務(wù)發(fā)現(xiàn)纺弊，斷路器牛欢，智...
    卡卡羅2017閱讀 134,695評(píng)論 18贊 139
  • 早上在地鐵上擠了近1個(gè)小時(shí)（平時(shí)不擠的時(shí)候20多分鐘就可以了），我還是低估了3號(hào)線～八點(diǎn)多一點(diǎn)從學(xué)校出發(fā)淆游，宣講9:...
    六月的碎碎念閱讀 365評(píng)論 0贊 0
  • 某人傍睹，你可能不知道隔盛，曾經(jīng)的傷害對(duì)我有多大，也不會(huì)知道我有多在乎拾稳！那樣決絕的離開(kāi)吮炕，不給我任何緩沖的機(jī)會(huì)，這些年我心里...
    等待2017閱讀 1,620評(píng)論 6贊 1