美图

一、前言

计算机程序离不开算法和数据结构,数据结构这门学科就是为了让计算机能够以更加高效,简单,便捷的方式来存储和使用数据而产生的。本文简单介绍栈 (Stack) 和队列 (Queue) 的实现

二、图解

图解

三、线性表

1、 顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素 2、 链式存储结构:用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续,空间与内存没有线性关系

四、栈

1、只允许在一端进行插入和删除操作的线性表

2、 实现的功能

  • push:在最顶层加入数据。
  • pop:返回并移除最顶层的数据。
  • peek:返回最顶层数据的值,但不移除它。
  • empty:返回一个布尔值,表示当前 stack 是否为空栈。

2-1、初始化

private int[] arr;
    // 常量用大写
    private final static int SIZE = 1;
    // 栈的当前指针
    private int index;
<span class="hljs-comment">//构造器没有参数的</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">StackDemo</span><span class="hljs-params">()</span> </span>{
    arr = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[SIZE];
    index = -<span class="hljs-number">1</span>;
}
复制代码

2-2、push

// 入栈
private void push(int target){
    if (index == SIZE){
        throw  new  StackOverflowError();
    }else {
        // 刚开始为 -1,要前加
        arr[++index] = target;
    }
}
复制代码

2-3、peek

// 返回栈顶元素
private int peek(){
    if (index == -1){
        throw new StackOverflowError();
    }else {
        return arr[index];
    }
}
复制代码

2-4、empty

    // 判空
    private boolean empty(){
        if (index == -1){
            return true;
        }
        return false;
    }
复制代码

3、代码实现

import java.util.Arrays;

/**
*
* @author buer
* @date 2019/1/20
*/

public class StackDemo {
private int[] arr;
// 常量用大写
private final static int SIZE = 1;
// 栈的当前指针
private int index;

<span class="hljs-comment">//构造器没有参数的</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">StackDemo</span><span class="hljs-params">()</span> </span>{
    arr = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[SIZE];
    index = -<span class="hljs-number">1</span>;
}

<span class="hljs-comment">//入栈</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">push</span><span class="hljs-params">(<span class="hljs-keyword">int</span> target)</span></span>{
    <span class="hljs-keyword">if</span> (index == SIZE){
        <span class="hljs-keyword">throw</span>  <span class="hljs-keyword">new</span>  StackOverflowError();
    }<span class="hljs-keyword">else</span> {
        <span class="hljs-comment">//刚开始为-1,要前加</span>
        arr[++index] = target;
    }
}

<span class="hljs-comment">//出栈</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">pop</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">if</span> (index == -<span class="hljs-number">1</span>){
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> StackOverflowError();
    }<span class="hljs-keyword">else</span> {
        <span class="hljs-keyword">return</span> arr[index--];
    }
}

<span class="hljs-comment">//返回栈顶元素</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">peek</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">if</span> (index == -<span class="hljs-number">1</span>){
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> StackOverflowError();
    }<span class="hljs-keyword">else</span> {
        <span class="hljs-keyword">return</span> arr[index];
    }
}

<span class="hljs-comment">//判空</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">empty</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">if</span> (index == -<span class="hljs-number">1</span>){
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
    StackDemo stackDemo = <span class="hljs-keyword">new</span> StackDemo();
    stackDemo.push(<span class="hljs-number">1</span>);
    System.out.println(stackDemo.toString());
    stackDemo.pop();
    System.out.println(stackDemo.toString());

}

<span class="hljs-meta">@Override</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>{
    <span class="hljs-keyword">return</span> <span class="hljs-string">"StackDemo{"</span> +
            <span class="hljs-string">"arr="</span> + Arrays.toString(arr) +
            <span class="hljs-string">", index="</span> + index +
            <span class="hljs-string">'}'</span>;
}

}

复制代码

应用

1、括号匹配

2、中缀表达式(人类的思考)和后缀表达式(计算机的计算)

3、递归

4、浏览器的前进后退功能

参考资料

zh.wikipedia.org www.zhihu.com/question/21… www.ruanyifeng.com/blog/2013/1…

  • Java

    Java,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台的总称。用 Java 实现的 HotJava 浏览器(支持 Java applet)显示了 Java 的魅力:跨平台、动态的…

    380 引用 • 6 回帖
感谢    赞同    分享    收藏    关注    反对    举报    ...