[数据结构] 栈-阿里云开发者社区

开发者社区> ghost丶桃子> 正文

[数据结构] 栈

简介:
+关注继续查看

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

栈的示意图:

这里写图片描述

java中的Stack

  Stack 类表示后进先出(LIFO)的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ,允许将向量视为堆栈。它提供了通常的 push 和 pop 操作,以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。首次创建堆栈时,它不包含项。

Deque 接口及其实现提供了 LIFO 堆栈操作的更完整和更一致的 set,应该优先使用此 set,而非此类。例如:


Deque<Integer> stack = new ArrayDeque<Integer>(); 
 

成员方法:

E push(E item) 
把项压入堆栈顶部。  

E pop() 
移除堆栈顶部的对象,并作为此函数的值返回该对象。  

E peek() 
查看堆栈顶部的对象,但不从堆栈中移除它。  

boolean empty() 
测试堆栈是否为空。  

int search(Object o) 
返回对象在堆栈中的位置,以 1 为基数。 

Stack继承于Vector,Vector本身是一个可增长的对象数组。 
Stack并不要求其中保存数据的唯一性,当Stack中有多个相同的item时,调用search方法,只返回与查找对象equal并且离栈顶最近的item与栈顶间距离。

empty()

  判断stack是否为空,就需要有一个变量来计算当前栈的长度,如果该变量为0,则表示该栈为空。

源码:

public boolean empty() {
    return size() == 0;
}

size()方法在父类Vector中实现了,在Vector里面有一个变量elementCount来表示容器里元素的个数。如果为0,则表示容器空。


public synchronized int size() {  
    return elementCount;  
}  


peek()

  返回栈顶端的元素,如果栈为空的话,则要抛出异常。


public synchronized E peek() {  
    int     len = size();  

    if (len == 0)  
        throw new EmptyStackException();  
    return elementAt(len - 1);  
}  

elementAt方法也是在Vector里面实现的,实际上是用一个elementData的Object数组来存储元素的。

public synchronized E elementAt(int index) {  
    if (index >= elementCount) {  
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
    }  

    return elementData(index);  
}  

@SuppressWarnings("unchecked")  
E elementData(int index) {  
    return (E) elementData[index];  
} 

peek()

  将栈顶的元素弹出来,如果栈里有元素,就取最顶端的那个,否则就要抛出异常。

public synchronized E pop() {  
     E   obj;  
     int  len = size();  

     obj = peek();  
     removeElementAt(len - 1);  

     return obj;  
} 

  通过peek()取到顶端的元素之后,我们需要用removeElementAt()方法将最顶端的元素移除。 
removeElementAt()方法定义在vector中。

public synchronized void removeElementAt(int index) {  
    modCount++;  
    if (index >= elementCount) {  
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
        }  
    else if (index < 0) {  
        throw new ArrayIndexOutOfBoundsException(index);  
    }  
    int j = elementCount - index - 1;  
    if (j > 0) {  
        System.arraycopy(elementData, index + 1, elementData, index, j);  
    }  
    elementCount--;  
    elementData[elementCount] = null; /* to let gc do its work */  
}  

  这里用待删除元素的后面元素依次覆盖前面一个元素。这样,就相当于将数组的实际元素长度给缩短了。

push()

  将数据入栈

public E push(E item) {  
    addElement(item);  

    return item;  
}

  将要入栈的元素放到数组的末尾,再将数组长度加1就可以了。addElement()方法也在vector中(好父亲啊)。

public synchronized void addElement(E obj) {  
    modCount++;  
    ensureCapacityHelper(elementCount + 1);  
    elementData[elementCount++] = obj;  
}  

private void ensureCapacityHelper(int minCapacity) {  
    // overflow-conscious code  
    if (minCapacity - elementData.length > 0)  
        grow(minCapacity);  
}  

private void grow(int minCapacity) {  
    // overflow-conscious code  
    int oldCapacity = elementData.length;  
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?  
                                    capacityIncrement : oldCapacity);  
    if (newCapacity - minCapacity < 0)  
        newCapacity = minCapacity;  
    if (newCapacity - MAX_ARRAY_SIZE > 0)  
        newCapacity = hugeCapacity(minCapacity);  
    elementData = Arrays.copyOf(elementData, newCapacity);  
}  

private static int hugeCapacity(int minCapacity) {  
    if (minCapacity < 0) // overflow  
        throw new OutOfMemoryError();  
    return (minCapacity > MAX_ARRAY_SIZE) ?  
        Integer.MAX_VALUE :  
        MAX_ARRAY_SIZE;  
} 

search()

  找到一个最靠近栈顶端的匹配元素,然后返回这个元素到栈顶的距离

public synchronized int search(Object o) {  
    int i = lastIndexOf(o);  

    if (i >= 0) {  
        return size() - i;  
    }  
    return -1;  
} 

对应在vector里面的实现也相对容易理解:

public synchronized int lastIndexOf(Object o) {  
    return lastIndexOf(o, elementCount-1);  
}  

public synchronized int lastIndexOf(Object o, int index) {  
    if (index >= elementCount)  
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);  

    if (o == null) {  
        for (int i = index; i >= 0; i--)  
            if (elementData[i]==null)  
                return i;  
    } else {  
        for (int i = index; i >= 0; i--)  
            if (o.equals(elementData[i]))  
                return i;  
    }  
    return -1;  
}  


lastIndexOf是从数组的末端往前遍历,如果找到这个对象就返回。如果到头了,还未找到就返回个-1。

栈和队列的区别

  • 队列是FIFO的(先进先出),堆栈是FILO的(现今后出)

  • 栈是限定只能在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表

  • 栈只能从头部取数据,也就最先放入的需要遍历整个栈最后才能取出来,而且在遍历数据的时候还得为数据开辟临时空间; 
    队列基于地址指针进行遍历,而且可以从头或尾部开始遍历,但不能同时遍历,无需开辟临时空间,因为在遍历的过程中不影像数据结构,速度要快的多。













版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
8661 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2849 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
11025 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10493 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
11950 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
8806 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
12305 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4573 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
21747 0
1955
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载