数据结构教程系列06：如何在Java中使用堆栈和队列

数据结构教程系列

数据结构教程系列01：JavaScript数组教程

数据结构教程系列02：使用Java深入研究树

数据结构教程系列03：如何在Java中使用链接列表

数据结构教程系列04：在JavaScript中引入图

数据结构教程系列05：在JavaScript中实现哈希表

数据结构教程系列06：如何在Java中使用堆栈和队列

掌握数据结构是不可谈判的。高效的数据结构有助于执行有效的程序。如今，许多编程角色都要求对数据结构有深入的了解。它们也是编码面试的基本部分。

堆栈和队列是线性数据结构，遵循特定的顺序来添加或删除实体。它们在我们移除实体的方式上有所不同。在本文中，将向您介绍栈和队列。我们将重点介绍它们的用途，功能，并向您展示如何在Java中实现这些数据结构。

今天，我们将介绍：

什么是堆栈？
什么是队列？
堆栈和队列的优缺点
基本操作
如何在Java中实现堆栈
如何在Java中实现队列
接下来要学什么和面试问题

什么是堆栈？

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

插入和删除发生在同一端

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

这称为后进先出（LIFO）或先进先出（FILO）排序。

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

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

堆栈如何工作？

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

将元素插入堆栈时，它将占据最高位置，并且存储该位置的变量指向其下方的数字。顶部变量应在元素插入或删除时随时更新。

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

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

什么是队列？

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

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

插入和删除发生在不同的末端

如果要排队，可以考虑在您最喜欢的杂货店结帐柜台。结帐行中的第一个人将在其他人之前首先参加，排行中的最后一个人将在最后一个出席。这就是队列的工作方式。它有两个末端，前部和后部。元素从后面进入，从前面离开。

队列类型

您可能会遇到三种常见的队列类型。到目前为止，我们了解了线性队列。其他两个队列是：

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

堆栈和队列的优缺点

堆栈

优点

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

缺点

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

Queue列

优点

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

缺点

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

堆栈和队列的基本操作

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

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

队列允许执行以下操作：

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

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

top()：返回最近添加到堆栈中的元素
intStack.peek()：返回栈顶而不删除元素
poll()：删除队列的头并返回它
size()：以元素数的形式返回队列的大小
isEmpty()：true如果堆栈/队列已满，则返回
isFull()：true如果堆栈/队列已满，则返回

如何在Java中实现堆栈

每种编程语言都具有堆栈的基本功能。但是，在Java中，堆栈数据类型是Adapter class。这意味着它是建立在其他数据结构之上的。因此，可以使用数组，向量，链接列表或任何其他集合来实现它。

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

不管所使用的基础数据结构或编程语言如何，堆栈都必须实现相同的基本功能。在Java中，可以导入堆栈的预构建类，也可以手动实现堆栈并扩展其功能。为了实现内置的Stack类，我们使用java.util以下import语句使用该包：

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类：

main.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!");
    }
}

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;
    }

}

在将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");
    }
}

Stack.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];
    }
}

如果您的输出返回truefor isEmpty()和falsefor isFull()，则表示这些帮助器功能正常运行！现在，看一下带有push和pop添加到Stack类定义中的函数的扩展代码。我们将尝试在此堆栈中添加和删除一些元素。

main.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 
}

Stack.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];
    }

    //inserts a value to the top of Stack
    public void push(V value){
        if(isFull()) {
            System.err.println("Stack is Full!");
            return;
        }
        array[++top] = value; //increments the top and adds value to updated top
    }

    //removes a value from top of Stack and returns
    public V pop(){
        if(isEmpty())
            return null;
        return array[top--]; //returns value and top and decrements the top
    }

}

在代码输出中，您可以看到元素按推入时的顺序完全相反地从堆栈中弹出。这意味着我们的堆栈可以完美地工作。

如何在Java中实现队列

最常见的队列实现是使用数组，但是也可以使用链接列表或从堆栈开始实现。我们可以使用以下命令导入队列接口：

import java.util.queue;
// or
import java.util.*;

然后，我们使用以下语句创建队列接口，该接口为队列创建链表并提供值：

Queue<String> str_queue = new LinkedList<> ();
str_queue.add(“one”);
str_queue.add(“two”);
str_queue.add(“three”);

让我们来看一个使用整数数据类型并创建实例的Queue类的手动示例。该类将容纳5个数据成员，以容纳以下信息：

包含所有元素的数组
的maxSize是这样的阵列的大小
队列的前端元素
队列的后面元素
所述currentSize队列中的元素

下面给出的代码显示了如何构造Queue类：

main.java

class QueueDemo {
 
	public static void main(String[] args) {
		Queue<Integer> queue = new Queue<Integer>(5);
        System.out.print("You have successfully created a Queue!");
	}
}

stack.java

public class Queue<V> {
    private int maxSize;
    private V[] array;
    private int front;
    private int back;
    private int currentSize;

    /*
    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 Queue(int maxSize) {
        this.maxSize = maxSize;
        array = (V[]) new Object[maxSize];
        front = 0;
        back = -1;
        currentSize = 0;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public int getCurrentSize() {
        return currentSize;
    }

}

在将enqueueand dequeue方法添加到此类之前，我们需要实现一些辅助方法。这里将使用前述的辅助方法。现在运行以下代码，查看辅助函数是否正确输出。

main.java

class QueueDemo {
	public static void main(String[] args) {
		Queue<Integer> queue = new Queue<Integer>(5); //create the queue
    
        if(queue.isEmpty())
        System.out.print("Queue is empty.");
        else
        System.out.print("Queue is not empty.");
        
        System.out.printf("%n");
        
        if(queue.isFull())
        System.out.print("Queue is full.");
        else
        System.out.print("Queue is not full.");
	}
}

stack.java

public class Queue<V> {
    private int maxSize;
    private V[] array;
    private int front;
    private int back;
    private int currentSize;

    /*
    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 Queue(int maxSize) {
        this.maxSize = maxSize;
        array = (V[]) new Object[maxSize];
        front = 0;
        back = -1;
        currentSize = 0;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public int getCurrentSize() {
        return currentSize;
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public boolean isFull() {
        return currentSize == maxSize;
    }

    public V top() {
        return array[front];
    }

}

对于上述代码，由于队列为空，因此isEmpty() 应返回true，并且isFull()应返回false。现在，我们将使用enqueue方法扩展此代码以添加元素，并使用dequeue方法扩展该元素以从队列中删除元素。

main.java

class QueueDemo {
	public static void main(String[] args) {
		Queue<Integer> queue = new Queue<Integer>(5);
		//equeue 2 4 6 8 10 at the end
        queue.enqueue(2);
		queue.enqueue(4);
		queue.enqueue(6);
		queue.enqueue(8);
		queue.enqueue(10);
        //dequeue 2 elements from the start
		queue.dequeue();
		queue.dequeue();
		//enqueue 12 and 14 at the end
        queue.enqueue(12);
        queue.enqueue(14);

        System.out.println("Queue:");
        while(!queue.isEmpty()){
                System.out.print(queue.dequeue()+" ");
            }
	}
}

stack.java

public class Queue<V> {
    private int maxSize;
    private V[] array;
    private int front;
    private int back;
    private int currentSize;

    /*
    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 Queue(int maxSize) {
        this.maxSize = maxSize;
        array = (V[]) new Object[maxSize];
        front = 0;
        back = -1;
        currentSize = 0;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public int getCurrentSize() {
        return currentSize;
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public boolean isFull() {
        return currentSize == maxSize;
    }

    public V top() {
        return array[front];
    }

    public void enqueue(V value) {
        if (isFull())
            return;
        back = (back + 1) % maxSize; //to keep the index in range
        array[back] = value;
        currentSize++;
    }

    public V dequeue() {
        if (isEmpty())
            return null;

        V temp = array[front];
        front = (front + 1) % maxSize; //to keep the index in range
        currentSize--;

        return temp;
    }
}

查看代码的输出，并注意元素在后面入队，并从前面出队。这意味着我们的队列工作完美。

接下来要学什么和面试问题

您到本文末尾为止。恭喜你！我希望您现在对堆栈和队列数据结构的工作方式有一个良好的基础。掌握Java队列和堆栈的知识还有很多。以下是这些数据结构的一些常见面试挑战：

使用堆栈实现队列
使用队列生成从1到n的二进制数
使用堆栈评估后缀表达式
使用一个数组实现两个堆栈
反转队列的前k个元素
创建堆栈，其中min()给出最小的 $O （ 1 ）$

数据结构教程系列06：如何在Java中使用堆栈和队列

数据结构教程系列

什么是堆栈？

堆栈如何工作？

什么是队列？

队列类型

堆栈和队列的优缺点

堆栈

Queue列

堆栈和队列的基本操作

如何在Java中实现堆栈

如何在Java中实现队列

接下来要学什么和面试问题

常见问题FAQ

IT 大叔普通

发表评论取消回复

IT人小站资源共享中心

WWW.ITXIAOZHAN.CN

关于会员

本站导航

精选内容

数据结构教程系列

什么是堆栈？

堆栈如何工作？

什么是队列？

队列类型

堆栈和队列的优缺点

堆栈

Queue列

堆栈和队列的基本操作

如何在Java中实现堆栈

如何在Java中实现队列

接下来要学什么和面试问题

常见问题FAQ

IT 大叔 普通

发表评论 取消回复

相关推荐

IT人小站资源共享中心

WWW.ITXIAOZHAN.CN

IT 大叔普通

发表评论取消回复