前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法—栈详解(看完面试考试再也不怕了)

数据结构与算法—栈详解(看完面试考试再也不怕了)

作者头像
bigsai
发布2019-09-24 11:59:23
5040
发布2019-09-24 11:59:23
举报
文章被收录于专栏:bigsai

什么是栈

百度百科上,栈是这么定义的:

  • 栈(stack)又名堆栈,它是一种运算受限线性表。限定仅在表尾进行插入删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

稍微介绍一下关键名词:

  • 运算受限:也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端就行插入和删除。同样,队列也是运算受限,只能在两天操作。
  • 线性表:栈也是一种线性表,前面详细介绍过线性表,它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分数组和链表实现,他们的物理存储结构不同。但是逻辑结构(实现的目的)相同。
  • 栈顶栈底: 这个描述是偏向于逻辑上的内容,因为大家知道数组在末尾插入删除更容易,而单链表通常在头插入删除更容易。所以数组可以用末尾做栈顶,而链表可以头做栈顶。

栈的应用:

  • 栈的应用广泛,比如你的程序执行查看调用堆栈、加减运算、甚至在搜索算法中dfs,替代递归等等。所以栈也是必须掌握的一门数据结构。很多规范也是栈,比如上图放书拿书一样!

设计与介绍

这里我们介绍数组实现的栈和链表实现的栈。

数组实现

结构设计

  • 对于数组来说,我们模拟栈的过程很简单,因为栈是后进先出,我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。所以对于一个栈所需要的基础元素是 一个data数组和一个top(int)表示栈顶位置。
  • 那么初始化以及构造的函数代码为:
代码语言:javascript
复制
private T data[];
private int top;
public seqStack() {
  data=(T[]) new Object[10];
  top=-1;
}
public seqStack(int maxsize)
{
  data=(T[]) new Object[maxsize];
  top=-1;
}

push插入

栈的核心操作之一push:入栈操作。

  • 如果top<数组长度-1。入栈。top++;a[top]=value;
  • 如果top==数组长度-1;栈满。

pop弹出并返回首位

  • 如果top>=0,栈不为空,可以弹出。return data[top--];
  • 如下图,本来栈为1,2,3,4(栈顶),执行pop操作。top变为3的位置并且返回4;

其他操作

  • 其他例如peek操作时返回栈顶不弹出.所以只需满足题意时候return data[top]即可。

链表实现

有数组实现,链表当然也能实现。对于栈的运算。大致可以分为两种思路:

  • 像数组那样在尾部插入删除。大家都知道链表效率低在查询。而查询到尾部效率很低。而我们就算用了尾指针,可以解决尾部插入效率。但是依然无法解决删除效率(删除需要找到前节点).还需要双向链表。前面虽然详细介绍过双向链表,但是这样未免太复杂!
  • 所以我们采用带头节点的单链表在头部插入删除,把头部当中栈顶,这样精了很多。插入直接在头节点后插入。而删除也直接删除头节点后第一个元素即可。

结构设计

长话短说,短话不说。直接上代码就懂。 链表的节点:

代码语言:javascript
复制
static class node<T>
{
  T data;
  node next;
  public node() {    
  }
  public node(T value)
{
    this.data=value;
  }
}

基本结构:

代码语言:javascript
复制
public class lisStack <T>{
  int length;
    node<T> head;//头节点
    public lisStack() {
    head=new node<>();
    length=0;
  }
  //其他方法
}

push插入

与单链表头插入一致,如果不太了解请先看笔者队线性表介绍的。

和数组形成的栈有个区别。就是理论上栈没有大小限制(不突破内存系统限制)。不需要考虑是否越界。

  • 节点team入栈
  • 空链表入栈head.next=team;
  • 非空入栈team.next=head.next;head.next=team;

pop弹出

与单链表头删除一致,如果不太了解请先看笔者队线性表介绍的。

和数组同样需要判断是否为空。

  • 节点team出栈
  • head指向team后驱节点。不需要考虑链表是否为1个节点。如果为1个节点,team.next=null.执行完毕head.next=null。变为空,满足条件。

其他操作

  • 其他例如peek操作时返回栈顶不弹出.所以只需判空满足题意时候return head.next.data即可。而length你可以遍历链表返回长度,也可以动态设置(本文采取)跟随栈长变化。其他操作直接看api。

实现代码

数组实现

代码语言:javascript
复制
package 队栈;

public class seqStack<T> {
  
  private T data[];
  private int top;
  public seqStack() {
    data=(T[]) new Object[10];
    top=-1;
  }
  public seqStack(int maxsize)
{
    data=(T[]) new Object[maxsize];
    top=-1;
  }
  boolean isEmpty()
{
    return top==-1;
  }
  int length()
{
    return top+1;
  }
  
  boolean push(T value) throws Exception//压入栈
{
    if(top+1>data.length-1)
    {
      throw new Exception("栈已满");
    }
    else {
      data[++top]=value;
      return true;
    }
  }
  T peek() throws Exception//返回栈顶元素不移除
{
    if(!isEmpty())
    {
      return data[top];
    }
    else {
      throw new Exception("栈为空");
    }
  }
  T pop() throws Exception
{
    if(isEmpty())
    {
      throw new Exception("栈为空");
    }
    else {
       return data[top--];
    }
  }
  public String toString()
{
    if(top==-1)
    {
      return "";
    }
    else {
      String va="";
      for(int i=top;i>=0;i--)
      {
        va+=data[i]+"  ";
      }
      return va;
    }
  }
}

链表实现

代码语言:javascript
复制
package 队栈;

public class lisStack <T>{
  static class node<T>
{
    T data;
    node next;
    public node() {    
    }
    public node(T value)
{
      this.data=value;
    }
  }
  int length;
    node<T> head;//头节点
    public lisStack() {
    head=new node<>();
    length=0;
  }
    boolean isEmpty()
{
    return head.next==null;
  }
  int length()
{
    return length;
  }
    public void push(T value) {//近栈
       node<T> team=new node<T>(value);
       if(length==0)
       {
         head.next=team;
       }
       else {
    team.next=head.next;
    head.next=team;}
       length++;
    }
    public T peek() throws Exception {
        if(length==0) {throw new Exception("链表为空");}
        else {//删除
      return (T) head.next.data;
    }
  }
    public T pop() throws Exception {//出栈
          if(length==0) {throw new Exception("链表为空");}
          else {//删除
          T value=(T) head.next.data;
      head.next=head.next.next;//va.next
      length--;
      return value;
      
      
    }
    }
    public String toString(){
      if(length==0) {return "";}
      else {
      String va="";
        node team=head.next;
        while(team!=null)
        {
          va+=team.data+" ";
          team=team.next;
        }
        return va;
    }
       
    }
}

测试

总结

  • 栈的逻辑比较简单。很容易理解,实现起来也相对容易。但是要注意数组情况的界限问题。
  • 后面将介绍队列,相比栈,队列内容更丰富一些。难度也稍大一些。
  • 如果有不好需要改进还请指出
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 bigsai 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 设计与介绍
    • 数组实现
      • 结构设计
      • push插入
      • pop弹出并返回首位
      • 其他操作
    • 链表实现
      • 结构设计
      • push插入
      • pop弹出
      • 其他操作
      • 数组实现
      • 链表实现
      • 测试
  • 实现代码
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档