数据结构图文解析之：栈的简介及C++模板实现

2022-09-25 16:07:11

0. 数据结构图文解析系列

数据结构系列文章
数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现
数据结构图文解析之：栈的简介及C++模板实现
数据结构图文解析之：队列详解与C++模板实现
数据结构图文解析之：树的简介及二叉排序树C++模板实现.
数据结构图文解析之：AVL树详解及C++模板实现
数据结构图文解析之：二叉堆详解及C++模板实现
数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现

1. 栈的简介

1.1栈的特点

栈(Stack)是一种线性存储结构，它具有如下特点：

栈中的数据元素遵守”先进后出"(First In Last Out)的原则，简称FILO结构。
限定只能在栈顶进行插入和删除操作。

1.2栈的相关概念

栈的相关概念：

栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
压栈：栈的插入操作，叫做进栈，也称压栈、入栈。
弹栈：栈的删除操作，也叫做出栈。

例如我们有一个存储整型元素的栈，我们依次压栈：{1,2,3}

在压栈的过程中，栈顶的位置一直在”向上“移动，而栈底是固定不变的。

如果我们要把栈中的元素弹出来：

出栈的顺序为3、2、1 ，顺序与入栈时相反，这就是所谓的”先入后出“。

在弹栈的过程中，栈顶位置一直在”向下“移动，而栈底一直保持不变。

如果你玩过一种称为汉诺塔的益智玩具，你就会知道游戏中小圆盘的存取就是一种先进后出的顺序，一个圆柱就是一个栈：

1.3 栈的操作

栈的常用操作为：

弹栈，通常命名为pop
压栈，通常命名为push
求栈的大小
判断栈是否为空
获取栈顶元素的值

1.4 栈的存储结构

栈既然是一种线性结构，就能够以数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。

本文我们以数组、单向链表为底层数据结构构建栈。

2. 基于数组的栈实现

当以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向：

2.1 栈的抽象数据类型

栈提供了如上所述操作的相应接口。

template<typename T>

class ArrayStack

{

public:

    ArrayStack(int s = 10);    //默认的栈容量为10

    ~ArrayStack();

public:

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

    void push(T t);        //压栈操作

    T pop();            //弹栈操作

    bool isEmpty();        //判空操作

    int size();            //求栈的大小

private:

    int count;            //栈的元素数量

    int capacity;        //栈的容量

    T * array;            //底层为数组

};

count 为栈的元素数量，capacity为栈的容量，count<=capacity，当栈满的时候，count = capacity。
本实现中不支持栈的动态扩容，栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定，默认的栈容量为10。

2.2 栈的具体实现

栈的实现还是相对简单的，很容易理解。这里就不再画蛇添足了。

 /*栈的判空操作*/

template <typename T>

bool ArrayStack<T>::isEmpty()

{

     return count == 0; //栈元素为0时为栈空

};

/*返回栈的大小*/

 template <typename  T>

int ArrayStack<T>::size()

{

     return count;

};

/*插入元素*/

template <typename T>

void ArrayStack<T>::push(T t)

{

     if (count != capacity)    //先判断是否栈满

     {

         array[count++] = t;

     }

};

/*弹栈*/

template <typename T>

T ArrayStack<T>::pop()

{

     if (count != 0)    //先判断是否是空栈

     {

         return array[--count];

     }

};

/*获取栈顶元素*/

template <typename T>

T ArrayStack<T>::top()

{

     if (count != 0)

     {

         return array[count - 1];

     }

};

2.3 栈的代码测试

int _tmain(int argc, _TCHAR* argv[])

{

    ArrayStack <int> p(5);

    for (int i = 0; i < 5; i++)

    {

        p.push(i);

    }

    cout << "栈的大小:"<<p.size() << endl;

    cout << "栈是否为空:"<<p.isEmpty() << endl;

    cout << "栈顶元素："<<p.top() << endl;

    cout << "依次出栈:" << endl;

    while (!p.isEmpty())

    {

        cout << p.pop() << endl;

    }

    getchar();

    return 0;

}

测试结果：

栈的大小:5

栈是否为空:0

栈顶元素：4

依次出栈:

4

3

2

1

0

3. 基于单链表的栈

以链表为底层的数据结构时，以链表头为作为栈顶较为合适，这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部；

3.1 链表节点

/*链表节点结构*/

template <typename T>

struct Node

{

    Node(T t) :value(t), next(nullptr){};

    Node() :next(nullptr){};

public:

    T value;

    Node<T>* next;

};

value:栈中元素的值
next:链表节点指针，指向直接后继

3.2 栈的抽象数据类型

基于链表的栈提供的接口与基于数组的栈一致。



/*栈的抽象数据结构*/

template <typename T>

class LinkStack

{

public:

     LinkStack();

     ~LinkStack();

public:

     bool isEmpty();

     int size();

     void push(T t);

     T pop();

     T top();

private:

     Node<T>* phead;

     int count;

};

3.3 栈的具体实现

/*返回栈的大小*/

template <typename T>

int LinkStack<T>::size()

{

     return count;

};

/*栈的判空操作*/

template <typename T>

bool LinkStack<T>::isEmpty()

{

     return count == 0;

};

/*插入元素*/

template<typename T>

void LinkStack<T>::push(T t)

{

     Node <T> *pnode = new  Node<T>(t);

     pnode->next = phead->next;

     phead->next = pnode;

     count++;

};

/*弹栈*/

template <typename T>

T LinkStack<T>::pop()

{

     if (phead->next != nullptr) //栈空判断

     {

         Node<T>* pdel = phead->next;

         phead->next = phead->next->next;

         T value = pdel->value;

         delete pdel;

         count--;

         return value;

     }

};

/*获取栈顶元素*/

template <typename T>

T LinkStack<T>::top()

{

    if (phead->next!=nullptr)

        return phead->next->value;

};

3.4 栈的代码测试

int _tmain(int argc, _TCHAR* argv[])

{

    LinkStack <string> lstack;

    lstack.push("hello");

    lstack.push("to");

    lstack.push("you！");

    cout << "栈的大小:" << lstack.size() << endl;

    cout <<"栈顶元素:"<< lstack.top() << endl;

    while (!lstack.isEmpty())

    {

        lstack.pop();

    }

    cout << "栈的大小:" << lstack.size() << endl;

    getchar();

    return 0;

}