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

目录

  • 一,栈
    • 1,概念
    • 2,栈的操作
    • 3,栈的实现
      • ①入栈
      • ②出栈
      • ③获取栈顶元素
      • ④判断栈是否为空
    • 4,实现mystack
    • 二,队列
      • 1,概念
        • 2,队列的实现
          • ①入队
          • ②出队
          • ③获取队首元素
        • 3,实现myqueue
        Java深入了解数据结构之栈与队列的详解
        文章图片


        一,栈

        1,概念
        在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的。比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页。
        Java深入了解数据结构之栈与队列的详解
        文章图片

        很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的软件具体实现会有很大差异,不过原理其实都是一样的。
        【Java深入了解数据结构之栈与队列的详解】栈( stack )是限定仅在表尾进行插入和删除的线性表
        栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

        2,栈的操作
        压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
        出栈:栈的删除操作叫做出栈。出数据在栈顶。
        Java深入了解数据结构之栈与队列的详解
        文章图片


        3,栈的实现

        ①入栈 Java深入了解数据结构之栈与队列的详解
        文章图片

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

        Java深入了解数据结构之栈与队列的详解
        文章图片


        ②出栈
        public static void main(String[] args) {Stack 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); }

        Java深入了解数据结构之栈与队列的详解
        文章图片


        ③获取栈顶元素
        public static void main(String[] args) {Stack 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); }

        Java深入了解数据结构之栈与队列的详解
        文章图片


        ④判断栈是否为空 Java深入了解数据结构之栈与队列的详解
        文章图片

        public static void main(String[] args) {Stack 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); }

        Java深入了解数据结构之栈与队列的详解
        文章图片


        4,实现mystack
        public class MyStack {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] = itemtop++; 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 static void main(String[] args) {MyStack myStack = new MyStack<>(); myStack.push(1); myStack.push(2); myStack.push(3); System.out.println(myStack.peek()); System.out.println(myStack.pop()); System.out.println(myStack.pop()); System.out.println(myStack.pop()); System.out.println(myStack.empty()); System.out.println("============================"); MyStack myStack2 = new MyStack<>(); myStack2.push("hello"); myStack2.push("word"); myStack2.push("thank"); System.out.println(myStack2.peek()); System.out.println(myStack2.pop()); System.out.println(myStack2.pop()); System.out.println(myStack2.pop()); System.out.println(myStack2.empty()); }

        Java深入了解数据结构之栈与队列的详解
        文章图片


        二,队列 1,概念
        Java深入了解数据结构之栈与队列的详解
        文章图片

        像移动、联通、电信等客服电话,客服人员与客户相比总是少数,在所有的客服人员都占线的情况下,客户会被要求等待,直到有某个客服人员空下来,才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。
        操作系统和客服系统中,都是应用了种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。
        队列(queue) 是只允许在一端进行插入操作,而在另一端进行删除操作的线性表
        队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头 (Head/Front)
        Java深入了解数据结构之栈与队列的详解
        文章图片


        2,队列的实现

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


        ②出队
        public static void main(String[] args) {Deque 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()); }

        Java深入了解数据结构之栈与队列的详解
        文章图片


        ③获取队首元素
        public static void main(String[] args) {Deque 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()); }

        Java深入了解数据结构之栈与队列的详解
        文章图片


        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() {//不要移动firstif(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()); }

        Java深入了解数据结构之栈与队列的详解
        文章图片

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

          推荐阅读