Java数据结构之栈与队列实例详解

目录
  • 一,栈
    • 1,概念
    • 2,栈的操作
    • 3,栈的实现
    •  4,实现mystack
  • 二,队列
    • 1,概念
    •  2,队列的实现
    •  3,实现myqueue
  • 栈、队列与数组的区别?
  • 总结

一,栈

1,概念

在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的。比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页。

 

很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的软件具体实现会有很大差异,不过原理其实都是一样的。

栈( stack )是限定仅在表尾进行插入和删除的线性表

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

2,栈的操作

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

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

3,栈的实现

①入栈

 

 public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        int ret = stack.push(4);
        System.out.println(ret);
    }

②出栈

  public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        int ret1 = stack.pop();
        int ret2 = stack.pop();
        System.out.println(ret1);
        System.out.println(ret2);
    }

③获取栈顶元素

 public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        int ret1 = stack.pop();
        int ret2 = stack.pop();
        int ret3 = stack.peek();
        System.out.println(ret1);
        System.out.println(ret2);
        System.out.println(ret3);
    }

④判断栈是否为空

  public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        int ret1 = stack.pop();
        int ret2 = stack.pop();
        int ret3 = stack.peek();
        System.out.println(ret1);
        System.out.println(ret2);
        System.out.println(ret3);
        stack.pop();
        boolean flag = stack.empty();
        System.out.println(flag);
    }

 4,实现mystack

public class MyStack<T> {
    private T[] elem;//数组
    private int top;//当前可以存放数据元素的下标-》栈顶指针

    public MyStack() {
        this.elem = (T[])new Object[10];
    }

    /**
     * 入栈操作
     * @param item 入栈的元素
     */
    public void push(T item) {
        //1、判断当前栈是否是满的
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //2、elem[top] = item  top++;
        this.elem[this.top++] = item;
    }

    public boolean isFull(){
        return this.elem.length == this.top;
    }

    /**
     * 出栈
     * @return 出栈的元素
     */
    public T pop() {
        if(empty()) {
            throw new UnsupportedOperationException("栈为空!");
        }
        T ret = this.elem[this.top-1];
        this.top--;//真正的改变了top的值
        return ret;
    }

    /**
     * 得到栈顶元素,但是不删除
     * @return
     */
    public T peek() {
        if(empty()) {
            throw new UnsupportedOperationException("栈为空!");
        }
        //this.top--;//真正的改变了top的值
        return this.elem[this.top-1];
    }
    public boolean empty(){
        return this.top == 0;
    }
}
public class MyStack<T> {
    private T[] elem;//数组
    private int top;//当前可以存放数据元素的下标-》栈顶指针

    public MyStack() {
        this.elem = (T[])new Object[10];
    }

    /**
     * 入栈操作
     * @param item 入栈的元素
     */
    public void push(T item) {
        //1、判断当前栈是否是满的
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //2、elem[top] = item  top++;
        this.elem[this.top++] = item;
    }

    public boolean isFull(){
        return this.elem.length == this.top;
    }

    /**
     * 出栈
     * @return 出栈的元素
     */
    public T pop() {
        if(empty()) {
            throw new UnsupportedOperationException("栈为空!");
        }
        T ret = this.elem[this.top-1];
        this.top--;//真正的改变了top的值
        return ret;
    }

    /**
     * 得到栈顶元素,但是不删除
     * @return
     */
    public T peek() {
        if(empty()) {
            throw new UnsupportedOperationException("栈为空!");
        }
        //this.top--;//真正的改变了top的值
        return this.elem[this.top-1];
    }
    public boolean empty(){
        return this.top == 0;
    }
}

二,队列

1,概念

像移动、联通、电信等客服电话,客服人员与客户相比总是少数,在所有的客服人员都占线的情况下,客户会被要求等待,直到有某个客服人员空下来,才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。

操作系统和客服系统中,都是应用了种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。

队列(queue) 是只允许在一端进行插入操作,而在另一端进行删除操作的线性表

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头 (Head/Front)

 2,队列的实现

①入队

 public static void main(String[] args) {
        Deque<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);

    }

②出队

  public static void main(String[] args) {
        Deque<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue.poll());
        System.out.println(queue.poll());

    }

③获取队首元素

public static void main(String[] args) {
        Deque<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println("-----------------");
        System.out.println(queue.peek());
    }

 3,实现myqueue

class Node {
    private int val;
    private Node next;
    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 Node(int val) {
        this.val = val;
    }
}
public class MyQueue {
    private Node first;
    private Node last;
    //入队
    public void offer(int val) {
        //尾插法  需要判断是不是第一次插入
        Node node = new Node(val);
        if(this.first == null) {
            this.first = node;
            this.last = node;
        }else {
            this.last.setNext(node);//last.next = node;
            this.last = node;
        }
    }
    //出队
    public int poll() {
        //1判断是否为空的
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空!");
        }
        //this.first = this.first.next;
        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 boolean isEmpty() {
        return this.first == null;
    }
}
 public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        System.out.println(myQueue.peek());
        System.out.println(myQueue.poll());
        System.out.println(myQueue.poll());
        System.out.println(myQueue.poll());
        System.out.println(myQueue.isEmpty());

    }

栈、队列与数组的区别?

A: 栈、队列和优先级队列与数组主要有如下三个区别:

A: (一)程序员工具 

数组和其他的结构(栈、队列、链表、树等等)都适用于数据库应用中作为数据记录。它们常用于记录那些对应于现实世界的对象和活动的数据,如职员档案等,这些结构便于数据的访问:它们易于进行插入、删除和查找特定数据项的操作。 

然而,本篇要讲解的数据结构和算法更多的是作为程序员的工具来运用。它们主要作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短得多。在程序操作执行期间它们才被创建,通常用它们去执行某项特殊的任务;当完成任务之后,它们则被销毁。

A: (二)受限访问 

在数组中,若知道数据项的下标,便可以立即访问该数据项;而在本篇的数据结构中,访问是受限制的,即在特定时刻只有一个数据项可以被读取或者删除。 

这些结构接口的设计增强了这种受限访问,访问其他数据项理论上是不允许的。

A: (三)更加抽象 

栈、队列和优先队列是比数组和其他数据存储结构更为抽象的结构。主要是通过接口对栈、队列和优先队列进行定义,接口表明了它们可以完成的操作,而主要实现机制对用户来说是不可见的。 

例如:栈的实现机制可以用数组实现,本篇的示例就是这样处理的,但它也可以用链表来实现。优先级队列的内部实现可以用数组或一种特别的树-堆来实现。

总结

到此这篇关于Java数据结构之栈与队列的文章就介绍到这了,更多相关Java数据结构栈与队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java模拟栈和队列数据结构的基本示例讲解

    栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv

  • Java实现栈和队列面试题

    面试的时候,栈和队列经常会成对出现来考察.本文包含栈和队列的如下考试内容: (1)栈的创建 (2)队列的创建 (3)两个栈实现一个队列 (4)两个队列实现一个栈 (5)设计含最小函数min()的栈,要求min.push.pop.的时间复杂度都是O(1) (6)判断栈的push和pop序列是否一致 1.栈的创建: 我们接下来通过链表的形式来创建栈,方便扩充. 代码实现: public class Stack { public Node head; public Node current; //方法

  • java中栈和队列的实现和API的用法(详解)

    在java中要实现栈和队列,需要用到java集合的相关知识,特别是Stack.LinkedList等相关集合类型. 一.栈的实现 栈的实现,有两个方法:一个是用java本身的集合类型Stack类型:另一个是借用LinkedList来间接实现Stack. 1.Stack实现 直接用Stack来实现非常方便,常用的api函数如下: boolean        isEmpty() // 判断当前栈是否为空 synchronized E        peek() //获得当前栈顶元素 synchro

  • java 数据结构中栈和队列的实例详解

    java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • java 数据结构之栈与队列

    java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

  • Java数据结构之栈与队列实例详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现  4,实现mystack 二,队列 1,概念  2,队列的实现  3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页.   很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的

  • Java深入了解数据结构之栈与队列的详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现 ①入栈 ②出栈 ③获取栈顶元素 ④判断栈是否为空 4,实现mystack 二,队列 1,概念 2,队列的实现 ①入队 ②出队 ③获取队首元素 3,实现myqueue 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的

  • Java数据结构之栈的线性结构详解

    目录 一:栈 二:栈的实现 三:栈的测试 四:栈的应用(回文序列的判断) 总结 一:栈 栈是限制插入和删除只能在一个位置上进行的表,此位置就是表的末端,叫作栈顶. 栈的基本操作分为push(入栈) 和 pop(出栈),前者相当于插入元素到表的末端(栈顶),后者相当于删除栈顶的元素. 二:栈的实现 public class LinearStack { /** * 栈的初始默认大小为10 */ private int size = 5; /** * 指向栈顶的数组下标 */ int top = -1

  • 数据结构 栈的操作实例详解

    数据结构 栈的操作实例详解 说明: 往前学习数据结构,想运行一个完整的顺序栈的程序都运行不了,因为书上给的都是一部分一部分的算法,并没有提供一个完整可运行的程序,听了实验课,自己折腾了一下,总算可以写一个比较完整的顺序栈操作的小程序,对于栈也慢慢开始有了感觉.下面我会把整个程序拆开来做说明,只要把这些代码放在一个文件中,用编译器就可以直接编译运行了. 一.实现 1.程序功能 关于栈操作的经典程序,首当要提及进制数转换的问题,利用栈的操作,就可以十分快速地完成数的进制转换. 2.预定义.头文件导入

  • Java 栈和队列的相互转换详解

    目录 用栈实现队列-力扣232题 用队列实现栈-力扣225题  1. 双队列实现栈 2.一个队列实现栈 栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除.因此,栈和队列可以相互转换. 用栈实现队列-力扣232题 题目要求:仅使用两个栈实现先入先出队列.队列应当支持一般队列支持的所有操作 使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助  上图可以看到,新元素进栈时,要确保该栈为空.进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中.

  • Java 异常的栈轨迹(Stack Trace)详解及实例代码

    Java 异常的栈轨迹(Stack Trace)详解 捕获到异常时,往往需要进行一些处理.比较简单直接的方式就是打印异常栈轨迹Stack Trace.说起栈轨迹,可能很多人和我一样,第一反应就是printStackTrace()方法.其实除了这个方法,还有一些别的内容也是和栈轨迹有关的. 1.printStackTrace() 首先需要明确,这个方法并不是来自于Exception类.Exception类本身除了定义了几个构造器之外,所有的方法都是从其父类继承过来的.而和异常相关的方法都是从jav

  • Java 数据结构算法Collection接口迭代器示例详解

    目录 Java合集框架 Collection接口 迭代器 Java合集框架 数据结构是以某种形式将数据组织在一起的合集(collection).数据结构不仅存储数据,还支持访问和处理数据的操作 在面向对象的思想里,一种数据结构也被认为是一个容器(container)或者容器对象(container object),它是一个能存储其他对象的对象,这里的其他对象常被称为数据或者元素 定义一种数据结构从实质上讲就是定义一个类.数据结构类应该使用数据域存储数据,并提供方法支持查找.插入和删除等操作 Ja

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

  • C语言数据结构之图的遍历实例详解

    C语言数据结构之图的遍历实例详解 输入一组顶点,建立无向图的邻接矩阵.输入一组顶点,建立有向图的邻接表.分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历).写出深度优先遍历的递归和非递归算法.根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列. 实现代码: #include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; st

随机推荐