Home > Algorithm > 2024 > ๐Ÿ“ฆ[DS,Algorithm] Deque์—์„œ์˜ front์™€ rear์˜ ๋ณ€ํ™”.

๐Ÿ“ฆ[DS,Algorithm] Deque์—์„œ์˜ front์™€ rear์˜ ๋ณ€ํ™”.
DataStructure Algorithm

๐Ÿงจ ์‹œ๋ฐœ์ .

Deque์„ ๊ณต๋ถ€ํ•˜๋˜ ์ค‘ ๋™์ ์œผ๋กœ ๋ณ€ํ•˜๋Š” front์™€ rear๊ฐ€ ๊ทผ๋ณธ์ ์œผ๋กœ ์–ด๋–ป๊ฒŒ ๋™์ž‘ํ•˜๋Š”์ง€ ๊ถ๊ธˆํ•ด์กŒ์Šต๋‹ˆ๋‹ค.

์ด๊ฒƒ์„ ์•Œ๊ฒŒ๋˜๋ฉด ์ •ํ™•ํ•˜๊ฒŒ Deque์˜ addFirst, addLast, removeFirst, removeLast ์‹œ front์™€ rear๊ฐ€ ์–ด๋””์— ์œ„์น˜ํ•˜๋Š”์ง€ ์•Œ ์ˆ˜ ์žˆ๊ณ  Deque์˜ ์›๋ฆฌ๋ฅผ ์ดํ•ด ํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์•˜์Šต๋‹ˆ๋‹ค.

1๏ธโƒฃ Deque์˜ front์™€ rear์˜ ์œ„์น˜๋Š” ๋ณ€ํ•  ์ˆ˜ ์žˆ๋‚˜์š”? ๐Ÿค”

โ€˜Dequeโ€˜ (Double Ended Queue)์—์„œ โ€˜frontโ€˜ ์™€ โ€˜rearโ€˜ ์˜ ์œ„์น˜๋Š” ๋ณ€ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

โ€˜Dequeโ€˜ ๋Š” ์–‘์ชฝ ๋์—์„œ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๊ฐ€ ๋ชจ๋‘ ๊ฐ€๋Šฅํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ด๊ธฐ ๋•Œ๋ฌธ์—, โ€˜frontโ€˜ ์™€ โ€˜rearโ€˜ ์˜ ์œ„์น˜๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ์‚ฝ์ž…๋˜๊ฑฐ๋‚˜ ์ œ๊ฑฐ๋  ๋•Œ๋งˆ๋‹ค ๋ณ€ํ•ฉ๋‹ˆ๋‹ค.

2๏ธโƒฃ Deque์—์„œ์˜ front์™€ rear์˜ ๋ณ€ํ™”. ๐Ÿคฉ

1๏ธโƒฃ ์‚ฝ์ž… ์—ฐ์‚ฐ (โ€˜addFirstโ€˜ ์™€ โ€˜addLastโ€˜)

  • โ€˜addFirstโ€™ : ์š”์†Œ๋ฅผ ๋ฑ์˜ ์•ž์ชฝ์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜frontโ€˜ ์œ„์น˜๊ฐ€ ๋ฐ”๋€๋‹ˆ๋‹ค.
  • โ€˜addLastโ€™ : ์š”์†Œ๋ฅผ ๋ฑ์˜ ๋’ค์ชฝ์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜rearโ€˜ ์œ„์น˜๊ฐ€ ๋ฐ”๋€๋‹ˆ๋‹ค.

2๏ธโƒฃ ์‚ญ์ œ ์—ฐ์‚ฐ (โ€˜removeFirstโ€˜ ์™€ โ€˜removeLastโ€˜)

  • โ€˜removeFirstโ€™ : ๋ฑ์˜ ์•ž์ชฝ์—์„œ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜frontโ€˜ ์œ„์น˜๊ฐ€ ๋ฐ”๋€๋‹ˆ๋‹ค.
  • โ€˜removeLastโ€™ : ๋ฑ์˜ ๋’ค์ชฝ์—์„œ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜rearโ€˜ ์œ„์น˜๊ฐ€ ๋ฐ”๋€๋‹ˆ๋‹ค.

3๏ธโƒฃ ์˜ˆ์ œ ์ฝ”๋“œ.

์•„๋ž˜๋Š” โ€˜Dequeโ€™ ์˜ โ€˜LinkedListโ€™ ๊ตฌํ˜„์„ ์‚ฌ์šฉํ•˜์—ฌ โ€˜frontโ€™ ์™€ โ€˜rearโ€™ ์˜ ๋ณ€ํ™”๋ฅผ ๋ณด์—ฌ์ฃผ๋Š” ์˜ˆ์ œ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค.

import java.util.Deque;
import java.util.LinkedList;

public class DequeExample {
	public static void main(String[] args) {
		Deque<String> deque = new LinkedList<>();

		// ์š”์†Œ๋ฅผ ๋ฑ์˜ ์•ž๊ณผ ๋’ค์— ์ถ”๊ฐ€
		deque.addFirst("A"); // front: A
		deque.addLast("B"); // rear: B
		deque.addFirst("C"); // front: C, rear: B
		deque.addLast("D"); // rear: D

		System.out.println("Initial Deque: " + deque); // ์ถœ๋ ฅ : [C,A,B,D]

		// ์•ž์ชฝ์—์„œ ์š”์†Œ ์ œ๊ฑฐ
		System.out.println("Removed from front: " + deque.removeFirst()); // ์ถœ๋ ฅ: C

		// ๋’ค์ชฝ์—์„œ ์š”์†Œ ์ œ๊ฑฐ
		System.out.println("Removed from rear: " + deque.removeLast()); // ์ถœ๋ ฅ: D

		System.out.println("Deque after removals: " + deque); // ์ถœ๋ ฅ: [A, B]

		// ๋ฑ์˜ ์•ž์ชฝ๊ณผ ๋’ค์ชฝ์—์„œ ์š”์†Œ ํ™•์ธ
		System.out.println("Front element: " + deque.getFirst()); // ์ถœ๋ ฅ: A
		System.out.println("Rear element: " + deque.getLast()); // ์ถœ๋ ฅ: B
	}
}

๐Ÿ‘‰ ์„ค๋ช….

1๏ธโƒฃ ์‚ฝ์ž… ์—ฐ์‚ฐ.

  • โ€˜deque.addFirst(โ€œAโ€)โ€™ : โ€œAโ€๋ฅผ ๋ฑ์˜ ์•ž์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.

  • โ€˜deque.addLast(โ€œBโ€)โ€™ : โ€œBโ€๋ฅผ ๋ฑ์˜ ๋’ค์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.

  • โ€˜deque.addFirst(โ€œCโ€)โ€™ : โ€œCโ€๋ฅผ ๋ฑ์˜ ์•ž์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.

  • โ€˜deque.addLast(โ€œDโ€)โ€™ : โ€œDโ€๋ฅผ ๋ฑ์˜ ๋’ค์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.

์ด ์—ฐ์‚ฐ๋“ค์€ โ€˜frontโ€™ ์™€ โ€˜rearโ€™ ์˜ ์œ„์น˜๋ฅผ ์—…๋ฐ์ดํŠธํ•ฉ๋‹ˆ๋‹ค.

2๏ธโƒฃ ์‚ญ์ œ ์—ฐ์‚ฐ.

  • โ€˜deque.removeFirst()โ€™ : ๋ฑ์˜ ์•ž์ชฝ์—์„œ โ€œCโ€๋ฅผ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค.

  • โ€˜deque.removeLast()โ€™ : ๋ฑ์˜ ๋’ค์ชฝ์—์„œ โ€œDโ€๋ฅผ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค.

์ด ์—ฐ์‚ฐ๋“ค์€ โ€˜frontโ€™ ์™€ โ€˜rearโ€™ ์˜ ์œ„์น˜๋ฅผ ๋‹ค์‹œ ์—…๋ฐ์ดํŠธํ•ฉ๋‹ˆ๋‹ค.

3๏ธโƒฃ ์š”์†Œ ํ™•์ธ.

  • โ€˜deque.getFirst()โ€™ : ๋ฑ์˜ ์•ž์ชฝ ์š”์†Œ๋ฅผ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.

  • โ€˜deque.getLast()โ€™ : ๋ฑ์˜ ๋’ค์ชฝ ์š”์†Œ๋ฅผ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.

์ด ์˜ˆ์‹œ ์ฝ”๋“œ๋Š” โ€˜frontโ€™ ์™€ โ€˜rearโ€™ ๊ฐ€ ๋ฐ์ดํ„ฐ์˜ ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ ์—ฐ์‚ฐ์— ๋”ฐ๋ผ ์–ด๋–ป๊ฒŒ ๋ณ€ํ•˜๋Š”์ง€ ์ž˜ ๋ณด์—ฌ์ค๋‹ˆ๋‹ค.
โ€˜Dequeโ€™ ๋Š” ์ด์ฒ˜๋Ÿผ ์–‘์ชฝ ๋์—์„œ์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ ์—ฐ์‚ฐ์„ ์ง€์›ํ•˜๋ฏ€๋กœ, โ€˜frontโ€™ ์™€ โ€˜rearโ€™ ์˜ ์œ„์น˜๋Š” ๋™์ ์ž…๋‹ˆ๋‹ค.