• 认真地记录技术中遇到的坑！
  • 能摸鱼真是太好啦！嘿嘿嘿！
> 算法数据结构 > 栈与队列

栈与队列

算法数据结构 Moxun 7年前 (2018-03-28) 2413次浏览 3个评论

基础

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许在一端进行插入操作，另一端进行删除操作的线性表。

栈

栈是一种先进后出的结构。它是仅限定在表尾进行删除和插入操作的线性表。我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出（LIFO：Last In First Out）的线性表，简称LIFO结构。
（比如，很多软件提供的撤销操作就是用栈来实现的）

  • 栈首先是线性表（有前驱和后继）
  • 栈的表尾指的是栈顶而不是栈底
  • 栈底是固定的，最先进的只能在栈底

栈的插入操作叫做进栈，也称为压栈、入栈。
栈的删除操作，叫做出栈，也有的叫做弹栈。

栈的出栈不一定是先进去的后出来（从时间上来看），比如1，2,3按顺序进栈，1先进去再出来，2进，3进，3出，2出，这个顺序就说明了先进的从时间上看不一定最后出。

栈的抽象数据结构

理论上说，线性表具有的操作，栈都具备，但是因为它限制了操作的位置，所以插入和删除是有不同之处的，栈的进栈操作起名为push，出栈操作起名为pop。栈的存储结构也分顺序存储和链式存储两种。

template
class SeqStack
{
    using size_t = unsigned int;
    T *m_pSeqStack{ nullptr };
    int m_iCurrLen{ 0 };
    unsigned int m_iMaxSize{ 0 };
    int m_iTop{ -1 };  //栈顶指针始终指向栈顶元素，当栈顶指针小于0时表示空栈
public:
    bool empty();

    size_t size();

    size_t maxSize();

    //清空栈中的元素，不是销毁栈
    void clear();

    T& top();

    void push(const T & value);

    T pop();


    SeqStack();
    ~SeqStack();
};

栈的顺序存储结构实现

#ifndef SEQSTACK_H_
#define SEQSTACK_H_

//顺序存储的方式实现栈

template

//描述一个栈需要：最大长度，存储元素的数组首地址，当前长度，栈顶指针
//顺序实现使用动态数组，栈结构本身是后进先出的，栈底元素的变化最小，所以把数组首起始位置作为栈底
//支持的操作：1.空判断 2.求长度（数据长度）3.求栈能容纳的最大数据量4.进栈5.出栈（数据元素要从栈中删除）6.获取栈顶元素7.清空栈中的元素

class SeqStack
{
    using size_t = unsigned int;
    T *m_pSeqStack{ nullptr };
    int m_iCurrLen{ 0 };
    unsigned int m_iMaxSize{ 0 };
    int m_iTop{ -1 };  //栈顶指针始终指向栈顶元素，当栈顶指针小于0时表示空栈
public:
    bool empty()
    {
        if (m_iTop < 0)
        {
            return true;
        }
        return false;
    }

    size_t size()
    {
        return m_iCurrLen;
    }

    size_t maxSize()
    {
        return m_iMaxSize;
    }

    //清空栈中的元素，不是销毁栈
    void clear()
    {
        memset(m_pSeqStack, 0x00, m_iCurrLen);
        m_iTop = -1;
        m_iCurrLen = 0;
    }

    T& top()
    {
        if (true == empty())
        {
            throw runtime_error("Stack is empty!");
        }
        return m_pSeqStack[m_iTop];
    }

    void push(const T & value)
    {
        if (m_iCurrLen +1 == m_iMaxSize)
        {
            throw runtime_error("Run out of Space!");
        }
        ++m_iTop;
        m_pSeqStack[m_iTop] = value;
        ++m_iCurrLen;
    }

    T pop()
    {
        if (true == empty())
        {
            throw runtime_error("Stack is empty!");
        }
        T value = m_pSeqStack[m_iTop];
        --m_iTop;
        --m_iCurrLen;
        return value;
    }


    SeqStack();
    ~SeqStack();



};


#endif

template
SeqStack::SeqStack()
{
    m_pSeqStack = new T[2000];
    m_iMaxSize = 2000 / sizeof(T);

}

template
SeqStack::~SeqStack()
{
    if (m_pSeqStack != nullptr)
    {
        delete[] m_pSeqStack;
        m_pSeqStack = nullptr;
    }
}

两栈共享空间：
模型：栈的数据类型必须是相同的，而且在两个栈的空间需求是正好相反的，例如栈1有数据进栈，栈2就有数据出栈。像这种应用模型，可以使两个栈共享一个大数组。在进行每一步操作时需要判断是要在哪个栈上进行。

栈A和栈B共享大数组，A的栈底从0号位置开始，B的栈底从MAXSIZE-1位置开始，判断A栈是否为空，条件是top （栈顶指针） ==-1，判断B栈是否为空，条件是 top == MAXSIZE，这里注意下栈顶指针的增长方向，A栈的top在进栈情况下是增大的，而B栈的top在进栈情况下是减小的。判断栈满的条件是： topA+1 == topB。

栈的链式存储结构及实现

链栈的逻辑结构通过指针来维护。结点的ADT如下：

template
class Node
{
public:
    T m_data;       //数据域
    Node *m_next;    //指针域，指向后继结点
    Node(const T &value, const Node *pNext = nullptr) :m_data(value), m_next(pNext) {};
    Node(const Node *pNext = nullptr) :m_next(pNext) {};
    Node(const Node &value) = delete;  //禁止拷贝构造
    Node &operator = (const Node & leftValue) = delete; //禁止赋值
};

链栈的绝大部分操作和单链表是类似的，只是在插入和删除操作上有所不同。

链式栈的简单实现：

//栈的逻辑结构是：线性关系
//描述一个栈的数据要素：当前数据长度、栈顶指针
template
class LinkStack
{
    using size_t = unsigned int;
    size_t m_iSzie{ 0U };
    StackNode *m_pTop{ nullptr };        //指向栈顶元素的指针
public:
    LinkStack() =default;
    ~LinkStack() = default;
    LinkStack(const T & value) = delete;
    LinkStack &operator = (const T &leftValue) = delete;
    size_t size()
    {
        return m_iSzie;
    }

    bool empty()
    {
        if (nullptr == m_pTop)
        {
            return true;
        }
        return false;
    }

    void push(const T value);

    //获取栈顶元素
    T& top();

    //栈顶元素出栈
    T pop();

    //清空中的所有元素
    void clear();

};



#endif

template
void LinkStack::push(const T value)
{
    //用传入的参数书构造新的结点
    auto pNode = new StackNode(value, nullptr);

    //新结点的指针域指向栈顶指针所指对象（注意栈顶指针，它所表示的就是使这个指针指向栈顶）
    pNode->m_next = m_pTop;

    //栈顶指针指向新结点
    m_pTop = pNode;

    //栈的长度自增1
    ++m_iSzie;
}

template
T & LinkStack::top()
{
    if (true == empty())
    {
        throw runtime_error("Stack is empty!");
    }
    return m_pTop->m_data;
}

template
T LinkStack::pop()
{
    if (true == empty())
    {
        throw runtime_error("Stack is empty!");
    }

    auto topValue = m_pTop->m_data;

    auto pTop = m_pTop;
    m_pTop = m_pTop->m_next;

    //释放栈顶元素
    if (pTop != nullptr)
    {
        delete pTop;
        pTop = nullptr;
    }

    --m_iSzie;
    return topValue;
}

template
void LinkStack::clear()
{
    while (m_pTop->m_next != nullptr)
    {
        auto pTop = m_pTop;
        m_pTop = m_pTop->m_next;
        if (nullptr != pTop)
        {
            delete pTop;
            pTop = nullptr;
        }
        --m_iSzie;
    }

    //删除最后一个结点
    if (nullptr == m_pTop->m_next)
    {
        delete m_pTop;
        m_pTop = nullptr;
        --m_iSzie;
        std::cout << "删除最后的结点！" << std::endl;
    }
}

注：因为输出运算符的求值顺序是不定的，所以在做测试验证时，不支持类似：cout << myLinkStack.pop() << myLinkStack.size() << endl;这样的操作，因为求值顺序的不定，这条输出的结果的正确性是不定的，所以为了保证正确的输出，必须将pop和size拆成两个输出。

栈的应用——递归

斐波那契数列的特征：前面相邻两项之和，构成了最后一项。用数学语言描述这个特征：

F(n) = 0，当n=0
F(n) = 1，当n=1
F(n) = F(n-1) +F(n-2)，当n>1

斐波那契数列的递归调用实现：

int Fbi(int i)
{
    if (i < 2)
    {
        //输入是不是等于0，等于0输出0，否则输出1
        return i == 0 ? 0 : 1;
    }
    return Fbi(i - 1) + Fbi(i - 2);
}

其中 if(i<2)是递归的终止条件，递归函数必须要有递归终止条件，当满足此条件是递归不再执行，此时函数直接退出，而不是再次引用自己。所谓递归函数实际上就是函数自己直接调用自己或者通过一些列的调用语句间接的调用自己的函数，你可以理解为函数调用了另外一个函数，而被调函数只是和自己长的一模一样而已。

递归算法能使代码逻辑清晰，但是会建立大量的函数副本，会耗费大量的内存和时间，而非递归函数则无此副作用，只是代码理解上会比递归函数稍微难一些而已。

我们用数学语言来描述递归函数的执行过程，假设求Fbi(5)的值，其执行过程如下：
Fbi(5) = Fbi(4)+ Fbi(3) = Fbi(3)+ Fbi(2) + Fbi(2) + Fbi(1) = Fbi(2) + Fbi(1) + Fbi(1) + Fbi(0) + Fbi(1) + Fbi(0) +1 = Fbi(1) + Fbi(0) +1 +1 +0 +1 +0 +1 =
1+0+1+1+0+1+0+1 = 5。

关于汉诺塔问题的天才解法就是递归算法的经典体现。

在上述数学描述中，可以发现递归执行过程包含两个必要的操作流程：前行和逆回，在前行过程中，对于每一层递归，函数的局部变量、参数值和返回地址都被压入栈中。在退出阶段，位于栈顶的局部变量、参数值和返回地址被弹栈，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。 就是说编译器实现递归是通过栈来实现的。

栈的应用——四则运算表达式求值

后缀表达式（逆波兰表示法）

逆波兰表示法举例：
表达式： 9+(3-1) *3 +10/2
等价的逆波兰表达式：9 3 1 - 3 * + 10 2 / （也叫后缀表达式，叫后缀的原因是所有的符号都在运算数字的后面出现）

逆波兰表示法的计算机求解：使用栈
计算规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，直到获得最终的结果（此时栈为空）。注意左右操作数，先出栈的数为右操作数，后出栈的数为左操作数。

中缀表达式

平时使用的规则四则运算表达式叫做中缀表达式。例：
9+(3-1) *3 +10/2就是中缀表达式。
中缀表达式转后缀表达式的规则：
从左到右遍历中缀表达式的每个数字和符号，如果是数字就输出，即成为后缀表达式的一部分，若是符号，则判断其与栈顶符号的优先级，如果是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

队列

队列：只允许在一端进行插入操作，另一端进行删除操作的线性表。是先进先出（First In First Out）的线性表简称FIFO，允许插入的一端称为队尾，允许删除的一头称为队头。假设队列是q=(a1,a2,a3……,an)，那么a1就是对头元素，而an为队尾元素。

顺序存储结构的队列实现：
在队尾插入和对头出队的时间复杂度均为O(1)

#ifndef SEQQUEUE_H_
#define SEQQUEUE_H_

//队列的顺序结构实现(循环队列）
//循环队列，首尾相接，目的是为了解决假溢出，队尾插入，队头删除
//队列判空的条件是首指针（front）==尾指针（rear），假设队列的最大长度是QueueSize，注意队尾指向的是最后一个元素的下一个紧邻的位置
//队列判满的条件是(rear + 1) % QueueSize == front
//求队列长度的通用公式是：（rear - front +QueueSize）% QueueSize


//根据上述分析，描述一个队列的要数是：首指针，尾指针，队列最大长度，以及存储数据所使用的大数组
template

class SeqQueue
{
    using size_t = unsigned int;
    int m_iRear{ 0 };
    int m_iFront{ 0 };
    int m_iMaxSize{ 1000 };
    T *m_pQueue = new T[m_iMaxSize];

    bool full()
    {
        if ((m_iRear+1)%m_iMaxSize == m_iFront)
        {
            return true;
        }
        return false;
    }

public:
    bool empty()
    {
        if (m_iRear == m_iFront)
        {
            return true;
        }
        return false;
    }

    size_t size()
    {
        return (m_iRear - m_iFront + m_iMaxSize) % m_iMaxSize;
    }

    //清楚队列中的所有元素
    void clear()
    {
        memset(m_pQueue, 0x00, m_iMaxSize);
        m_iFront = 0;
        m_iRear = m_iFront;
    }

    //队头出，队尾进
    bool enQueue(const T & value);

    bool deQueue(T & value);




};



#endif

template
bool SeqQueue::enQueue(const T & value)
{
    if (true == full())
    {
        return false;
    }

    m_pQueue[m_iRear] = value;

    //将队列想象成一个首尾相连的环来理解
    m_iRear = (m_iRear + 1) % m_iMaxSize;

    return true;
}

template
bool SeqQueue::deQueue(T &value)
{
    if (true == empty())
    {
        return false;
    }

    value = m_pQueue[m_iFront];

    //将队列想象成一个首尾相连的环来理解这句代码
    m_iFront = (m_iFront + 1) % m_iMaxSize;
    // TODO: 在此处插入 return 语句
    return false;
}

链式存储结构的队列实现：
队列的链式存储结构，实际上还是单链表，只不过它只能尾进头出罢了，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点。空队列时，front（头指针）和rear（尾指针）都指向头结点。代码示例如下：

#ifndef LINKQUEUE_H_
#define LINKQUEUE_H_

//队列的链式存储实现

//队列的结点类型
template
class LinkQueNode
{
public:
    T m_data;
    LinkQueNode *m_next{ nullptr };
    LinkQueNode(LinkQueNode *pNext = nullptr) :m_next(pNext) {};
    LinkQueNode(const T & value, LinkQueNode *pNext = nullptr) : m_data(value), m_next(pNext) {};
    LinkQueNode(LinkQueNode &value) = delete;    //禁止拷贝
    LinkQueNode & operator = (const T & leftValue) = delete;//禁止赋值

};

template
class LinkQueue
{
public:
    bool empty()
    {
        if (m_pFront == m_pRear)
        {
            return true;
        }
        return false;
    }

    int size()
    {
        return m_iSize;
    }

    void enqueue(const T & value);

    T dequeue();

    //从头结点开始一个一个删除
    void clear();


    LinkQueue();
    ~LinkQueue();

private:
    int m_iSize{ 0 };   //队列长度
    LinkQueNode *m_pFront;       //队头指针（在构造函数里初始化）以免产生误解（当队列为空时，队头指针和队尾指针都指向头结点）
    LinkQueNode *m_pRear;        //队尾指针
};






#endif // 

template
void LinkQueue::enqueue(const T & value)
{
    auto pTailNode = new LinkQueNode(value);
    //注意当链队列为空的时候，头指针的变化
    if (true == empty())
    {
        //尾指针指向新加入的结点
        m_pRear = pTailNode;
        //头指针的指针域指向这个结点（先进先出）
        m_pFront->m_next = pTailNode;

    }
    else
    {
        m_pRear->m_next = pTailNode;
        m_pRear = pTailNode;
    }
    ++m_iSize;
}

template
T LinkQueue::dequeue()
{
    if (true == empty())
    {
        throw runtime_error("LinkQue is empty!");
    }

    auto pFront = m_pFront->m_next;
    //如果被删除的结点同时是尾结点，删除后令尾指针指向头结点
    if (pFront == m_pRear)
    {
        m_pRear = m_pFront;
    }

    auto retValue = pFront->m_data;

    m_pFront->m_next = m_pFront->m_next->m_next;

    if (nullptr != pFront)
    {
        delete pFront;
        pFront = nullptr;
    }
    --m_iSize;
    return retValue;
}

template
void LinkQueue::clear()
{
    if (true == empty())
    {
        return;
    }
    //从头结点开始删除
    LinkQueNode *p{ nullptr };
    LinkQueNode *q{ nullptr };

    //绝大部分的操作都要从头结点开始
    p = m_pFront->m_next; //令p指向首元结点
    while (p != nullptr) //没到表尾
    {
        q = p->m_next; //保存p下一节点的地址
        if (nullptr != p)
        {
            delete p;
            p = nullptr;
        }
        p = q;
        --m_iSize;
    }


    m_pRear = m_pFront;
    m_pFront->m_next = nullptr;


    std::cout << "clear:队列长度是：" << m_iSize << endl;

}

template
LinkQueue::LinkQueue()
{
    auto pHeadNode = new LinkQueNode(nullptr);
    m_pFront = pHeadNode;
    m_pRear = pHeadNode;
}

template
LinkQueue::~LinkQueue()
{
    clear();
    if (nullptr != m_pFront)
    {
        delete m_pFront;
        m_pFront = nullptr;
    }
}
转载请注明出处 栈与队列
喜欢 (2)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi，您需要填写昵称和邮箱！

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(3)个小伙伴在吐槽
  1. 试试水
    12019-10-27 09:36 回复
  2. 能问一下，那个日历的是怎么做的吗？
    齐齐齐2018-03-29 15:31 回复
    • 悠悠
      那个日历是WordPress自带的，我只是调了一下样式。
      悠悠2018-03-29 22:07 回复