数据结构101：如何在Java中使用栈和队列（一）-阿里云开发者社区

什么是堆栈？

在编程中，堆栈是一种抽象的线性数据类型，具有预定义的容量（或边界）。它遵循添加或删除元素的特定顺序。线性数据结构以直线组织它们的组件，所以如果我们添加或删除一个元素，它们将分别增长或收缩。

网络异常，图片无法展示

让我们使用放置在盒子中的一堆盘子来概念化堆栈。放置在堆叠中的第一个盘子（堆叠底部的盘子）将是最后一个被移除的盘子，最后添加的盘子将是第一个被移除的盘子。

这称为后进先出 (LIFO) 或先进后出 (FILO) 排序。

当我们编码时，堆栈以多种方式使用。我们使用堆栈来实现函数、解析器、表达式求值和一些算法。堆栈非常适合处理嵌套结构，因此它们对于理解递归很重要。

堆栈的一个简单的实际应用是逐个字母地反转字符串。数据堆栈的另一个很好的例子是计算机或文本编辑器上的撤消和重做功能。撤消删除您最近的更改，重做建立在现有更改的基础上。

堆栈如何工作？

栈的实现相对容易。如上图所示，功能取决于pop和方法。push该pop方法从堆栈中移除push或删除元素，同时该方法将项目添加到堆栈。

当一个元素被插入到栈中时，它会占据栈顶位置，存储这个位置的变量指向它下面的数字。每当向其中插入或删除元素时，都应更新顶部变量。

注意： 重要的是要记住插入和删除发生在堆栈的同一端。

在本文后面，我们将学习如何在 Java 中手动实现 Stack 数据结构。

什么是队列？

队列很像堆栈。队列也是一种遵循先进先出 (FIFO) 顺序的线性结构，但它们在删除元素的方式上有所不同。队列从两端开放：一端用于插入数据 ( enqueue)，另一端用于删除数据 ( dequeue)。堆栈仅从一端打开。

简化： 对于堆栈，我们删除最近添加的元素，但对于队列，我们删除“最旧”的元素。

网络异常，图片无法展示

说到排队，想想你最喜欢的杂货店的结账柜台。结账队伍中排在第一位的人将在其他人之前得到最先的接待，而排队的最后一个人将得到最后的接待。这就是队列的工作原理。它有两端，前部和后部。元素从后面进入，从前面离开。

队列类型

您可能会遇到三种常见类型的队列。至此，我们了解了线性队列。另外两个队列是：

循环队列： 在循环队列中，最后一个元素与第一个元素相连形成一个圆圈。最初，队列的前部和后部指向相同的位置，但随着更多元素插入队列，它们会分开。循环队列的一个真实示例是自动交通信号系统。
优先队列： 在优先队列中，元素根据优先级排序。最重要的元素最先出现，最不重要的元素最后出现。[优先级队列在操作系统]中用于负载平衡，以确定应给予哪些程序更高的优先级。

栈和队列的优缺点

堆栈

优点

对于初学者来说很容易实现并且合乎逻辑
它允许您控制内存的分配方式
比队列更容易使用

缺点

既不灵活也不可扩展
随机访问堆栈中的元素几乎是不可能的

队列

优点

队列是灵活的。
他们可以处理多种数据类型。
数据队列快速且优化

缺点

从中间插入/删除元素很复杂。
队列不容易搜索

栈和队列的基本操作

典型的堆栈必须包含以下方法：

pop()：此方法从堆栈顶部删除一个元素并将其返回。
push()：此方法将一个元素添加到堆栈的顶部。

队列允许进行以下操作：

enqueue()：此方法将一个元素添加到队列的尾部/尾部
dequeue()：此方法从队列的前面删除一个元素
top()：返回队列中的第一个元素
initialize(): 创建一个空队列

从那里，我们可以应用各种方法来获得更多功能和信息检索：

top(): 返回最近添加到堆栈的元素
intStack.peek(): 返回栈顶而不移除元素
poll()：删除队列的头部并返回它
size()：返回队列的大小作为元素的数量
isEmpty()``true：如果堆栈/队列已满则返回
isFull()``true：如果堆栈/队列已满则返回

如何在 Java 中实现堆栈

每种编程语言都带有堆栈的基本功能。但是，在 Java 中，堆栈数据类型是Adapter 类。这意味着它建立在其他数据结构之上。因此，它可以使用 Array、Vector、Linked List 或任何其他集合来实现。

注意： 堆栈通常使用数组来实现，因为它占用的内存更少。

无论使用何种底层数据结构或编程语言，堆栈都必须实现相同的基本功能。在 Java 中，您可以导入堆栈的预构建类或手动实现堆栈并扩展其功能。为了实现内置的 Stack 类，我们使用java.util以下导入语句来使用包：

import java.util.*;
// or
import java.util.Stack;
复制代码

导入包后，我们可以创建一个堆栈对象，如下所示：

Stack mystack = new Stack();
复制代码

然后，我们向舞台添加元素。例如，我们可以使用 . 添加整数push()。

Stack<Integer> myStack = new Stack<>();
 myStack.push(5);
 myStack.push(6);
 myStack.push(7);
复制代码

基本语法如下所示：

public class Stack <V> {
    private int maxSize;
    private int top;
    private V arr[];
复制代码

要手动创建堆栈，我们构造一个 Stack 类并创建一个实例。该类具有以下三个数据成员：

一个包含所有元素的数组
这个数组的大小/边界
栈顶元素的变量

以下代码显示了如何构造 Stack 类：

主要的java：

class StackDemo {
    public static void main( String args[] ) {
        Stack<Integer> stack = new Stack<Integer>(10);
        System.out.print("You have successfully created a Stack!");
    }
}
复制代码

堆栈.java：

public class Stack <V> {
    private int maxSize;
    private int top;
    private V arr[];
    /*
    Java does not allow generic type arrays. So we have used an 
    array of Object type and type-casted it to the generic type V.
    This type-casting is unsafe and produces a warning.
    Comment out the line below and execute again to see the warning.
    */
    @SuppressWarnings("unchecked")
    public Stack(int max_size) {
        this.maxSize = max_size;
        this.top = -1; //initially when stack is empty
        arr = (V[]) new Object[max_size];//type casting Object[] to V[]
    }
    public int getCapacity() {
        return maxSize;
    }
}
复制代码

输出：

You have successfully created a Stack!
复制代码

在将 push 和 pop 方法添加到这段代码之前，我们需要实现一些辅助方法。辅助方法使代码简单易懂。下面是我们将在下面的代码中实现的辅助函数列表：

isEmpty()
isFull()
top()

下面是使用新辅助方法的堆栈代码。

main.java：

class HelloWorld {
    public static void main( String args[] ) {
        Stack<Integer> stack = new Stack<Integer>(10);
        //output if stack is empty or not
        if(stack.isEmpty())
        System.out.print("Stack is empty");
        else
        System.out.print("Stack is not empty");
        System.out.printf("%n");
        //output if stack is full or not
        if(stack.isFull())
        System.out.print("Stack is full");
        else
        System.out.print("Stack is not full");
    }
}
复制代码

堆栈.java：

public class Stack <V> {
    private int maxSize;
    private int top;
    private V array[];
    /*
    Java does not allow generic type arrays. So we have used an
    array of Object type and type-casted it to the generic type V.
    This type-casting is unsafe and produces a warning.
    Comment out the line below and execute again to see the warning.
    */
    @SuppressWarnings("unchecked")
    public Stack(int max_size) {
        this.maxSize = max_size;
        this.top = -1; //initially when stack is empty
        array = (V[]) new Object[max_size];//type casting Object[] to V[]
    }
    //returns the maximum size capacity
    public int getMaxSize() {
        return maxSize;
    }
    //returns true if Stack is empty
    public boolean isEmpty(){
        return top == -1;
    }
    //returns true if Stack is full
    public boolean isFull(){
        return top == maxSize -1;
    }
    //returns the value at top of Stack
    public V top(){
        if(isEmpty())
            return null;
        return array[top];
    }
}
复制代码

输出：

Stack is empty
Stack is not full
复制代码

如果您的输出返回trueforisEmpty()和falsefor isFull()，则表示这些辅助函数正常工作！现在，看看这个扩展代码，其中添加了 push 和pop添加到 Stack 类定义的函数。我们将尝试从这个堆栈中添加和删除一些元素。

主要的java：

class StackDemo {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>(5); 
        System.out.print("Elements pushed in the Stack: ");
        for (int i = 0; i < 5; i++) {
            stack.push(i); //pushes 5 elements (0-4 inclusive) to the stack
            System.out.print(i + " ");
        }
        System.out.println("\nIs Stack full? \n" + stack.isFull());
        System.out.print("Elements popped from the Stack: ");
        for (int i = 0; i < 5; i++) {
            System.out.print(stack.pop()+" "); //pops all 5 elements from the stack and prints them
        }
        System.out.println("\nIs Stack empty? \n" + stack.isEmpty());
    }//end of main 
}
复制代码

数据结构101：如何在Java中使用栈和队列（一）

什么是堆栈？

堆栈如何工作？

什么是队列？

队列类型

栈和队列的优缺点

堆栈

队列

栈和队列的基本操作

如何在 Java 中实现堆栈

热门文章

最新文章

相关课程

相关电子书

相关实验场景