Stack & Queue

mon99745·2022년 6월 9일
0
post-thumbnail

🤔 목적

컴퓨터공학의 기초가 되는 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 (참고 자료)

0개의 댓글