34_栈的概念及实现（上）

关键词：栈的定义、栈的操作、栈的实现、StaticStack.h的实现

0. 栈的定义

• 栈是一种特殊的线性表
• 栈仅能在线性表的一端进行操作
  栈顶(Top)：允许操作的一端
  栈底(Bottom)：不允许操作的一端

1. 栈的特性

后进先出（Last In First Out）

栈的特性示意图

2. 栈的操作

• 创建栈(Stack())
• 销毁栈(~Stack())
• 清空栈(clear())
• 进栈(push())
• 出栈(pop())
• 获取栈顶元素(top())
• 获取栈的大小(size())

3. 栈的实现

栈的继承关系图

Stack.h

#ifndef STACK_H
#define STACK_H

#include "Object.h"

namespace DTLib
{

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

}

#endif // STACK_H

4. 栈的顺序实现

StaticStack示意图

• StaticStack设计要点：
  • 类模板
  • 使用原生数组作为栈的存储空间
  • 使用模板参数决定栈的最大容量

StaticStack.h

#ifndef STATICSTACK_H
#define STATICSTACK_H

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

namespace DTLib
{

template < typename T, int N >
class StaticStack : public Stack<T>
{
protected:
    T m_space[N];
    int m_top;
    int m_size;
public:
    StaticStack();
    void push (const T& e);
    void pop();
    T top() const;
    void clear();
    int size() const;
    int capacity() const;
};

template < typename T, int N >
StaticStack<T,N>::StaticStack()
{
    m_top = -1;
    m_size = 0;
}

template < typename T, int N >
void StaticStack<T,N>::push (const T& e)
{
    if( m_size < N )
    {
        m_space[m_top + 1] = e;     // 异常安全：保证赋值完全正确后，将m_top自增
        ++ m_top;
        ++m_size;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No space in current stack ...");
    }
}

template < typename T, int N >
void StaticStack<T,N>::pop()
{
    if( m_size > 0)
    {
        --m_top;
        --m_size;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current stack ...");
    }
}

template < typename T, int N >
T StaticStack<T,N>::top() const
{
    if( m_size > 0)
    {
        return m_space[m_top];
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current stack ...");
    }
}

template < typename T, int N >
void StaticStack<T,N>::clear()
{
    m_top = -1;
    m_size = 0;
}

template < typename T, int N >
int StaticStack<T,N>::size() const
{
    return m_size;
}

template < typename T, int N >
int StaticStack<T,N>::capacity() const
{
    return N;
}

}

#endif // STATICSTACK_H

5. 小结

• 栈是一种特殊的线性表
• 栈只允许在线性表的一端进行操作
• StaticStack使用原生数组作为内部存储空间
• StaticStack的最大容量由模板参数决定

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4