数据结构(2):栈的原理和实现

简介: 一、介绍栈是一种数据先入后出,后入先出的数据结构。如果图所示,将数字 10、15、6、9 存入栈后,从栈中取到的数据按顺序将会是 9、6、15、10。栈的结构像我们生活中的箱子,最先放入的物品将会在箱子的最底部,最后放入的数据在最上面,拿物品时也需要从最上面拿起。

一、介绍

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

image

如果图所示,将数字 10、15、6、9 存入栈后,从栈中取到的数据按顺序将会是 9、6、15、10。栈的结构像我们生活中的箱子,最先放入的物品将会在箱子的最底部,最后放入的数据在最上面,拿物品时也需要从最上面拿起。

二、代码实现

1、创建 MyStack 类作为自定义的栈

public class MyStack {

}

2、声明所需的属性

底层使用数组存储数据,也可以使用java的泛型替代Object类型。

private Object[] arr;//存储数据
private int top;//栈顶的位置

栈顶:整个栈最上面(最后入栈)的元素,也就是数组中最后存入的元素。

栈底:整个栈最下面(最先入栈)的元素,也就是数组中最先存入的元素。

3、栈的构造方法

public MyStack(){
    arr = new Object[10];
    top = -1;
}

/**
 * 参数为数组的初始长度
 * @param maxSize
 */
public MyStack(int maxSize){
    arr = new Object[maxSize];
    top = -1;
}

4、向栈中压入数据

底层的操作就是向数组中存入数据,由于top变量记栈顶的位置,所以top的值增加1后即为最新的栈顶的置。

 public void push(Object value) {
    arr[++top] = value;
}

5、弹出栈顶的数据

取得栈顶的数据,并将此数据将栈中移除。向栈中压入数据需要将记录栈顶的位置的变量top加1,同理,移除栈顶数据需要将top减1。

public Object pop(){
    return arr[top--];
}

6、查看栈顶数据

public Object peek(){
    return arr[top];
}

7、判断是否为空

public boolean isEmpty(){
    return top == -1;
}

8、判断是否存满

top的值等于数组最后一个元素的位置即为存满

public boolean isFull(){
    return top == arr.length-1;
}

9、完整代码

public class MyStack {
    private Object[] arr;//存储数据
    private int top;//栈顶的位置

    public MyStack() {
        arr = new Object[10];
        top = -1;
    }

    /**
     * 参数为数组的初始长度
     *
     * @param maxSize
     */
    public MyStack(int maxSize) {
        arr = new Object[maxSize];
        top = -1;
    }

    public void push(Object value) {
        arr[++top] = value;
    }

    /**
     * 弹出栈顶的数据
     * @return
     */
    public Object pop(){
        return arr[top--];
    }

    public Object peek(){
        return arr[top];
    }

    public boolean isEmpty(){
        return top == -1;
    }

    public boolean isFull(){
        return top == arr.length-1;
    }
}

三、验证

public static void main(String[] args) {
    MyStack stack = new MyStack(4);
    stack.push("a");
    stack.push("b");
    stack.push("c");
    stack.push("d");

    System.out.println("是否为空:" + stack.isEmpty());
    System.out.println("是否存满:" + stack.isFull());

    System.out.println("栈顶:"+stack.peek());
    System.out.println("栈顶:"+stack.peek());

    //弹出栈中所有数据
    while (!stack.isEmpty()){
        System.out.println(stack.pop());
    }

    System.out.println("是否为空:" + stack.isEmpty());
    System.out.println("是否存满:" + stack.isFull());
}
相关文章
|
25天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
116 9
|
16天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
22 1
|
3天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
22 5
|
18天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
21天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
23天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
47 4
|
28天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
33 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
数据结构(栈与列队)
数据结构(栈与列队)
20 1