[STUDY] 자료구조_스택과 큐

👩🏻‍💻 스터디에서 진행하는 Data Structure 개념 공부입니다.

1. 스택 (STACK)

🥉 LIFO (Last In First Out) / 후입선출 구조

일단 개념적으로 봤을때 스택(stack)의 의미는 쌓아 올린다는 뜻이다. 즉, 자료구조 중 스택은 자료를 하나씩 쌓아 올리고 제거를 위해서 위에서부터 하나씩 제거해야한다.

특징

• 자료가 하나씩 쌓이는 형태의 자료구조이다.
• 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
• 가장 위에 있는 자료는 가장 최근에 들어온 자료이다.
• 자료를 삭제하기 위해선 가장 위(최근) 자료부터 삭제가 가능하다.

사용

스택에서는 자료를 삽입하는 연산을 push 라고 하며 삭제하는 연산은 pop이라고 지칭된다.

Java 코드

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.pop();
stack.clear(); // stack의 전체 값 제거
stack.peek(); // stack의 가장 상단의 값 출력

Python 코드

List를 이용한 stack 구현

n_list = [1,2,3]
n_list.append(1)

출력 : [1,2,3,1]

n_list = [1,2,3]
n_list.pop()

출력 : [1,2]

활용 예시

• 뒤로가기
• 역순 문자열 생성
• 실행 취소
• 후위 표기법 계산
• 수식의 괄호 검사

2. 큐 (Queue)

🥇 FIFO (First In First Out) / 선입선출 구조

Queue의 개념은 줄, 줄을 서서 기다리는 것이며 우리가 보통 알바를 할때 선입선출, 먼저 들어온것이 먼저 나가야 하는 형태를 말하고 있다.

특징

• 정해진 한쪽 방향으로 자료가 삽입이 되고 삽입되는 방향의 반대쪽에서 삭제 작업이 이루어진다.
• 삽입연산이 수행되는 곳을 rear, 삭제연산이 수행되는 곳을 front 라고 한다.
• 삽입연산을 인큐(enQueue) 라고 하며 삭제연산을 디큐(deQueue)라고 한다.
• 큐에 가장 먼저들어왔던 원소가 첫번째 원소가 되고 가장 늦게들어온 원소가 마지막 원소가 된다고 볼 수 있다.

Java 코드

Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 값 추가
queue.offer(2);     
queue.offer(3);     
queue.poll(); // queue에 첫번째 값을 반환하고 제거, 비어있다면 null
queue.remove(); // 값 제거
queue.clear(); // queue 초기화
queue.peek(); // queue의 첫번째 값 참조

Python 코드

List를 이용한 Queue 구현

n_list = [4, 5, 6]
n_list.append(7)
n_list.append(8)

출력 : [4, 5, 6, 7, 8]

queue.pop(0) # pop(0)을 이용하여 deQueue를 구현
>>> 4
출력 : [5, 6, 7, 8]

활용 예시

• 우선순위가 필요한 서비스
• 은행 업무
• 프로세스 관리
• 너비 우선 탐색
• 캐시(Cache) 구현

서비스에서 캐싱을 구현하면서 Queue와 같이 캐싱 전략을 설계하여 구현하였었는데, 이는 해당 서비스에서 알맞은 전략을 통해 구현해야만 서비스에 오류나 데이터의 불일치성을 최소화 할 수 있다.