【Java数据结构】手动实现——栈 和 队列

简介: 笔记

栈(Stack)


概念

栈: 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。


压栈: 栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。


出栈: 栈的删除操作叫做出栈。出数据在栈顶。


20.png

实现


  1. 利用顺序表实现,即使用尾插 + 尾删的方式实现
  2. 利用链表实现,则头尾皆可

相对来说,顺序表的实现上要更为简单一些,所以优先用顺序表实现栈。

import java.util.Arrays;
public class MyStack<T> {
    private T[]stack;//数组
    private int top;//当前可以存放数据元素的下标——>栈顶指针
    //用构造函数给定一个初始容量10的数组
    public MyStack( ){
        this.stack = (T[])new Object[10];//泛型不能实例化对象,但是可以类型转换
    }
    //判断栈是否满了
    public boolean isFull(){
        return (stack.length == this.top);
    }
    //判断栈是否为空
    public boolean empty(){
        return this.top == 0;
    }
    //入栈操作
    public void push(T value) {
        //判断栈是否已经满了
        if (isFull()){
            this.stack = Arrays.copyOf(stack,2*stack.length);//满了就扩容成原来容量的两倍
        }
        this.stack[this.top] = value;//给top位置添加元素
        this.top++;//top指针指向下一可用空间
    }
    //出栈操作,并返回弹出(删除)栈顶元素
    public T pop() {
        //先判断栈是否为空
        if (empty()) {
            throw new IllegalStateException("栈为空!");
        }
        //弹出元素
        T ret = this.stack[this.top-1];
        this.top--;
        return ret;//返回删除的元素
    }
    //得到栈顶元素,但是不删除
    public T peek() {
        //判断是否为空
        if (empty()){
            throw new IllegalStateException("栈为空!");
        }
        //返回栈顶元素,不删除
        return this.stack[top-1];
    }
    //展示栈元素
    public void show() {
        for (int i = top-1; i>=0 ; i--){
            System.out.print(stack[i]+" ");
        }
        System.out.println();
    }
}

代码测试:

21.png


队列(Queue)


概念


队列: 只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstIn First Out)


入队列: 进行插入操作的一端称为队尾(Tail/Rear)


出队列: 进行删除操作的一端称为队头(Head/Front)

22.png


实现


队列也可以 数组链表 的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据效率会比较低

23.png

public class Node {
    private int val;
    private Node next;
    public Node(int val){
        this.val = val;
    }
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}
public class MyQueue {
    private Node first;
    private Node last;
    //队列是否为空
    public boolean isEmpty() {
        return this.first == null;
    }
    //入队
    public void offer(int value){
        Node node = new Node(value);
        //尾插法,要判断是否第一次插入
        if (this.first == null){
            this.first = node;
            this.last = node;
        }else{
            this.last.setNext(node);
            this.last = node;
        }
    }
    //出队
    public int poll(){
        //判断是否为空
        if (isEmpty()){
            throw new IllegalStateException("队列为空");
        }
        int ret = this.first.getVal();
        this.first = this.first.getNext();
        return ret;//返回出队元素
    }
    //得到队头元素但是不删除
    public int peek() {
        //不要移动first
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空!");
        }
        return this.first.getVal();
    }
    //展示队列
    public void show() {
        Node cur = this.first;
        while(cur != null) {
            System.out.print(cur.getVal()+" ");
            cur = cur.getNext();
        }
        System.out.println();
    }
}


代码测试:

24.png


双端队列


后边会专门出一篇双端队列的博客,有兴趣的小伙伴们可以关注一下


概念

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。

那就说明元素可以从队头出队和入队,也可以从队尾出队和入队


Java中的栈和队列

又是这张图!这张图很重要,请务必记住

25.png


Stack

方法 解释
E push(E item) 压栈
E pop() 出栈
E peek() 查看栈顶元素
boolean empty() 判断栈是否为空


Queue

错误处理 抛出异常 返回特殊值
入队列 add(e) offer(e)
出队列 remove() poll()
队首元素 element() peek()


Deque26.png

相关文章
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
164 77
|
15天前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
26 11
|
17天前
|
存储 IDE Java
java设置栈内存大小
在Java应用中合理设置栈内存大小是确保程序稳定性和性能的重要措施。通过JVM参数 `-Xss`,可以灵活调整栈内存大小,以适应不同的应用场景。本文介绍了设置栈内存大小的方法、应用场景和注意事项,希望能帮助开发者更好地管理Java应用的内存资源。
29 4
|
1月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
2月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
59 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
2月前
|
存储 监控 Java
JAVA线程池有哪些队列? 以及它们的适用场景案例
不同的线程池队列有着各自的特点和适用场景,在实际使用线程池时,需要根据具体的业务需求、系统资源状况以及对任务执行顺序、响应时间等方面的要求,合理选择相应的队列来构建线程池,以实现高效的任务处理。
147 12
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
53 9
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
48 7
|
3月前
|
存储 算法 Java
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
109 5
|
4月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
110 5