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

2024-04-02 19:04:59 561人浏览泡泡鱼

Python 官方文档：入门教程 => 点击学习

摘要

目录一，栈1，概念2，栈的操作3，栈的实现 4，实现mystack二，队列1，概念 2，队列的实现 3，实现myqueue栈、队列与数组的区别？总结一，栈 1，概念在我们软件应用

一，栈

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];
    }
 
    
    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;
    }
 
    
    public T pop() {
        if(empty()) {
            throw new UnsupportedOperationException("栈为空！");
        }
        T ret = this.elem[this.top-1];
        this.top--;//真正的改变了top的值
        return ret;
    }
 
    
    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];
    }
 
    
    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;
    }
 
    
    public T pop() {
        if(empty()) {
            throw new UnsupportedOperationException("栈为空！");
        }
        T ret = this.elem[this.top-1];
        this.top--;//真正的改变了top的值
        return ret;
    }
 
    
    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());
       
    }