阅读 289

数据结构学习与运用-栈

栈的定义

栈是一种先进后出的数据结构,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何元素的栈称为空栈。

1、栈的操作端通常被称为栈顶,另一端被称为栈底。 2、栈的插入操作称为进栈(压栈|push);栈删除操作称为出栈(弹栈|pop)。

栈的分类

根据栈的存储方式,栈可以分为静态栈(数组实现)和动态栈(链表实现)。

静态栈

对于静态栈,我们一般通过数组来实现的。实现一个栈,里面主要涉及到 2 种状态和 2 种操作。

  1. 2 种状态:栈满和栈空
  2. 2 种操作:出栈和入栈

Java代码实现静态栈

首先我们需要使用到一个数组来存储数据,其次还需要一个变量用于栈的容量大小,还有一个变量来指示栈顶的数据。因此栈的内部数据结构如下所示:

  private T data[];// 用数组表示栈元素
  private int maxSize;// 栈空间大小(常量)
  private int top;// 栈顶指针(指向栈顶元素)
复制代码

对于栈的构造函数,我们可以如下表示:

  public LJStack(int maxSize) {
    this.maxSize = maxSize;
    this.top = -1;
    this.data = (T[]) new Object[maxSize];
  }
复制代码

对于栈空的判断很简单,只需要判断 top 是否等于-1即可:

/**
   * 判断栈是否为空
   * 
   * @return
   */
  public boolean isEmpty() {
    return this.top == (-1) ? true : false;
  }
复制代码

对于栈满的状态判断也很简单,通过 top 的值是否等于栈的容量大小 -1 即:

/**
   * 判断栈是否为满了
   * 
   * @return
   */
  public boolean isFull() {
    return this.top == this.maxSize - 1 ? true : false;
  }
复制代码

两种状态已经实现了,接下来我们来看下两种操作,对于入栈操作,核心就是数组的增加而已:

  /**
   * 压栈操作,将数据存入到栈中
   * 
   * @param value
   */
  public boolean push(T value) {
    if (isFull()) {
      return false;
    } else {
      data[++top] = value;
      return true;
    }
  }
复制代码

对于出栈来说就是将取出数组最后一个值:

 /**
   * 出栈操作
   * @return
   */
  public T pop() {
    if (isEmpty()) {
      return null;
    } else {
      return data[top--];
    }
  }
复制代码

以上便是用数组来实现的静态栈,我们可以进行简单的测试一下:

LJStack<String> stack = new LJStack<String>(10);
System.out.println("是否栈空:" + stack.isEmpty());
stack.push("AAAA");
stack.push("BBBB");
stack.push("CCCC");
stack.push("DDDD");
stack.push("1111");
stack.push("2222");
stack.push("3333");
stack.push("4444");
stack.push("5555");
stack.push("6666");
stack.push("7777");
stack.push("8888");
System.out.println("是否栈满:" + stack.isFull());
复制代码

打印出结果是:

在这里插入图片描述

我们观察结果会发现,打印栈里面的结果发现,竟然没有“7777”,“8888”,那是因为栈满了,所以无法入栈了。因此可以判断,上面我们写的代码是正确的。

链式栈

接着我们来讨论一下链式栈的实现。其实链式栈是通过链表实现栈,我们可以想象有个栈顶节点,当入栈的时候,原先的栈顶节点成为新的节点后继节点,新的节点成为新的栈顶节点。同理,出栈的时候,将栈顶节点弹出,第二个节点成为新的栈顶节点。

Java代码实现链式栈

既然链式栈是通过链表来实现的,首先我们需要构造一个链表的节点LJLinkNode,

public class LJLinkNode <T>{
  private T data;//数据域
  private LJLinkNode<T> next;//指针域
  
  public LJLinkNode() {
    this.data=null;
    this.next=null;
  }
  
  public LJLinkNode(T data) {
    this.data=data;
    this.next=null;
  }
  
  public void setData(T data) {
    this.data=data;
  }
  
  public T getData() {
    return this.data;
  }
  
  public void setNext(LJLinkNode<T> next) {
    this.next=next;
  }
  
  public LJLinkNode<T> getNext(){
    return this.next;
  }
}
复制代码

具体实现如下:

private LJLinkNode<T> topLinkNode;// 栈顶节点
​
  /**
   * 初始化
   */
  public LJLinkStack() {
    this.topLinkNode = new LJLinkNode<T>();
  }
​
  /**
   * 初始化
   */
  public void initLinkStack() {
    this.topLinkNode.setData(null);
    this.topLinkNode.setNext(null);
  }
复制代码

判断栈空状态:

/**
   * 判断是否栈空
   * 
   * @return
   */
  public boolean isEmpty() {
    return this.topLinkNode.getNext() == null;
  }
复制代码

压栈操作:

/**
   * 压栈 
   * 当入栈的时候,原先的栈顶节点成为新的节点后继节点,新的节点成为新的栈顶节点。
   * 
   * @param node
   */
  public void push(LJLinkNode<T> node) {
    if (isEmpty()) {
      this.topLinkNode.setNext(node);
    } else {
      node.setNext(this.topLinkNode.getNext());
      this.topLinkNode.setNext(node);
    }
  }
复制代码

出栈操作:

/**
   * 出栈 
   * 出栈的时候,将栈顶节点弹出,第二个节点成为新的栈顶节点。
   * @return
   */
  public LJLinkNode<T> pop() {
    if (isEmpty()) {
      // 栈空无法弹栈
      return null;
    } else {
      LJLinkNode<T> delNode = this.topLinkNode.getNext();// 取出删除节点
      this.topLinkNode.setNext(this.topLinkNode.getNext().getNext());// 删除节点
      return delNode;
    }
  }
复制代码

我们来测试一下写的代码:

    LJLinkStack<String> linkStack = new LJLinkStack<String>();
    System.out.println("栈是否为空:" + linkStack.isEmpty());
    linkStack.push(new LJLinkNode<String>("AAAAA"));
    linkStack.push(new LJLinkNode<String>("BBBBB"));
    linkStack.push(new LJLinkNode<String>("CCCCC"));
​
    // 依次弹栈
    System.out.println("弹栈顺序:");
    System.out.println(linkStack.pop().getData());
    System.out.println(linkStack.pop().getData());
    System.out.println(linkStack.pop().getData());
复制代码

打印结果如下:

在这里插入图片描述

以上便是栈的静态及动态实现方式。那么这两种方式有什么具体运用呢?接着我们来通过具体的面试题目来运用栈。

算法运用

题目:匹配有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。


有效字符串需满足:


左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。


示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true
复制代码

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/va…

在这里插入图片描述

在这里插入图片描述

关注下面的标签,发现更多相似文章
评论