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

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

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

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

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

堆栈如何工作？

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

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

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

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

什么是队列？

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

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

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

队列类型

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

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

堆栈和队列的优缺点

堆栈和队列的基本操作

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

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

}

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”);

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

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

}

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

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

}

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()+" ");
            }
	}
}

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