栈与队列相关知识（二）

目录

Java中栈（Stack）

一. 常用方法

1.push(E item)

2.pop()

3.peek()

4.empty()

二. 常用方法扩展

1. search(Object o)

2. clone()

3. contains(Object o)

4. size()

5. toArray()

Java中队列（Queue）

一.常用方法（以LinkedList实现Queue为例）

1.add(E e)

2.offer(E e)

3.remove()

4.poll()

5.element()

6.peek()

二. 常用方法扩展（以LinkedList实现Queue为例，同时包括一些Queue接口实现类共有的特性）

1. size()

2. contains(Object o)

3. toArray()

4. clear()

5. iterator()

6. remove(Object o)

7. retainAll(Collection c)

Java中栈（Stack）

一. 常用方法

1.push(E item)

• 功能：将元素item压入栈顶。

• 示例：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);

2.pop()

• 功能：移除并返回栈顶元素。如果栈为空，会抛出EmptyStackException异常。

• 示例：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int topElement = stack.pop();// 返回2

3.peek()

• 功能：返回栈顶元素，但不移除它。如果栈为空，会抛出EmptyStackException异常。

• 示例：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.peek();// 返回2，栈不变

4.empty()

• 功能：检查栈是否为空，为空返回true，否则返回false。

• 示例：

Stack<Integer> stack = new Stack<>();
boolean isEmpty = stack.empty();// true
stack.push(1);
isEmpty = stack.empty();// false

二. 常用方法扩展

1. search(Object o)

• 功能：返回对象o在栈中的位置，从栈顶开始计数，栈顶元素位置为1。如果对象o不在栈中，则返回 - 1。

• 示例：

Stack<String> stack = new Stack<>();
stack.push("a");
stack.push("b");
stack.push("c");
int position = stack.search("b");// 返回2
int notInStack = stack.search("d");// 返回 - 1

2. clone()

• 功能：创建并返回此栈的副本。克隆后的栈是一个包含相同元素的新栈，但它们在内存中是独立的对象。

• 示例：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
Stack<Integer> clonedStack = (Stack<Integer>) stack.clone();

3. contains(Object o)

• 功能：判断栈中是否包含指定元素o，如果包含则返回true，否则返回false。

• 示例：

Stack<String> stack = new Stack<>();
stack.push("hello");
boolean hasHello = stack.contains("hello");// 返回true
boolean hasWorld = stack.contains("world");// 返回false

4. size()

• 功能：返回栈中元素的个数。

• 示例：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int size = stack.size();// 返回2

5. toArray()

• 功能：返回一个包含栈中所有元素的数组。数组的顺序与栈中元素的顺序相同，从栈顶到栈底。

• 示例：

Stack<String> stack = new Stack<>();
stack.push("a");
stack.push("b");
Object[] array = stack.toArray();
String[] stringArray = stack.toArray(new String[0]);

Java中队列（Queue）

一.常用方法（以LinkedList实现Queue为例）

1.add(E e)

• 功能：将指定元素e插入队列。如果队列已满（对于有界队列），则抛出IllegalStateException异常。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);

2.offer(E e)

• 功能：将指定元素e插入队列。如果队列已满（对于有界队列），则返回false，与add方法类似但处理满队列的方式不同。

• 示例：

Queue<Integer> queue = new LinkedList<>();
boolean success = queue.offer(1);
success = queue.offer(2);

3.remove()

• 功能：移除并返回队列的头元素。如果队列为空，则抛出NoSuchElementException异常。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
int head = queue.remove();// 返回1

4.poll()

• 功能：移除并返回队列的头元素。如果队列为空，则返回null，与remove方法类似但处理空队列的方式不同。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
int head = queue.poll();// 返回1

5.element()

• 功能：返回队列的头元素，但不移除它。如果队列为空，则抛出NoSuchElementException异常。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
int head = queue.element();// 返回1，队列不变

6.peek()

• 功能：返回队列的头元素，但不移除它。如果队列为空，则返回null，与element方法类似但处理空队列的方式不同。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
int head = queue.peek();// 返回1，队列不变

二. 常用方法扩展（以LinkedList实现Queue为例，同时包括一些Queue接口实现类共有的特性）

1. size()

• 功能：返回队列中元素的个数。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
int size = queue.size();// 返回2

2. contains(Object o)

• 功能：判断队列中是否包含指定元素o，如果包含则返回true，否则返回false。

• 示例：

Queue<String> queue = new LinkedList<>();
queue.add("hello");
boolean hasHello = queue.contains("hello");// 返回true
boolean hasWorld = queue.contains("world");// 返回false

3. toArray()

• 功能：返回一个包含队列中所有元素的数组。数组的顺序与队列中元素的顺序相同，从队头到队尾。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
Object[] array = queue.toArray();
Integer[] intArray = queue.toArray(new Integer[0]);

4. clear()

• 功能：移除队列中的所有元素，将队列清空。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.clear();
boolean isEmpty = queue.isEmpty();// 返回true

5. iterator()

• 功能：返回一个迭代器，用于遍历队列中的元素。迭代器按照从队头到队尾的顺序访问元素。

• 示例：

Queue<String> queue = new LinkedList<>();
queue.add("a");
queue.add("b");
Iterator<String> iterator = queue.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

6. remove(Object o)

• 功能：从队列中移除指定元素o的第一次出现（如果存在）。如果队列为空或者元素不存在，则返回false；如果成功移除元素，则返回true。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
boolean removed = queue.remove(1);

7. retainAll(Collection<?> c)

• 功能：仅保留队列中包含在指定集合c中的元素。如果队列为空或者指定集合c为空，则不做任何操作。如果队列发生了改变（即有元素被移除），则返回true；否则返回false。

• 示例：

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
Collection<Integer> collection = Arrays.asList(2, 3);
boolean changed = queue.retainAll(collection);