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

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

隊列

FIFO（First In First Out）先進先出
隊頭，隊尾

普通隊列

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

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

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


/******************************/
/*環(huán)形隊列C++實現(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)形隊列使用實例[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）后進先出

棧頂

示例：

#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++實現(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;
    }
}


/******************************/
/*棧使用實例[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;
}

進階

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

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

private:
    T *m_pQueue;//隊列數(shù)組指針
    int m_iQueueLen;//隊列元素個數(shù)
    int m_iQueueCapacity;//隊列數(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)用之進制轉(zhuǎn)換

十進制轉(zhuǎn)換二進制，八進制，十六進制。
原理：短除法，將余數(shù)push進棧，然后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)用之括號匹配

任意輸入一組括號，判斷括號是否匹配。[()]、[()()]、[[()]]

main.cpp

/**只限輸入[]()字符進行檢測*/
#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)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Android 自定義View的各種姿勢1 Activity的顯示之ViewRootImpl詳解 Activity...
    passiontim閱讀 178,725評論 25贊 709
  • Spring Cloud為開發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見模式的工具（例如配置管理，服務(wù)發(fā)現(xiàn)，斷路器，智...
    卡卡羅2017閱讀 136,502評論 19贊 139
  • 早上在地鐵上擠了近1個小時（平時不擠的時候20多分鐘就可以了），我還是低估了3號線～八點多一點從學(xué)校出發(fā)，宣講9:...
    六月的碎碎念閱讀 440評論 0贊 0
  • 某人，你可能不知道，曾經(jīng)的傷害對我有多大，也不會知道我有多在乎！那樣決絕的離開，不給我任何緩沖的機會，這些年我心里...
    等待2017閱讀 1,701評論 6贊 1

友情鏈接更多精彩內(nèi)容