java中的栈和队列
时间: 2023-12-06 17:39:49 浏览: 42
在 Java 中,栈和队列都是常见的数据结构,可以通过使用内置的类或自定义类来实现。
栈是一种后进先出(LIFO)的数据结构,类似于一堆盘子,只能从最上面取盘子。Java 中的 Stack 类就是一个典型的栈实现,它提供了 push()、pop()、peek() 等方法。例如:
```java
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 输出 3
System.out.println(stack.peek()); // 输出 2
```
队列是一种先进先出(FIFO)的数据结构,类似于排队等候。Java 中的 Queue 接口提供了队列的基本操作,例如 offer()、poll()、peek() 等方法。LinkedList 类实现了 Queue 接口,可以用来实现队列。例如:
```java
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 输出 1
System.out.println(queue.peek()); // 输出 2
```
除了内置的类,我们也可以自定义栈和队列的实现。例如,使用数组实现栈:
```java
class MyStack {
private int[] arr;
private int top;
public MyStack(int size) {
arr = new int[size];
top = -1;
}
public void push(int val) {
if (top == arr.length - 1) {
throw new RuntimeException("Stack overflow");
}
arr[++top] = val;
}
public int pop() {
if (top == -1) {
throw new RuntimeException("Stack underflow");
}
return arr[top--];
}
public boolean isEmpty() {
return top == -1;
}
}
```
使用链表实现队列:
```java
class MyQueue {
private ListNode head;
private ListNode tail;
public MyQueue() {
head = null;
tail = null;
}
public void offer(int val) {
ListNode node = new ListNode(val);
if (tail == null) {
head = node;
} else {
tail.next = node;
}
tail = node;
}
public int poll() {
if (head == null) {
throw new RuntimeException("Queue underflow");
}
int val = head.val;
head = head.next;
if (head == null) {
tail = null;
}
return val;
}
public boolean isEmpty() {
return head == null;
}
private class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
this.next = null;
}
}
}
```