数据结构101:如何在Java中使用栈和队列(二)

简介: 数据结构101:如何在Java中使用栈和队列

堆栈.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
    }
}
复制代码

输出:

Elements pushed in the Stack: 0 1 2 3 4 
Is Stack full? 
true
Elements popped from the Stack: 4 3 2 1 0 
Is Stack empty? 
true
复制代码

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

如何在 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 个数据成员来保存以下信息:

  • 一个包含所有元素的数组
  • ThemaxSize是这个数组的大小
  • 队列的前端元素
  • 队列的后元素
  • 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!");
    }
}
复制代码

队列.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;
    }
}
复制代码

输出:

You have successfully created a Queue!
复制代码

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

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.");
    }
}
复制代码

队列.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];
    }
}
复制代码

输出:

Queue is empty.
Queue is not full.
复制代码

对于上面的代码,既然队列是空的,isEmpty()应该返回trueisFull()应该返回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()+" ");
            }
    }
}
复制代码

队列.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;
    }
}
复制代码

输出:

Queue:
6 8 10 12 14 
复制代码

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

相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
8天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
29 6
|
14天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
40 4
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
24 6
|
20天前
|
存储 算法 Java
🧠Java零基础 - Java栈(Stack)详解
【10月更文挑战第17天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
15 2

热门文章

最新文章