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

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

一、栈是什么?


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


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


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


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


1667910011023.jpg


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


二、栈的接口设计


栈可以直接在链表的基础上去实现,运用组合的方式,让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。

1667910112816.jpg

1667910124503.jpg

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

1667910158658.jpg



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

1667910169958.jpg

1667910182914.jpg

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

1667910194986.jpg

根据逆波兰表达式求值:


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


1667910208114.jpg


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


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


1667910220937.jpg


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

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


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


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


相关文章
|
1天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
8 1
【数据结构】栈和队列
|
1天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
9 0
【数据结构OJ题】用栈实现队列
|
1天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
12 0
【数据结构OJ题】用队列实现栈
|
15天前
|
API
用栈翻转字符串
用栈翻转字符串
15 0
|
15天前
|
JavaScript
数据结构(用 JS 实现栈和队列【三种方式】)
数据结构(用 JS 实现栈和队列【三种方式】)
17 0
|
19天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
20天前
|
算法
数据结构与算法:栈与队列
数据结构与算法:栈与队列
|
23天前
|
Unix Linux 虚拟化
虚拟机VMware知识积累
虚拟机VMware知识积累
|
11天前
|
运维 安全 虚拟化