1. Overview

1.概述

In this tutorial, we’ll discuss how to create a char stack in Java. We’ll first see how we can do this by using the Java API, and then we’ll look at some custom implementations.

在本教程中，我们将讨论如何在Java中创建一个char栈。我们首先会看到如何通过使用Java API来实现这一目标，然后我们会看看一些自定义的实现。

Stack is a data structure that follows the LIFO (Last In First Out) principle. Some of its common methods are:

堆栈是一种遵循后进先出（LIFO）原则的数据结构。它的一些常用方法有

push(E item) – pushes an item to the top of the stack
pop() – removes and returns the object at the top of the stack
peek() – returns the object at the top of the stack without removing it

2. Char Stack Using Java API

2.字符堆栈使用Java API

Java has a built-in API named java.util.Stack. Since char is a primitive datatype, which cannot be used in generics, we have to use the wrapper class of java.lang.Character to create a Stack:

Java有一个名为java.util.Stack的内置API。由于char是一个原始数据类型，不能用于泛型，我们必须使用java.lang.Character的包装类来创建Stack。

Stack<Character> charStack = new Stack<>();

Now, we can use the push, pop, and peek methods with our Stack.

现在，我们可以使用push、pop和peek方法与我们的Stack。

On the other hand, we may be asked to build a custom implementation of a stack. Therefore, we’ll be looking into a couple of different approaches.

另一方面，我们可能被要求建立一个自定义的堆栈实现。因此，我们将研究几种不同的方法。

3. Custom Implementation Using LinkedList

3.使用LinkedList的自定义实现

Let’s implement a char stack using a LinkedList as our back-end data structure:

让我们使用LinkedList作为后端数据结构，实现一个char堆栈。

public class CharStack {

    private LinkedList<Character> items;

    public CharStack() {
        this.items = new LinkedList<Character>();
    }
}

We created an items variable that gets initialized in the constructor.

我们创建了一个items变量，在构造函数中被初始化。

Now, we have to provide an implementation of the push, peek, and pop methods:

现在，我们必须提供一个push、peek和pop方法的实现。

public void push(Character item) {
    items.push(item);
}

public Character peek() {
    return items.getFirst();
}

public Character pop() {
    Iterator<Character> iter = items.iterator();
    Character item = iter.next();
    if (item != null) {
        iter.remove();
        return item;
    }
    return null;
}

The push and peek methods are using the built-in methods of a LinkedList. For pop, we first used an Iterator to check if there’s an item on the top or not. If it’s there, we remove the item from the list by calling the remove method.

push和peek方法是使用LinkedList的内置方法。对于pop，我们首先使用一个Iterator来检查顶部是否有一个项目。如果有，我们通过调用remove方法将该项目从列表中移除.。

4. Custom Implementation Using an Array

4.使用数组的自定义实现

We can also use an array for our data structure:

我们也可以使用一个数组作为我们的数据结构。

public class CharStackWithArray {

    private char[] elements;
    private int size;

    public CharStackWithArray() {
        size = 0;
        elements = new char[4];
    }

}

Above, we create a char array, which we initialize in the constructor with an initial capacity of 4. Additionally, we have a size variable to keep track of how many records are present in our stack.

上面，我们创建了一个char数组，我们在构造函数中初始化了它，初始容量为4。此外，我们还有一个size变量来跟踪我们堆栈中的记录数量。

Now, let’s implement the push method:

现在，让我们来实现push方法。

public void push(char item) {
    ensureCapacity(size + 1);
    elements[size] = item;
    size++;
}

private void ensureCapacity(int newSize) {
    char newBiggerArray[];
    if (elements.length < newSize) {
        newBiggerArray = new char[elements.length * 2];
        System.arraycopy(elements, 0, newBiggerArray, 0, size);
        elements = newBiggerArray;
    }
}

While pushing an item to the stack, we first need to check if our array has the capacity to store it. If not, we create a new array and double its size. We then copy the old elements to the newly created array and assign it to our elements variable.

在向堆栈推送一个项目时，我们首先需要检查我们的数组是否有足够的容量来存储它。如果没有，我们创建一个新的数组，并将其大小增加一倍。然后我们将旧的元素复制到新创建的数组中，并将其分配给我们的elements变量。

Note: for an explanation of why we want to double the size of the array, rather than simply increase the size by one, please refer to this StackOverflow post.

注意：关于为什么我们要把数组的大小增加一倍，而不是简单地增加一个，请参考这个StackOverflow帖子。

Finally, let’s implement the peek and pop methods:

最后，我们来实现peek和pop方法。

public char peek() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[size - 1];
}

public char pop() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[--size];
}

For both methods, after validating that the stack is not empty, we return the element at position size – 1. For pop, in addition to returning the element, we decrement the size by 1.

对于这两种方法，在验证了堆栈不是空的之后，我们返回位于size – 1位置的元素。对于pop，除了返回元素外，我们还将size递减1。

5. Conclusion

5.总结

In this article, we learned how to make a char stack using the Java API, and we saw a couple of custom implementation.

在这篇文章中，我们学习了如何使用Java API制作一个char堆栈，我们看到了几个自定义的实现。

The code presented in this article is available over on GitHub.

本文介绍的代码可在GitHub上获得。