스택 Stack, 큐 Queue, 덱 Deque

스택 Stack

• 한쪽 끝에서 자료를 넣거나 뺄 수 있는, 데이터를 제한적으로 접근할 수 있는 구조
  • 후입 선출  LIFO  Last In First Out
  • 깊이 우선 탐색  DFS  Depth First Search
    • 백트래킹 종류의 알고리즘에 효과적이다
    • 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 비슷하기 때문
  • 사용 예 )  브라우저의 뒤로가기,  실행 취소 (Ctrl + z),  재귀 함수,  역순 문자열 (문자열 거꾸로 뒤집기)
  • 스택의 자료구조는 삽입과 삭제시에 O(1),  탐색에는 O(n)의 시간복잡도를 가지게 된

큐 Queue

• 한 쪽에서는 데이터 삽입, 다른 한 쪽에서는 데이터의 삭제만 가능
  
  • 선입선출  FIFO  First In First Out  ( 먼저 삽입된 데이터가 가정 먼저 제거된다 )
    • 작업 스케줄링, 프린터 대기열, 너비 우선 탐색 (BFS), 데이터 버퍼에 사용된다
    • 실생활에서는 재료의 선입선출(유통기한이 오래된 것을 가장 앞쪽에 배치), 식당의 줄서기 등이 대표적인 예

---

덱  Deque   (Double-ended Queue)   

• 큐 2개를 겹쳐놓은것과 같기 때문에 Double ended Queue 라고 부르며 Deque라는 축약형으로 부른다
• 양쪽에서 데이터의 입출력이 모두 가능하다
• front(가장 앞)와 rear(가장 뒤)라는 포인터가 있다
• 데이터의 삽입과 삭제에 O(1) 시간복잡도를 가진다

---

스택  Stack	덱  Deque
Java에서 기본으로 제공하는 클래스	스레드 안정성 보장 X
스레드 안정성 보장	양쪽 끝에서 삽입과 삭제가 모두 가능
성능이 다소 떨어진다	스택과 큐의 기능을 모두 포함
	다양한 상황에서 유연하게 사용 가능

---

Java에서 Stack 구현 (1)      Stack

import java.util.Stack;

 

장점

- Java 기본 제공 스택 클래스

- 스레드 안정성 보장 (동기화 메서드 사용)

 

단점

- 성능이 다소 떨어질 수 있다 (동기화 메서드 사용으로 인한 오버헤드)

- Vector 클래스를 상속받아 구현되어 있어, 스택 외의 불필요한 메서드가 포함된다

 

스레드 안정성

 

- 여러 스레드가 동시에 스택에 접근하더라도 데이터의 일관성과 무결성을 유지할 수 있다.

- 한 번에 하나의 스레드만 접근할 수 있도록 보장한다.

 

스레드

- 프로그램 내에서 동시에 실행될 수 있는 작업의 단위

- 여러 스레드를 사용하면 프로그램이 동시에 여러 작업을 수행할 수 있다  =>  멀티스레딩

성능 오버헤드

 

- 동기화 메서드는 한 번에 하나의 스레드만 접근할 수 있도록 보장하기 때문에, 멀티스레드 환경에서 성능이 저하될 수 있다.

- 동기화 메서드를 호출할 때마다 동기화 오버헤드가 발생하여, 단일 스레드 환경에서는 불필요한 성능 저하가 발생할 수 있다.

 

오버헤드

- 추가적인 작업이나 비용

- 프로그램이 특정 작업을 수행할 때, 그 작업을 처리하기 위해 필요한 추가적인 리소스나 시간

Vector 클래스 상속, 구현

 

- 불필요한 메서드와 데이터 구조가 포함되어 메모리 사용량이 증가할 수 있다

- 스택은 LIFO 구조를 따르지만, Vector는 동적 배열로 구현되어 있어, 스택의 특성과 맞지 않는 메서드가 포함될 수 있다

push()

pop()

peek()

size()

isEmpty()

---

Java에서 Stack 구현 (2)     ArrayDeque

 

 

장점 

- 덱 인터페이스 구현한 클래스

- 성능이 좋다

- 메모리 재할당이 적어 효율적

 

단점

- 중간 삽입/삭제 작업이 느리다 (배열 복사 필요)

- 배열의 초기 크기나 동적 크기 조정에 따라 성능 변동 가능

 

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

Deque<Integer> stack = new ArrayDeque<>();

 

ArrayDeque  ( Array Double Ended Queue )

일반적으로 Last-In, First-Out을 구현하여 배열의 끝에서 데이터를 추가하는 큐와 다르게,

ArrayDeque는 큐의 양 끝에 데이터를 용이하게 추가하고 제거할 수 있다.

Java에서 Deque 인터페이스는 크기를 조절할 수 있는 배열에 요소를 저장하는데, 

ArrayDeque이 이 Deque 인터페이스를 구현한다. 

크기에 제한도 없고, 배열의 양 끝에 데이터를 추가하고 제거하는 연산을 O(1) 시간복잡도에 제공한다.

---

Java에서 덱 구현

 

장점 

- 덱 인터페이스를 구현한 클래스

- 성능이 좋다 (비동기화 메서드 사용)

- 양방향 연결 리스트로 구현되어 있어, 삽입과 삭제가 빠르다

 

단점

- 스레드 안전성이 보장되지 않는다 (멀티스레드 환경에서 사용시 주의 필요)

- 메모리 사용량이 상대적으로 많을 수 있다 (노드 객체를 위한 추가 메모리 필요)

 

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new LinkedList<>();

        stack.push(1);
        stack.push(2);

        System.out.println(stack.pop());    
        System.out.println(stack.peek());   
        System.out.println(stack.size());
        System.out.println(stack.isEmpty());
    }
}

 

출력값

 

 

pop()

맨 위에 있는 요소를 제거하면서 반환한다.

 

peek()

맨 위에 있는 요소를 제거하지 않고 반환만 한다.

 

 

---

getFirst()

getLast()

removeFirst()

removeLast()

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        
        Deque<Integer> deque = new ArrayDeque<>();
        System.out.println(deque);

        deque.add(1);
        deque.add(2);
        deque.add(3);
        deque.add(4);
        deque.add(5);
        System.out.println(deque);

        System.out.println(deque.getFirst());  // 제거X,  출력O
        System.out.println(deque.getLast());  // 제거X,  출력O
        System.out.println(deque);

        System.out.println(deque.removeFirst());  // 제거O,  출력O
        System.out.println(deque);

        System.out.println(deque.removeLast());  // 제거O,  출력O
        System.out.println(deque);

        System.out.println(deque.size());
        System.out.println(deque.isEmpty());
    }
}

---

ArrayDeque  <=  Deque

LinkedList  <=  List

ArrayList  <=  List   스프링 목록조회 등

 

mybatis에서 arraylist 쓰는 이유를 설명해보세요

 

스택/큐 연산에서는 ArrayDeque 최적

양방향 삽입,제거 ArrayDeque 최적  LinkedList 보통  ArrayList  별로

중간 삽입,제거  ArrayDeque 중간  LinkedList 최적  ArrayList  별로

	ArrayDeque	LinkedList	ArrayList
스택/큐	Good	Normal	Bad
양방향 삽입/제거	Good	Normal	Bad
중간 삽입/제거	Normal	Good	Bad
인덱스에 의한 임의접근	지원X	Bad	Good
메모리효율	Good	Bad	Great

 

인덱스 임의접근 필요한 스프링 프로젝트에서는 ArrayList 쓰는 것이 좋다

 

---

기능	Stack	ArrayDeque	LinkedList	ArrayList	return
요소 추가	push(E item)	push(E e) addFirst(E e)	push(E e) addFirst(E e)	add(int index, E element)	추가된 요소 (E)
요소 제거 및 반환	pop()	removeFirst() pollFirst()	removeFirst() pollFirst()	remove(int index)	제거된 요소 (E)
요소 확인 (제거X)	peek()	getFirst() peekFirst()	getFirst() peekFirst()	get(int index)	맨 위의 요소 (E)
스택이 비었는지 확인	isEmpty()	isEmpty()	isEmpty()	isEmpty()	true |  false
특정 요소 위치 찾기	search(Object o)	해당 없음	indexOf(Object o)	indexOf(Object o)	요소의 위치 (없으면 -1)
크기 확인	size()	size()	size()	size()	크기(길이)

 

 

 

 

 

 

 

 

---

refer to

메가스터디아이티 이광호쌤

https://velog.io/@sisofiy626/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2.-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue-%EB%8D%B1Deque