数据结构之栈(使用、自实现、应用及栈与虚拟机栈和栈帧的区别)

导读:本篇文章讲解 数据结构之栈(使用、自实现、应用及栈与虚拟机栈和栈帧的区别),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

目录

  • 一、栈是什么?
  • 二、栈的接口设计
  • 三、栈的常用方法
  • 四、栈的底层是什么?
  • 五、栈的自实现(数组、单链表、双向链表)
  • 六、栈的应用(浏览器的前进后退、根据逆波兰表达式求值)
  • 七、栈、虚拟机栈、栈帧有什么区别呢?

一、栈是什么?

是一种特殊的线性表,只能在一端进行操作

往栈中添加元素的操作,一般叫做push,入栈

从栈中移除元素的操作,一般叫做pop,出栈(只能移除栈顶元素,也叫做弹出栈顶元素)

遵循先进后出,后进先出的原则

b11e435aceb748ea803496b085521560.png

 注意:这里所说的栈和栈空间是两个不同的概念,栈是一种数据结构,用来组织数据和存放数据的,而栈空间是内存的一种,是一种内存空间。

 

二、栈的接口设计

栈可以直接在链表的基础上去实现,运用组合的方式,让ArrayList成为栈的一部分,然后在此基础上实现栈的功能。

◼ int size(); // 元素的数量
 
◼ boolean isEmpty(); // 是否为空
 
◼ void push(E element); // 入栈
 
◼ E pop(); // 出栈
 
◼ E top(); // 获取栈顶元素
 
◼ void clear(); // 清空
public class Stack<E> {
	private List<E> list = new ArrayList<>();
	
	public void clear() {
		list.clear();
	}
	
	public int size() {
		return list.size();
	}

	public boolean isEmpty() {
		return list.isEmpty();
	}

	public void push(E element) {
		list.add(element);
	}


	public E pop() {
		return list.remove(list.size() - 1);
	}


	public E top() {
		return list.get(list.size() - 1);
	}
}

 

三、栈的常用方法

方法 功能
Stack()
构造一个空的栈
E push(E e)
将e入栈,并返回e
E pop()
将栈顶元素出栈并返回
E peek()
获取栈顶元素
int size()
获取栈中有效元素个数
boolean empty()
检测栈是否为空

四、栈的底层是什么?

通过观察源码,我们可以发现,Stack继承了Vector。

bf0680cf07c04cefbbf1c19bd1ac9e7a.png

 f8f85adc1e6746188bee9446d776b618.png

 Vector是用数组实现的,所以栈的底层是数组。

五、栈的自实现(数组、单链表、双向链表)

一:用数组自实现:

public class MyStack {
    int[] elem;
    int usesize;
    static final int DEFAULT_SIZE = 10;
    public MyStack(){
        this.elem = new int[DEFAULT_SIZE];
    }
    public int push(int val){
        if (isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usesize] = val;
        usesize++;
        return val;
    }
    public boolean isFull(){
        return usesize == elem.length;
    }
    public int pop(){
        if (empty()){
            throw new MyEmptyStackException("栈为空!");
        }
        return elem[--usesize];
    }
    public boolean empty(){
        return usesize == 0;
    }
    public int peek(){
        if (empty()){
            throw new MyEmptyStackException("栈为空!");
        }
        return elem[usesize-1];
    }
}

二:用单链表的也可以实现,其中入栈用头插,出栈也是在头部,时间复杂度为O(1)。当然双向链表也可以实现栈,而且头尾都可以作为出栈和入栈。 

六、栈的应用(浏览器的前进后退、根据逆波兰表达式求值)

浏览器的前进和后退其实就是用到了栈。

当我们连续输入三个网站,比如,baidu.com,taobao.com,qq.com

156322aa54394581b3609073ed6a284e.png

这个时候这三个网站可以前进和后退,其实这里是用到了两个栈。

831ed540bd8145b395566145641d3b27.png

 358997da604c4123a7cddc43baf4e57f.png

 但是当我们后退到中间位置时,即没有在最后进来的网站的时候,这个时候我们再次输入bilibili.com的时候,在之前位置的后面的网站全都清空了,把新加进来的网站做为最新的最后的网站。

1d631cbd3b8e4fdab8ec99db486b643b.png

根据逆波兰表达式求值:

中缀表达式转后缀表达式(逆波兰式):

7adbbefd0d8d47e5a0a1ef446d6fd9cb.png

用栈实现计算后缀表达式:1 2 3 * + 4 5 * 6 + 7 * +

方法:遇到数字入栈,遇到运算符出栈顶的两个元素,其中弹出的第一个是右操作数,第二个是左操作数。

7b2286a446a240c1adddc817707551af.png 

 

七、栈、虚拟机栈、栈帧有什么区别呢? 

栈是一种先进后出的数据结构。

虚拟机栈是JVM的一块内存空间。

栈帧是在函数的调用过程中,在java虚拟机栈上开辟的一块内存。

 


 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/94599.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!