🤔 목적
컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비 하고자한다.
스택(Stack) 이란?
정의
스택(Stack)은 "쌓다"라는 의미로 데이터를 쌓아 올린 형태의 자료구조 또한 제한적으로 접근할 수 있는 나열구조의 자료구조이다. 접근 방법은 언제나 목록 끝에서만 일어난다. 끝먼저내기 목록(Pushdown lise)라고도 한다.
특징
그림과 같이 꺼내지는 자료는 가장 최근에 push한 자료터 나오게 된다. 이러한 구조를 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO - Last In First Out)로 되어 있다.
스택에 연산은 아래와 같다.
- pop(): 스택에서 가장 위에 있는 항목을 제거한다.
- push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
- peek(): 스택의 가장 위에 있는 항목을 반환한다.
- isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
사용사례
재귀 알고리즘을 사용하는 경우 스택이 유용하다
- 재귀 알고리즘
- 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
- 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야한다.
- 스택은 이런 일련 행위를 직관적으로 가능하게 해준다.
- 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
- 웹 브라우저 방문기록 (뒤로가기)
- 실행취소 (undo)
- 역순 문자열 만들기
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
- Ex) 올바른 괄호 문자열 판단하기
- 후위 표기법 계산
후위 표기법이란? : 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법
컴파일러가 사용하는 것
큐(Queue) 란?
정의
큐(Queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어넣은 데이터가 먼저나오는 선입선출(FIFO)구조로 저장하는 형식을 말한다.
개념
- 전단(front): 큐에서 삭제가 일어나는 곳
- 후단(back,rear): 큐에서 삽입이 일어나는 곳
큐의 연산
- create(): 큐를 생성한다.
- init(): 큐를 초기화한다.
- is_empty(q): 큐가 비어 있는지를 검사한다.
- is_full(q): 큐가 가득 찼는지를 검사한다.
- enqueue(q, e): 큐의 뒤에 요소를 추가한다.
- dequeue(q): 큐의 앞에 있는 요소를 반환한 다음 삭제한다.
- peek(q): 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.
종류
- 선형 큐
선형 큐는 Front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열에 끝에 도달하게 되고 배열의 앞부분이 비어있더라도 더 이상 삽입하지 못한다는 단점이 있다, 따라서 후단에 더 이상 삽입할 공간이 없으면 모든 요소들을 왼쪽으로 이동시켜야한다. 하지만 매번 이동시키려면 상강한 시간이 걸리고 또한 복잡도는 높아진다
즉, 막대 모양으로 된 큐이다. 크기가 제한되어 있고, 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.
- 환형 큐
선형 큐의 문제점을 보완한 것이 환형 큐이다. Front가 큐의 끝에 닿으면 큐의 맨앞으로 자료를 보내어 원형으로 연결하는 방식이다.
사용 사례
데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
- 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
- 노드를 접근한 순서대로 처리할 수 있다.
- 캐시(Cache) 구현
- 우선순위가 같은 작업 예약 (인쇄 대기열)
- 선입선출이 필요한 대기열 (티켓 카운터)
- 콜센터 고객 대기시간
- 프린터의 출력 처리
- 윈도 시스템의 메시지 처리기
- 프로세스 관리
덱,데크(Deque) 란?
덱(Deque)이란, Double Ended Queue의 준말로 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산을 모두 지원한다.
Scroll: 입력 제한 덱 (입력이 한쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있음)
Shelf: 출력 제한 덱 (입력은 양쪽에서 일어나고, 출력은 한쪽에서 일어나도록 제한)
덱의 연산은 collections 모듈에서 제공하는 deque 클래스로 구현 가능하다.
append(): 오른쪽에서 데이터를 삽입
appendleft(): 왼쪽에서 데이터를 삽입
pop(): 오른쪽에서 데이터 삭제
popleft(): 왼쪽에서 데이터 삭제
References (참고 자료)
