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

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

数据结构系列文章

数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

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

数据结构图文解析之:队列详解与C++模板实现

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

数据结构图文解析之:AVL树详解及C++模板实现

数据结构图文解析之:二叉堆详解及C++模板实现

数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

1. 栈的简介

1.1栈的特点

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

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

1.2栈的相关概念

栈的相关概念:

  1. 栈顶与栈底:允许元素插入与删除的一端称为栈顶,另一端称为栈底。
  2. 压栈:栈的插入操作,叫做进栈,也称压栈、入栈。
  3. 弹栈:栈的删除操作,也叫做出栈。

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

在压栈的过程中,栈顶的位置一直在”向上“移动,而栈底是固定不变的。 如果我们要把栈中的元素弹出来:

出栈的顺序为3、2、1 ,顺序与入栈时相反,这就是所谓的”先入后出“。 在弹栈的过程中,栈顶位置一直在”向下“移动,而栈底一直保持不变。

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

1.3 栈的操作

栈的常用操作为:

  1. 弹栈,通常命名为pop
  2. 压栈,通常命名为push
  3. 求栈的大小
  4. 判断栈是否为空
  5. 获取栈顶元素的值

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;            //底层为数组
};
  1. count 为栈的元素数量,capacity为栈的容量,count<=capacity,当栈满的时候,count = capacity。
  2. 本实现中不支持栈的动态扩容,栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定,默认的栈容量为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;
};
  1. value:栈中元素的值
  2. 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;
}

测试结果:

栈的大小:3
栈顶元素:you!
栈的大小:0

4. 栈的完整代码

基于数组的栈: https://github.com/huanzheWu/Data-Structure/blob/master/Stack/Main/Main/ArrayStack.h 基于单链表的栈:https://github.com/huanzheWu/Data-Structure/blob/master/singleList/singleList/singleList.h

原创文章,转载请注明出处:http://www.cnblogs.com/QG-whz/p/5170418.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

UESTC 485 Game(康托,BFS)

Today I want to introduce an interesting game to you. Like eight puzzle, it is a...

2717
来自专栏ml

C++ 高级语法学习与总结(代码实例)

    C++11增加了许多的特性,auto就是一个很明显的例子。  还有就是typedid()获取数据变量的类型     看下面简短的代码:         ...

3446
来自专栏JavaEdge

"聊胜于无",浅析Java中的原子操作Java的指针Unsafe类i++不是线程安全的1 原子更新基本类型类2 原子更新数组3 AtomicReference(原子更新引用)4 原子更新字段Atomi

5076
来自专栏老马说编程

(70) 原子变量和CAS / 计算机程序的思维逻辑

从本节开始,我们探讨Java并发工具包java.util.concurrent中的内容,本节先介绍最基本的原子变量及其背后的原理和思维。 原子变量 什么是原子...

1789
来自专栏Hellovass 的博客

设计一个有 getMin 功能的栈

这个类的设计上,采用两个栈,一个用来保存当前栈中的元素,其功能等同于一个正常的栈,记为 mStack;另一个栈用来保存每一步的最小值,记为 mMinStack.

692
来自专栏Hellovass 的博客

由两个栈组成的队列

栈的特点是先进后出,队列的特点是先进先出,使用两个栈正好能把顺序反过来实现类似队列的操作。

892
来自专栏专注 Java 基础分享

详解Java动态代理机制(二)----cglib实现动态代理

     上篇文章的结尾我们介绍了普通的jdk实现动态代理的主要不足在于:它只能代理实现了接口的类,如果一个类没有继承于任何的接口,那么就不能代理该类,原因是我...

24810
来自专栏开发与安全

从零开始学C++之数据封装与抽象:分别用C和C++来实现一个链栈

下面通过分别用C和C++来实现一个链栈(链表实现),从中体会数据封装抽象的思想: C语言实现: #include <stdio.h> #include <std...

2000
来自专栏Java技术栈

你知道void和Void的区别吗?

区别 void 用于无返回值的方法定义。 Void Void是void的包装方法,和其他基础类型的包装方法不同是Void不能被实例化,Void还可用于一直返回n...

34311
来自专栏haifeiWu与他朋友们的专栏

死磕Java之聊聊LinkedList源码(基于JDK1.8)

我们主要看研究一下下面的几个方法,LinkedList其他方法都是通过调用这几个方法来实现功能,包括LinkedList的双端队列的方法也是。

994

扫码关注云+社区