实现栈和队列：用Java函数解决
栈和队列是计算机科学中常用的数据结构。它们可以用来轻松地管理数据。栈和队列是两种不同的数据结构，栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。在本文中，我们将介绍如何用Java函数来实现栈和队列。
一、栈
在Java中，可以使用数组或链表来实现栈。我们先来看如何使用数组来实现栈。
1. 使用数组来实现栈
首先，我们需要一个数组来存储栈中的数据，栈顶指针top也需要被定义。
int top = -1; // 栈顶指针
int[] stack = new int[SIZE]; // 定义一个数组作为栈
然后，我们需要实现以下几个基本的栈操作：
- push(x)：将x压入栈顶。
- pop()：弹出栈顶元素，并返回其值。
- isEmpty()：判断栈是否为空。
- isFull()：判断栈是否已满。
下面是使用数组实现的栈代码：
public class Stack {
int top = -1; // 栈顶指针
final int SIZE = 50; // 栈的大小
int[] stack = new int[SIZE]; // 定义一个数组作为栈
// 将x压入栈顶
void push(int x) {
if (top == SIZE - 1) {
System.out.println("Stack overflow!");
} else {
top++;
stack[top] = x;
}
}
// 弹出栈顶元素，并返回其值
int pop() {
if (top == -1) {
System.out.println("Stack underflow!");
return -1;
} else {
int x = stack[top];
top--;
return x;
}
}
// 判断栈是否为空
boolean isEmpty() {
return (top == -1);
}
// 判断栈是否已满
boolean isFull() {
return (top == SIZE - 1);
}
public static void main(String[] args) {
Stack s = new Stack();
s.push(10);
s.push(20);
s.push(30);
while (!s.isEmpty()) {
System.out.println(s.pop());
}
}
}
程序的输出是：
30
20
10
2. 使用链表来实现栈
另一种实现栈的方法是使用链表。链表中的每个节点都保存一个元素和指向下一个节点的引用。当新元素被推送到栈中时，我们可以创建一个新节点并将其添加到链表的头部。这个新节点就成为了新的栈顶。
下面是使用链表实现的栈代码：
public class Stack {
Node top; // 栈顶节点
// 节点内部类
class Node {
int data; // 节点数据
Node next; // 下一个节点
Node(int data) {
this.data = data;
this.next = null;
}
}
// 将x压入栈顶
public void push(int x) {
Node newNode = new Node(x);
if (top == null) {
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
System.out.println(x + " has been pushed into the stack.");
}
// 弹出栈顶元素，并返回其值
public int pop() {
if (top == null) {
System.out.println("Stack underflow!");
return -1;
} else {
int data = top.data;
top = top.next;
System.out.println(data + " has been popped from the stack.");
return data;
}
}
// 判断栈是否为空
public boolean isEmpty() {
return (top == null);
}
public static void main(String[] args) {
Stack s = new Stack();
s.push(10);
s.push(20);
s.push(30);
while (!s.isEmpty()) {
s.pop();
}
}
}
程序的输出是：
10 has been pushed into the stack.
20 has been pushed into the stack.
30 has been pushed into the stack.
30 has been popped from the stack.
20 has been popped from the stack.
10 has been popped from the stack.
二、队列
队列通常使用数组或链表来实现。下面我们将介绍如何使用这两种方法实现队列。
1. 使用数组来实现队列
队列可以使用数组实现，其中队列有两个指针front和rear，front指向队列的 个元素，rear指向队列的最后一个元素。当元素被插入队列时，将其插入rear指针所指向的位置。当从队列中删除元素时，将其从front指针所指向的位置删除。此外，还需要实现以下三个操作：
- enqueue(x)：将x插入队尾。
- dequeue()：从队首删除元素。
- isEmpty()：判断队列是否为空。
下面是使用数组实现的队列代码：
public class Queue {
int front, rear, size;
int[] queue;
public Queue(int x) {
size = x;
front = rear = 0;
queue = new int[size];
}
// 将x插入队尾
public void enqueue(int x) {
if (isFull()) {
System.out.println("Queue is full!");
return;
} else {
queue[rear] = x;
rear++;
System.out.println(x + " has been enqueued into the queue.");
}
}
// 从队首删除元素
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty!");
return -1;
} else {
int x = queue[front];
front++;
System.out.println(x + " has been dequeued from the queue.");
return x;
}
}
// 判断队列是否为空
boolean isEmpty() {
return (front == rear);
}
// 判断队列是否已满
boolean isFull() {
return (rear == size);
}
public static void main(String[] args) {
Queue q = new Queue(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
while (!q.isEmpty()) {
q.dequeue();
}
}
}
程序的输出如下：
10 has been enqueued into the queue.
20 has been enqueued into the queue.
30 has been enqueued into the queue.
10 has been dequeued from the queue.
20 has been dequeued from the queue.
30 has been dequeued from the queue.
2. 使用链表来实现队列
使用链表也可以实现队列。我们可以使用一个链表来保存队列中的元素，并在链表的尾部插入新元素。队首的元素保存在链表的头部，并且当我们需要删除一个元素时，只需要将头部的节点删除即可。
下面是用链表实现的队列代码：
public class Queue {
Node front, rear;
// 链表节点
class Node {
int data; // 节点的值
Node next; // 下一个节点
Node(int x) {
this.data = x;
this.next = null;
}
}
// 将x插入队尾
public void enqueue(int x) {
Node node = new Node(x);
if (front == null) {
front = node;
} else {
rear.next = node;
}
rear = node;
System.out.println(x + " has been enqueued into the queue.");
}
// 从队首删除元素
public int dequeue() {
if (front == null) {
System.out.println("Queue is empty!");
return -1;
} else {
int x = front.data;
front = front.next;
System.out.println(x + " has been dequeued from the queue.");
return x;
}
}
// 判断队列是否为空
boolean isEmpty() {
return (front == null);
}
public static void main(String[] args) {
Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);