Stack

정의

스택은 제한적으로 접근할 수 있는 나열구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. - wikipedia

개념

• 한쪽 끝에서만 자료를 넣고 빼는 작업이 이루어지는 자료구조

특징

• LIFO(Last In First Out) : 가장 마지막에 들어간 원소가 가장 먼저 나온다
• 스택의 top에서만 접근이 가능하기 때문에 데이터의 접근, 삽입, 삭제가 빠르다
• top이외의 데이터에 접근하기 위해서는 그 위에 있는 데이터를 모두 꺼내야 한다

동작

• 삽입(push) : top위치에 데이터를 삽입
  • O(1)
• 삭제(pop) : top위치의 데이터를 삭제
  • O(1)

구현

stack = []              # init
stack.append(3)         # push
stack.append(6)
stack.append(9)
print(stack)            # [3,6,9]
print(stack.pop())      # pop, stack = [3,6]
print(stack[-1])        # top

활용

• 웹 브라우저 방문기록
• 실행취소
• 재귀 알고리즘
• DFS

Queue

정의

큐는 시퀸스에서 유지 관리되는 엔티티의 모음이며, 시퀸스의 한쪽 끝에 엔티티를 추가하고 다른 쪽 끝에서 엔티티를 제거 하여 수정할 수 있다.

개념

• 한쪽 끝에서 자료를 넣고, 다른쪽 끝에서 빼는 자료구조

특징

• FIFO(First In First Out) : 가장 먼저 들어간 원소가 가장 먼저 나온다
• rear에서 데이터가 삽입되고, front에서 데이터가 나온다
• front와 rear를 통해서만 데이터를 조작할 수 있기 때문에 데이터의 접근, 삽입, 삭제가 빠르다
• 중간에 위치한 데이터에 대한 접근이 불가능하다

동작

• 삽입(enqueue) : rear의 위치로 데이터를 삽입
  • O(1)
• 삭제(dequeue) : front 위치의 데이터 삭제
  • O(1)

구현

• list로 구현

queue = []              # init
queue.append(3)         # push
queue.append(6)
queue.append(9)
print(queue)            # [3,6,9]
print(queue.pop(0))     # pop, queue = [6,9]

• deque로 구현 : deaue모듈은 내부적으로 이중 연결 리스트로 구현되어 양 끝에서의 연산이 빠름

from collections import deque

queue = deque()         # init
queue.append(3)         # push
queue.append(6)
queue.append(9)
print(queue)            # [3,6,9]
print(queue.popleft())  # pop, queue = [6,9]

활용

• 어떤 작업이나 데이터를 순서대로 실행시키기 위해 대기시킬때 사용
  • 대기열
  • 프로세스 관리
• BFS

Circular queue(Ring Buffer)

정의

선형 큐의 문제점 (배열로 큐를 선언할 시 큐의 삭제와 생성이 계속 일어났을 때 마지막 배열에 도달한 후 실제로는 데이터 공간이 남아있지만 오버플로우가 발생 )을 보완한 것 - wikipedia

개념

• 처음과 끝이 연결되어있는 큐

특징

• front와 rear가 배열의 마지막 인덱스에 도달하면 다음은 배열의 맨 앞 인덱스를 가리킨다.
  • 나머지 연산을 사용하여 구현
• 데이터가 배열의 끝에 다다르면 다시 처음으로 돌아올 수 있다.
• 데이터 삭제시 front 뒤의 모든 데이터를 앞으로 이동시키지 않아도 된다.
• front는 큐의 첫번째 원소보다 한칸 앞을 가리킨다
• rear는 큐의 마지막 원소의 위치를 가리킨다
• front나 rear를 이동할 때에는 다음 식을 따른다. : ([front|rear]+1) % MAX_QUEUE_SIZE
• 공백상태와 포화상태를 구분하기 위해 배열에 한 칸을 비운다

동작

• 삽입(enqueue) : rear가 증가하고 그 위치에 데이터가 삽입된다
  • O(1)
• 삭제(dequeue) : front가 증가하고 그 위치에 있는 데이터가 삭제된다
  • O(1)

Deque(Double Ended Queue)

정의

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조의 한 형태이다

개념

• 양방향 큐 : front와 rear에서 삽입과 삭제가 가능한 큐

특징

• 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있다

동작

• 삽입(push_front, push_back) : front, rear위치에 데이터 삽입
  • O(1)
• 삭제(pop_front, pop_back) : front, rear위치의 데이터 삭제
  • O(1)

구현

from collection import deque

queue = deque()         # init
queue.append(3)         # push_back
queue.append(6)
queue.appendleft(9)     # push_front
print(queue)            # [9,3,6]
print(queue.popleft())  # pop_front, queue = [3,6]
print(queue.pop())      # pop_back, queue = [3]