堆栈.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 个数据成员来保存以下信息:
- 一个包含所有元素的数组
- The
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!"); } } 复制代码
队列.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! 复制代码
在将enqueue
和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."); } } 复制代码
队列.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()
应该返回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()+" "); } } } 复制代码
队列.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 复制代码
查看代码的输出,注意元素在后面入队并从前面出队。这意味着我们的队列工作完美。