Java-栈和队列 | Yu's Blog

力扣225. 用队列实现栈

力扣232.用栈实现队列

这里不自己造轮子，主要讲一下Java里这两个数据结构相关的实现类

Java Stack类

Java集合框架提供了一个Stack类，它模拟和实现了一个 Stack数据结构 该类是基于后进先出的基本原则。除了基本的push和pop操作外，该类还提供了empty、search和peek三种功能。该类也可以说是对Vector的扩展，并将该类作为一个具有上述五个功能的堆栈。该类也可以被称为Vector的子类。

下图显示了 Stack类的层次结构

该类支持一个默认的构造函数 Stack() ，用于创建一个空栈。

声明

1	public class Stack<E> extends Vector<E>

所有实现的接口 。

可序列化（Serializable）： 这是一个标记性的接口，如果类要被序列化和反序列化，就必须实现它。
Cloneable: 这是Java中的一个接口，需要由一个类来实现，以使其对象可以被克隆。
Iterable <E>：这个接口表示一个可迭代的对象集合，意思是可以迭代。
Collection <E>:一个集合代表了一组被称为其元素的对象。在需要最大限度的通用性时，Collection接口被用来传递对象的集合。
List <E>:List接口提供了一种存储有序集合的方法。它是Collection的一个子接口。
RandomAccess： 这是一个标记接口，由List实现使用，表示它们支持快速（一般是恒定时间）的随机访问。

如何创建一个堆栈

为了创建一个堆栈，我们必须导入 java.util.stack 包并使用该类的Stack()构造函数。下面的例子创建了一个空的堆栈。

1	Stack<E> stack = new Stack<E>()

这里E是对象的类型。

例子

// Java code for stack implementation
  
import java.io.*;
import java.util.*;
  
class Test
{   
    // Pushing element on the top of the stack
    static void stack_push(Stack<Integer> stack)
    {
        for(int i = 0; i < 5; i++)
        {
            stack.push(i);
        }
    }
      
    // Popping element from the top of the stack
    static void stack_pop(Stack<Integer> stack)
    {
        System.out.println("Pop Operation:");
  
        for(int i = 0; i < 5; i++)
        {
            Integer y = (Integer) stack.pop();
            System.out.println(y);
        }
    }
  
    // Displaying element on the top of the stack
    static void stack_peek(Stack<Integer> stack)
    {
        Integer element = (Integer) stack.peek();
        System.out.println("Element on stack top: " + element);
    }
      
    // Searching element in the stack
    static void stack_search(Stack<Integer> stack, int element)
    {
        Integer pos = (Integer) stack.search(element);
  
        if(pos == -1)
            System.out.println("Element not found");
        else
            System.out.println("Element is found at position: " + pos);
    }
  
  
    public static void main (String[] args)
    {
        Stack<Integer> stack = new Stack<Integer>();
  
        stack_push(stack);
        stack_pop(stack);
        stack_push(stack);
        stack_peek(stack);
        stack_search(stack, 2);
        stack_search(stack, 6);
    }
}

输出
Pop Operation:
4
3
2
1
0
Element on stack top: 4
Element is found at position: 3
Element not found

Stack类中的方法

方法	描述
empty()	如果堆栈的顶部没有任何东西，则返回true。否则，返回false。
peek()	返回堆栈顶部的元素，但不删除它。
pop()	删除并返回堆栈顶部的元素。如果我们在调用pop()时，调用的堆栈是空的，就会抛出一个’EmptyStackException’异常。
push(Object element)	将一个元素推到堆栈的顶部。
search(Object element)	它确定一个对象是否存在于堆栈中。如果找到该元素，它返回该元素在堆栈顶部的位置。否则，它返回-1。

Java Stack类

队列接口存在于java.util包中，并扩展了Collection接口，用于保存即将以FIFO（先进先出）顺序处理的元素。它是一个有序的对象列表，其用途仅限于在列表的末尾插入元素和从列表的开头删除元素，（即）它遵循 先进先出 的原则。

队列的特点： 以下是队列的特点。

队列用于在队列的末端插入元素，并从队列的开头删除。它遵循FIFO概念。
Java队列支持集合接口的所有方法，包括插入、删除等。
LinkedList、ArrayBlockingQueue和PriorityQueue是最常使用的实现方式。
如果对阻塞队列进行任何空操作，就会抛出NullPointerException。
java.util包中的队列是无界队列。
java.util.concurrent包中的队列是有界队列。
除了Deques之外，所有的队列都分别支持在队列的尾部和头部进行插入和删除。Deques支持两端的元素插入和删除。

package java.util;

public interface Queue<E> extends Collection<E> {
    /**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);

    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);

    /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();

    /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
}

参考：https://geek-docs.com/java/java-collection/g_queue-interface-java.html