请问你知道什么是栈吗?

1.1栈的概念及记本操作

栈(stack)又称堆栈,是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶(Top),栈顶保存的元素称为栈顶元素。相对的,表的另一端称为栈底( Bottom)。当栈中没有数据元素时称为空栈;向一个栈插入元素又称为进栈或入栈;从一个栈中删除元素又称为出栈或退栈。

由于栈的插入和删除操作仅在栈顶进行,后进栈的元素必定先出栈,所以又把堆栈称为后进先出表( Last In First Out,LIFO)。图3.1显示了一个堆栈及数据元素插入和删除的过程。

在图3.1中,当ABCD 均已人栈之后,出栈时得到的序列为DCBA,这就是“后进先出”。在解决实际问题时,如果碰到了数据的使用具有“后进先出”的特性,就预示着可以使用堆栈来存储和使用这些数据,堆栈的基本操作除了进栈、出栈操作外,还有判空、取栈顶元素等操作。

1.2顺序栈

由于栈是运算受限的线性表,除了操作不同外,线性表的存储结构对栈也是适用的。利用顺序存储方式实现的栈称为顺序栈。为了便于理解,后面示例中顺序栈操作,均以学号和姓名为数据元素。

1.入职操作思想

根据顺序栈的存储特点,要将某一元素压入栈内,则要进行如下操作:

(1)先判断栈是否已经装满元素,如果未装满才能进行入栈操作,否则不操作。

(2 )栈顶指针先自增,给需要进栈的元素腾出内存空间。

(3 )再将要入栈的元素放入腾出的内存空间里,就是把入栈的元素赋值给对应的数组元素。

【例3.1】 1200101班已有2 名同学王丽、张阳的报到信息存放在栈内,现有(120010131,郑克龙) 同学来报到,请将其信息压人栈中。

首先要定义学生信息类来存放学生记录,具体参数自己定义。

接下来压入对应结点的过程如下:

栈顶指针先自增,给需要进栈的元素腾出内存空间,再往空间里压入元素( 120010131,郑克龙),如图3.3 所示。

2.入栈操作流程图

顺序栈的学生元素存放在data 数组中,length为栈的总长度,top为栈顶指针,则学生元素入栈程序流程图如图3.4 所示。

3.入栈操作代码实现

public class SeqStack { //顺序栈
 //在该例中各元素为学生对象,因此数组定义为student类型
    Student data[];//data为存放学生表各数据元素的数组
    int length;//栈长度
    int top;//栈顶指针
public SeqStack(){
     data=new Student[35];
     length=35;
     top=-1;
   }
public boolean push(Student stu){
     boolean bRst=false;
     if(top>=-1&&top<length-1){ //入栈位置正确与否判断
       top++;
       data[top]=stu;//插入新节点stu
       System.out.println("入栈:"+data[top].no+""+data[top].name);
       bRst=true;
     }
     return bRst;
   }
   public static void main(String[] args) {
     Student stu1=new Student();
     stu1.no="120010103";
     stu1.name="张阳";
     Student stu2=new Student();
     stu2.no="120010102";
     stu2.name="王丽";
     Student stu3=new Student();
     stu3.no="120010131";
     stu3.name="郑克龙";
     SeqStack ss= new SeqStack();
     ss.push(stu1);
     ss.push(stu2);
     ss.push(stu3);
   }
}

4.出栈操作思想

根据顺序栈的存储特点,要取出栈内某一元素,则要进行如下操作:

(1) 先判断栈是否有元素,如果有元素时才能进行出栈操作,否则不操作。

(2 )再将要出栈的元素取出放在内存空间里。

(3 )栈顶指针自减。

【例3.2】1200101班已有3名同学王丽、张阳、郑克龙的报到信息存放在栈内,现需要从栈中取出一位同学的信息进行审查,并显示取出的信息。

首先要定义学生信息类来存放学生记录,具体参见上一章的class Student 定义。

接下来取出对应结点的过程如下:

出栈前如图3.5 所示。

先把需要出栈的元素( 120010131,郑克龙)取出放在内存空间里,再把栈顶指针自减如图3.6 所示。

5.出栈操作流程图

顺序栈的学生元素存放在data数组中,length为栈的总长度,top为栈顶指针,则学生元素出栈流程图如3.7所示。

6.出栈操作代码实现

在入栈的基础上,添加出栈代码,实现如图3.7的流程功能,具体代码实现如下:

public class SeqStack { // 顺序栈
  // 在该例中各元素为学生对象,因此数组定义为student类型
  Student data[];// data为存放学生表各数据元素的数组
  int length;// 栈长度
  int top;// 栈顶指针
  public SeqStack() {
    data = new Student[35];
    length = 35;
    top = -1;
  }
  // 进栈
  public boolean push(Student stu) {
    boolean bRst = false;
    if (top >= -1 && top < length - 1) { // 入栈位置正确与否判断
      top++;
      data[top] = stu;// 插入新节点stu
      System.out.println("入栈:" + data[top].no + "" + data[top].name);
      bRst = true;
    }
    return bRst;
  }
  // 出栈
  public Student pop() {
    Student stu = null;
    if (top >= 0 && top < length) {
      stu = data[top];
      System.out.println("出栈:" + data[top].no + "" + data[top].name);
      top--;
    }
    return stu;
  }
  public static void main(String[] args) {
    Student stu1 = new Student();
    stu1.no = "120010103";
    stu1.name = "张阳";
    Student stu2 = new Student();
    stu2.no = "120010102";
    stu2.name = "王丽";
    Student stu3 = new Student();
    stu3.no = "120010131";
    stu3.name = "郑克龙";
    SeqStack ss = new SeqStack();
    ss.push(stu1);
    ss.push(stu2);
    ss.push(stu3);
    //出栈
    while(ss.top>=0){
      ss.pop();
    }
  }
}

1.3链栈

用链式存储结构实现的栈称为链栈。其结点结构与单链表的结构相同,链式堆栈也是由一个个结点组成的,每个结点由两个域组成,一个是存放数据元素的数据元素域element,另一个是存放指向下一个结点的对象引用(即指针)next

因为栈中的主要运算是在栈顶插入、删除,显然在链表的头部做栈顶是最方便的,而且没有必要像单链表那样为了运算方便附加一个头结点,所以链式堆栈通常不带头结点。

通常将链栈表示成图3.8 的形式。

在学生信息类的基础上,链栈的结点定义如下:

public class Node { // 节点类
  public Student stu; // 节点数据为学生对象
  public Node next;// 后继节点的地址
  public Node() {
    stu = null;
    next = null;
  }
}

链栈的基本操作也是进栈和出栈操作。

1.进栈操作思想

根据链栈的存储特点,要将某一个新节点s压入栈内,则要进行如下操作:

(1) 处理新结点s的后继,这个后继就是原本的栈顶结点。

(2) 将栈顶指针top 重新指向新结点s即可。

【例3.3】1200101班已有两名同学王丽、张阳的报到信息存放在链栈内,现有(120010131,郑克龙) 同学来报到,请将其信息压人链栈中。

首先要定义学生信息类和结点类。

接下来将对应结点压人链栈内的过程如下:

入栈前如图3.9 所示。

生成新节点(120010131,郑克龙),处理新节点的后继,使其后继指向原本的栈顶节点,如图3.10所示。

将栈顶指针top重新指向新节点(120010131,郑克龙)即可,如果3.11所示。

2.进栈操作流程图

链栈中插入的学生元素存放在node中,top为栈顶指针,curlen为栈的长度,则学生元素入栈程序流程图如图3.12所示。

3.进栈操作代码实现

public class LinkStack {// 链栈
  Node top;// 链表头指针
  int curlen;// 实际表长

  public LinkStack() {
    top = null;
    curlen = 0;
  }

  // 在表的第i个位置前插入新数据元素node,返回插入操作结果
  public void push(Node node) {
    node.next = top;
    top = node;
    System.out.println("入栈" + top.stu.no + "" + top.stu.name);
    curlen++;
  }

  public static void main(String[] args) {
    LinkStack ls = new LinkStack();
    Node node1 = new Node();
    node1.stu = new Student();
    node1.stu.no = "120010103";
    node1.stu.name = "张阳";
    Node node2 = new Node();
    node2.stu = new Student();
    node2.stu.no = "120010102";
    node2.stu.name = "王丽";
    Node node3 = new Node();
    node3.stu = new Student();
    node3.stu.no = "120010131";
    node3.stu.name = "郑克龙";
    ls.push(node1);
    ls.push(node2);
    ls.push(node3);
  }

}

4.出栈操作思想

根据链栈的存储特点,要弹出某一个结点,则要进行如下操作:

(1) 在栈顶指针top 非空的情况下,保存弹出结点。

(2) 将栈顶指针top 下移一个元素,即top= top.next。

【例3.4】 1200101班已有3 名同学王丽、张阳、郑克龙的报到信息存放在链栈内,现需要从链栈中取出一位同学的信息进行审查,并显示取出的信息。

首先要定义学生信息类和结点类,具体参见上一章class Student 和class Node的定义。

接下来弹出对应结点的过程如图3.13 所示。

5.出栈操作流程图

链栈中弹出学生元素存放在ni中,top为栈顶指针,curlen为栈的长度,则学生元素出栈程序流程图如3.14所示。

6.出栈操作代码实现

在链表入栈程序的基础上,添加出栈代码,如图。3.14所示的流程功能,具体实现代码如下:

public class LinkStack {// 链栈
  Node top;// 链表头指针
  int curlen;// 实际表长

  public LinkStack() {
    top = null;
    curlen = 0;
  }

  // 在表的第i个位置前插入新数据元素node,返回插入操作结果
  public void push(Node node) {
    node.next = top;
    top = node;
    System.out.println("入栈" + top.stu.no + "" + top.stu.name);
    curlen++;
  }

  // ========出栈===========
  public Node pop() {
    Node ni = null;
    if (top != null) {
      ni = top;
      top = top.next;
      curlen--;
      System.out.println("出栈" + ni.stu.no + "" + ni.stu.name);
    }
    return ni;

  }

  public static void main(String[] args) {
    LinkStack ls = new LinkStack();
    Node node1 = new Node();
    node1.stu = new Student();
    node1.stu.no = "120010103";
    node1.stu.name = "张阳";
    Node node2 = new Node();
    node2.stu = new Student();
    node2.stu.no = "120010102";
    node2.stu.name = "王丽";
    Node node3 = new Node();
    node3.stu = new Student();
    node3.stu.no = "120010131";
    node3.stu.name = "郑克龙";
    ls.push(node1);
    ls.push(node2);
    ls.push(node3);
    // =======出栈==========
    while (ls.top != null) {
      ls.pop();
    }
  }

}

原文发布于微信公众号 - java学习(javaxxf)

原文发表时间:2018-01-31

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣学算法

数据结构 第6讲 链栈

进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储。顺序栈和链栈图解:

931
来自专栏自学笔记

Data Structure_数组_栈_队列_链表_霍夫曼数组栈队列链表哈夫曼

这就表示一个数组,这个数组有八个元素存放。对于元素的获取,主要就是通过下标获取,所以索引对于数组是很重要的,这个索引可以是有意义的,也可以是没有意义的。比如ar...

782
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

1443
来自专栏LeetCode

LeetCode <dp>120&931 Triangle&Minimum Falling Path Sum

Given a triangle, find the minimum path sum from top to bottom. Each step you ma...

1424
来自专栏余林丰

有关LinkedList常用方法的源码解析

jdk1.7.0_79   上文里解析了有关ArrayList中的几个常用方法的源码——《有关ArrayList常用方法的源码解析》,本文将对LinkedLi...

26910
来自专栏XAI

程序员必知的8大排序(java实现)

8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

19910
来自专栏恰同学骚年

数据结构基础温故-2.栈

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,...

813
来自专栏我的技术专栏

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

1923
来自专栏WD学习记录

Leetcode Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

1122
来自专栏赵俊的Java专栏

从源码上分析 LinkedList(附图)

1595

扫码关注云+社区

领取腾讯云代金券