文档章节

java实现栈结构

蜀山下的鱼
 蜀山下的鱼
发布于 2015/04/29 00:39
字数 1033
阅读 5
收藏 0

栈的定义  

      栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。  

    (1)通常称插入、删除的这一端为栈顶 (Top),另一端称为栈底 (Bottom)。  

    (2)当表中没有元素时称为空栈。  

    (3)栈为后进先出(Last In First Out)的线性表,简称为 LIFO 表。  

      栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中

最新"的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部, 

要到最后才能删除。 

 

【示例】元素是以a1a2,…,an的顺序进栈,退栈的次序却是anan-1,…, 

a1。  

 

2、栈的基本运算  

 (1InitStackS)  

      构造一个空栈S。  

 (2StackEmptyS)  

      判栈空。若S为空栈,则返回TRUE,否则返回FALSE。  

 (3StackFullS)  

      判栈满。若S为满栈,则返回TRUE,否则返回FALSE。  

注意: 该运算只适用于栈的顺序存储结构。  

 (4PushSx)  

      进栈。若栈S不满,则将元素x插入S的栈顶。  

 (5PopS)  

 

 

定义堆栈ADT
StackADT
package Stack;
public interface StackADT {
    public void push(Object element);//压栈
    public Object pop();//出栈
    public boolean isEmpty();
    public int size();
    public Object peek();//返回栈顶对象的一个引用
    public String toString();
}

 

链式实现:


在栈的一段添加和删除元素,在栈中维护一个指向栈顶的结点和一个count变量指示栈的大小:
private LinearNode top; //指向栈顶
private int count;//标记栈的大小
每次出栈和压栈在链表的表头:(也可以再表尾,实现方式不一样而已)
top--->元素1--->元素2--->元素3.........
实现(附带测试main):
LinkedStack
package Stack;
import Bag.LinearNode;
//为了重点来实现算法,将异常情况直接打印出然后退出程序,不再声明异常类
public class LinkedStack implements StackADT {
    private LinearNode top; //指向栈顶
    private int count;//标记栈的大小
    public static void main(String[] args){
        LinkedStack stack = new LinkedStack();
        System.out.println("010依次压栈");
        for(int i = 0;i < 10;i++)
            stack.push(i);
        System.out.println("连续执行5次出栈操作");
        for(int i = 0;i < 5;i++)
            stack.pop();
        System.out.println("栈为空吗?: " + stack.isEmpty());
        System.out.println("栈的大小为: " + stack.size());
        System.out.println("栈顶元素为: " + stack.top.getElement());
        System.out.println("栈顶元素为: " + stack.peek());   
    }
    public LinkedStack()
    {
        top = null;
        count = 0;
    }
    public int size() {
        return count;
    }
    public boolean isEmpty() {
        return (size() == 0);
    }
    public void push(Object element) {
        LinearNode node = new LinearNode(element);
        node.setNext(top);
        top = node;
        count++;
    }
    public Object pop() {
        if(isEmpty())
        {
            System.out.println("stack is empty!");
            System.exit(1);
        }
        Object result = top.getElement();
        top = top.getNext();
        count--;
        return result;
    }
    public Object peek() {
        Object result =  top.getElement();
        return result;
    }
}
运行结果:
010依次压栈
连续执行5次出栈操作
栈为空吗?: false
栈的大小为: 5
栈顶元素为: 4
栈顶元素为: 4


数组实现:


栈底总是数组下标为0的位置,入栈出栈从数组下标的最后一个元素开始:
private Object[] contents;
private int top;//top标记下一个入栈的位置,同时也表示栈的容量大小,跟链式实现的count比较一下!!!
实现(附带测试main):
ArrayStack
package Stack;
public class ArrayStack implements StackADT {
    private Object[] contents;
    private int top;//top标记下一个入栈的位置,同时也表示栈的容量大小,跟链式实现的count比较一下!!!
    private static int SIZE = 10;
    public ArrayStack()
    {
        contents = new Object[SIZE];
        top = 0;
    }
    public void expand(){//借助于申请一个辅助空间,每次扩展容量一倍
        Object[] larger = new Object[size()*2];
        for(int index = 0;index < top;index++)
            larger[index] =  contents[index];
        contents = larger;
    }
    public int size() {
        return top;
    }
    public boolean isEmpty() {
        return (size() == 0);
    }
    public void push(Object element) {
        //if(isEmpty())
            //expand();
        if(top == contents.length)
            expand();
        contents[top] = element;
        top++;
    }
    public Object pop() {
        if(isEmpty())
        {
            System.out.println("stack is empty!");
            System.exit(1);
        }
        Object result = contents[top-1];
        contents[top-1] = null;//出栈
        top--;
        return result;   
        /*书上这样写简便一点:::
         * top--;
         * Object result = contents[top];
         * contents[top] = null;*/       
    }
    public Object peek() {
        Object result;
        if(isEmpty())
            result = null;
        else
            result = contents[top-1];
        return result;
    }
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack();
        System.out.println("024依次压栈,然后连续10次出栈");
        for(int i = 0;i < 25;i++)
            stack.push(i);
        for(int i = 0;i < 10;i++)
            stack.pop();
        System.out.println("栈的大小为: " + stack.size());
        System.out.println("栈为空吗?: " + stack.isEmpty());
        System.out.println("栈顶元素为: " + stack.peek());
    }
}
运行结果:
024依次压栈,然后连续10次出栈
栈的大小为: 15
栈为空吗?: false
栈顶元素为: 14 

 

 

 

 

本文转载自:http://blog.csdn.net/caiwenfeng_for_23/article/details/8496157

蜀山下的鱼
粉丝 9
博文 405
码字总数 0
作品 0
广州
高级程序员
私信 提问
JVM系列(二)—JVM内存结构

所有的Java开发人员可能会遇到这样的困惑?我该为堆内存设置多大空间呢?OutOfMemoryError的异常到底涉及到运行时数据的哪块区域?该怎么解决呢?其实如果你经常解决服务器性能问题,那么这些...

haoyuehong
2018/12/29
50
0
JVM 虚拟机(对象创建,类加载器,执行引擎等),

1.揭开 Java 对象创建的奥秘? 2.class 文件结构详解? 3.详解 Java 类的加载过程? > Java 对象创建,class 文件结构 Java对象模型 。Java对象保存在堆内存中。在内存中,一个Java对象包含三...

desaco
2018/08/29
0
0
云计算高级培训,Tomcat运维JVM 虚拟机常识

云计算高级培训,Tomcat运维JVM 虚拟机常识,作为了解JVM 虚拟机的开始。我们很有必要弄明白以下问题。 所谓虚拟机,就是一台虚拟的计算机。他是一款软件,用来执行一系列虚拟计算机指令。大...

长沙千锋
2018/05/17
0
0
Java代码编译和执行的整个过程

Java代码编译是由Java源码编译器来完成,流程图如下所示: Java字节码的执行是由JVM执行引擎来完成,流程图如下所示: Java代码编译和执行的整个过程包含了以下三个重要的机制: Java源码编译...

xiejunbo
2016/02/11
1K
1
Java虚拟机运行时数据区结构

本文部分参考自《Java虚拟机规范(Java SE 7版)》的中译本和周志明的《深入理解Java虚拟机》,另加个人理解。原书对Java虚拟机运行时数据区描述只有6页,同时参考其他网络网资料,个人能力所...

foodon
2014/12/09
351
4

没有更多内容

加载失败,请刷新页面

加载更多

Giraph源码分析(八)—— 统计每个SuperStep中参与计算的顶点数目

作者|白松 目的:科研中,需要分析在每次迭代过程中参与计算的顶点数目,来进一步优化系统。比如,在SSSP的compute()方法最后一行,都会把当前顶点voteToHalt,即变为InActive状态。所以每次...

数澜科技
今天
4
0
Xss过滤器(Java)

问题 最近旧的系统,遇到Xss安全问题。这个系统采用用的是spring mvc的maven工程。 解决 maven依赖配置 <properties><easapi.version>2.2.0.0</easapi.version></properties><dependenci......

亚林瓜子
今天
10
0
Navicat 快捷键

操作 结果 ctrl+q 打开查询窗口 ctrl+/ 注释sql语句 ctrl+shift +/ 解除注释 ctrl+r 运行查询窗口的sql语句 ctrl+shift+r 只运行选中的sql语句 F6 打开一个mysql命令行窗口 ctrl+l 删除一行 ...

低至一折起
今天
9
0
Set 和 Map

Set 1:基本概念 类数组对象, 内部元素唯一 let set = new Set([1, 2, 3, 2, 1]); console.log(set); // Set(3){ 1, 2, 3 } [...set]; // [1, 2, 3] 接收数组或迭代器对象 ...

凌兮洛
今天
4
0
PyTorch入门笔记一

张量 引入pytorch,生成一个随机的5x3张量 >>> from __future__ import print_function>>> import torch>>> x = torch.rand(5, 3)>>> print(x)tensor([[0.5555, 0.7301, 0.5655],......

仪山湖
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部