[자료구조] 선형 구조 - 스택(Stack), 큐(Queue), 덱(Deque)

스택

입출력이 한 방향에서만 발생하는 구조

출력 시 가장 최근 입력값(top에 위치)을 꺼냄 (FILO, First-in-last-out)

 

ex) 갑(곽) 휴지

 

 

 

• 시간복잡도(O)

삽입, 삭제(pop) 시 top 값만 추가, 삭제하면 됨 (추가 연산 없음) => O(1)

특정 값 삭제, 검색 시 위에서부터 순차적으로 탐색해야 함 => O(N)

 

 

 

• Stack 클래스 메소드

push() : top에 데이터 추가

pop() : top 데이터 삭제

peek() : top 데이터 조회

empty() : 스택 비어있을 때 true, 아니면 false 출력 

search() : 데이터 위치 조회 (1부터 시작)

 

 

 

• 장단점

장점 : top을 통한 데이터 접근, 삽입, 삭제 용이

단점 : 크기 고정 후에야 사용 가능 (=> 배열 대신 LinkedList로 구현 시 보완됨)

 

 

 

• 활용

실행 취소, 웹페이지 뒤로 가기, 수식 괄호 검사, 역순 문자열 만들기

 

 

 

 

큐

입출력이 각각 다른 방향에서 발생하는 구조 => 맨 뒤에서 입력(rear), 맨 앞에서 출력(front)

입력 순서대로 출력됨 (FIFO, First-in-first-out)

 

ex) 매점에 일렬로 선 줄

 

 

 

• 선형 큐

rear 값이 n-1(마지막 인덱스 값)일 때 꽉 찬 배열으로 인식

 

삽입, 삭제 시 각각 rear, front 값 증가

=> 여러 번 삽입, 삭제 반복시 rear은 마지막 인덱스 값에 도달하고, 이때 배열에 빈 공간 있더라도 full한 것으로 인식됨

=> 비효율적

 

 

 

=> 메모리 낭비 보완

• 원형 큐

맨 앞, 뒤가 연결돼있어 삭제된 공간도 다시 사용 가능

 

 

 

공백 상태 : front == rear % (큐 최대 크기)

포화 상태 : front == (rear+1) % (큐 최대 크기) => 공백 상태와 구별하기 위해 하나의 공간은 무조건 비움

 

 

 

• 시간복잡도(O)

삽입, 삭제(poll) 시 추가 연산 없이 각각 rear, front에 가장 가까운 값을 삽입, 삭제함 => O(1)

특정값, 검색 시 순차적으로 탐색해야 함 => O(N)

 

 

 

• Queue 클래스 메소드

add() : rear 값 추가 (실패 시 IllegalStateException)

offer() : rear 값 추가 (실패 시 false 반환)

element() : front 값 반환 (비어있으면 NoSuchElementException)

peek() : front 값 반환 (비어있으면 null 반환)

remove() : front 값 삭제 (비어있으면 NoSuchElementException)

poll() : front 값 삭제 (비어있으면 null 반환)

 

 

 

• 활용

대기 순서 처리, BFS 알고리즘, 캐시(Cache) 구현

 

 

 

 

덱 (Deque)

양쪽에서 입출력 가능한 자료구조

 

 

• 시간복잡도(O)

삽입, 삭제 시 양 끝에 값만 추가, 삭제하면 됨 (추가 연산 없음) => O(1)

인덱스 통해 탐색 => O(1)

 

 

 

• Deque 클래스 메소드

addFirst() : front 값 추가 (실패 시 IllegalStateException)

offerFirst() : front 값 추가 (실패 시 false 반환)

addLast(), add() : rear 값 추가 (실패 시 IllegalStateException)

offerLast(), offer() : rear 값 추가 (실패 시 false 반환)

 

removeFirst(), remove() : front 값 반환 (비어있으면 NoSuchElementException)

pollFirst(), poll() : front 값 반환 (비어있으면 null 반환)

removeLast() : rear 값 삭제 (비어있으면 NoSuchElementException)

pollLast() : rear값 삭제 (비어있으면 null 반환)

 

getFirst() : front 값 삭제 없이 반환 (비어있으면 NoSuchElementException)

peekFirst(), peek() : front 값 삭제 없이 반환 (비어있으면 null 반환)

getLast() : rear 값 삭제 없이 반환 (비어있으면 NoSuchElementException)

peekLast() : rear 값 삭제 없이 반환 (비어있으면 null 반환)

 

 

 

• 활용

데이터를 양 쪽에 삽입, 삭제해야 하는 경우, 데이터 크기가 가변적인 경우

 

 

 

 

 

 

 

출처

https://devuna.tistory.com/22

https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque

https://yjg-lab.tistory.com/115

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