数据结构图文解析之:栈的简介

  • 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. 基于数组的栈实现

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


3. 基于单链表的栈

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

tags: Python