Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] ArrayDeque

πŸ“¦[DS,Algorithm] ArrayDeque
DataStructure Algorithm

1️⃣ ArrayDeque.

Javaμ—μ„œ β€˜ArrayDequeβ€˜ λŠ” β€˜java.utilβ€˜ νŒ¨ν‚€μ§€μ— μ†ν•˜λŠ” 클래슀이며, 큐(Queue)와 덱(Deque)의 κΈ°λŠ₯을 λͺ¨λ‘ μ§€μ›ν•˜λŠ” λ°°μ—΄ 기반의 자료 κ΅¬μ‘°μž…λ‹ˆλ‹€.

β€˜ArrayDequeβ€˜ λŠ” β€˜Dequeβ€˜ μΈν„°νŽ˜μ΄μŠ€λ₯Ό κ΅¬ν˜„ν•˜λ©°, κ·ΈκΈ°κ°€ 가변적인 배열을 μ‚¬μš©ν•˜μ—¬ μš”μ†Œλ₯Ό μ €μž₯ν•©λ‹ˆλ‹€.

2️⃣ μ£Όμš” νŠΉμ§•.

  • 이쀑 끝 큐 : μ–‘μͺ½ λμ—μ„œ μš”μ†Œλ₯Ό μΆ”κ°€ν•˜κ³  μ œκ±°ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

  • 크기 μ‘°μ • : ν•„μš”μ— 따라 λ‚΄λΆ€ λ°°μ—΄μ˜ 크기λ₯Ό μžλ™μœΌλ‘œ μ‘°μ •ν•©λ‹ˆλ‹€.

  • μŠ€νƒ 및 큐둜 μ‚¬μš© κ°€λŠ₯ : β€˜ArrayDequeβ€˜ λŠ” μŠ€νƒ(LIFO, Last In First Out)κ³Ό 큐(FIFO, First In First Out) λͺ¨λ‘λ‘œ μ‚¬μš©ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

  • 비동기적 : β€˜ArrayDequeβ€˜ λŠ” λΉ„λ™κΈ°μ μœΌλ‘œ λ™μž‘ν•˜λ―€λ‘œ λ™κΈ°ν™”λœ ν™˜κ²½μ—μ„œ μ•ˆμ „ν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

3️⃣ μ£Όμš” λ©”μ„œλ“œ.

μ‚½μž… μ—°μ‚°.

  • β€˜addFirst(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 μ•žμͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

  • β€˜addLast(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 λ’€μͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

  • β€˜offerFirst(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 μ•žμͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

  • β€˜offerLast(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 λ’€μͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

μ‚­μ œ μ—°μ‚°.

  • β€˜removeFirst()’ : 덱의 μ•žμͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜removeLast()’ : 덱의 λ’€μͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜pollFirst()’ : 덱의 μ•žμͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜pollLast()’ : 덱의 λ’€μͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

쑰회 μ—°μ‚°.

  • β€˜getFirst()’ : 덱의 μ•žμͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜getLast()’ : 덱의 λ’€μͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜peekFirst()’ : 덱의 μ•žμͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜peekLast()’ : 덱의 λ’€μͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

μŠ€νƒ μ—°μ‚°.

  • β€˜push(E e)’ : μŠ€νƒμ˜ 맨 μœ„μ— μš”μ†Œλ₯Ό μΆ”κ°€ν•©λ‹ˆλ‹€.(LIFO, Last In First Out)

  • β€˜pop(E e)’ : μŠ€νƒμ˜ 맨 μœ„μ— μžˆλŠ” μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.(LIFO, Last In First Out)

4️⃣ μ‹œκ°„ λ³΅μž‘λ„.

  • μ‚½μž…κ³Ό μ‚­μ œ μ—°μ‚° : β€˜addFirstβ€˜, β€˜addLastβ€˜, β€˜removeFirstβ€˜, β€˜removeLastβ€˜, β€˜offerFirstβ€˜, β€˜offerLastβ€˜, β€˜pollFirstβ€˜, β€˜pollLastβ€˜, λ“±μ˜ 연산은 ν‰κ· μ μœΌλ‘œ O(1)μž…λ‹ˆλ‹€.

  • 쑰회 μ—°μ‚° : β€˜getFirstβ€˜, β€˜getLastβ€˜, β€˜peekFirstβ€˜, β€˜peekLastβ€˜ λ“±μ˜ 연산은 O(1)μž…λ‹ˆλ‹€.

  • 크기 μ‘°μ • : λ² μ—΄μ˜ 크기가 가득 찼을 λ•Œ 크기λ₯Ό 두 배둜 λŠ˜λ¦¬κ±°λ‚˜ μ€„μ΄λŠ” μž‘μ—…μ€ O(n) μ‹œκ°„μ΄ κ±Έλ¦¬μ§€λ§Œ, μ΄λŠ” λ“œλ¬Όκ²Œ λ°œμƒν•˜λ―€λ‘œ ν‰κ· μ μœΌλ‘œλŠ” O(1)둜 κ°„μ£Όν•©λ‹ˆλ‹€. (amortized O(1)).

5️⃣ 예제 μ½”λ“œ

μ•„λž˜μ˜ μ½”λ“œλŠ” β€˜ArrayDequeβ€˜ λ₯Ό μ‚¬μš©ν•œ 예제 μ½”λ“œμž…λ‹ˆλ‹€.

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {

	public static void main(String[] args) {
		// ArrayDeque둜 Deque 생성
		Deque<Integer> deque = new ArrayDeque<>();

		// μš”μ†Œ μ‚½μž…
		System.out.println("=== μš”μ†Œ μ‚½μž… ===");
		deque.addFirst(1);
		deque.addLast(2);
		deque.offerFirst(0);
		deque.offerLast(3);
		System.out.println(deque);
		System.out.println();

		// μš”μ†Œ 쑰회
		System.out.println("=== μš”μ†Œ 쑰회 ===");
		System.out.println("First element: " + deque.getFirst());
		System.out.println("Last element: " + deque.getLast());
		System.out.println("Peek first element: " + deque.peekFirst());
		System.out.println("Peek last element: " + deque.peekLast());
		System.out.println();

		// μš”μ†Œ μ‚­μ œ
		System.out.println("=== μš”μ†Œ μ‚­μ œ ===");
		System.out.println("Removed first element: " + deque.removeFirst());
		System.out.println("Removed last element: " + deque.removeLast());
		System.out.println("Poll first element: " + deque.pollFirst());
		System.out.println("Poll last element: " + deque.pollLast());
		System.out.println();

		// 덱의 크기와 λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€ 확인
		System.out.println("=== 덱의 크기와 λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€ 확인 ===");
		System.out.println("Deque size: " + deque.size());
		System.out.println("Is deque empty? " + deque.isEmpty());
		System.out.println();
		
		// μŠ€νƒ μ—°μ‚°
		System.out.println("=== μŠ€νƒ μ—°μ‚° ===");
		deque.push(4);
		System.out.println("Pushed element: " + deque.peekFirst());
		System.out.println("Popped element: " + deque.pop());
	}
}

/*
=== 좜λ ₯ ===
=== μš”μ†Œ μ‚½μž… ===
[0, 1, 2, 3]

=== μš”μ†Œ 쑰회 ===
First element: 0
Last element: 3
Peek first element: 0
Peek last element: 3

=== μš”μ†Œ μ‚­μ œ ===
Removed first element: 0
Removed last element: 3
Poll first element: 1
Poll last element: 2

=== 덱의 크기와 λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€ 확인 ===
Deque size: 0
Is deque empty? true

=== μŠ€νƒ μ—°μ‚° ===
Pushed element: 4
Popped element: 4
*/