Stack(스택)

스택이란?

컴퓨터 과학에서 사용되는 일종의 추상적인 자료구조로써 Last In First Out을 기본으로 하는 LIFO 방식의 자료구조이다.
스택이란 쌓아놓은 더미를 나타내며 이름 뜻 그대로 데이터를 위로 쌓아놓은 형태가 된다.

이처럼 스택은 Data가 들어가면 먼저 들어간 Data는 아래로 들어가고 마지막에 들어간 Data가 맨 위에 있으며, Stack에 접근하여 Data를 사용시에는 가장 마지막에 들어간 Data를 사용한다.

스택의 기본연산

• top(): 현재 Stack에 최상단 Data를 가리키는 Pointer
• push(): Stack에 Data를 삽입하는 연산
• pop(): top이 가리키고 있는 Data를 가져오는 연산 (삭제 O)
• peek(): top이 가리키고 있는 Data를 가져오는 연산 (삭제 X)
• size(): Stack에 들어있는 Data의 개수 반환
• empty(): Stack이 공백 상태인지 확인하는 연산
• full(): Stack의 size가 다 차있는지 확인하는 연산

시간 복잡도 (Time complexity)

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert (push)	O(1)	O(1)
Delete (pop)	O(1)	O(1)

Python에서의 Stack

파이썬에서는 Stack 자료구조 자체를 지원해주지 않고 리스트를 활용해서 표현한다.

stack = []  #stack init()
stack.append(5) #push()
top = stack.pop() #pop()
top = stack[-1] #peek()
len(stack) #size()

위 연산을 통해 Stack을 표현하여 Python에서 사용한다.

Stack의 사용 예시

• 함수 호출
• 깊이 우선 탐색(DFS)
• 웹 브라우저 History의 뒤로 가기 기능
• 수식 계산: 후위 표기법(Postfix notation)
• 역순 문자열
• 괄호의 짝, Undo 등

---

Queue (큐)

큐란?

컴퓨터 과학에 사용되는 선형 자료구조로, 데이터의 삽입과 삭제가 양 끝에서 일어나는 자료 구조다. 큐는 데이터가 들어온 순서대로 처리되는 선입선출(FIFO, First-In-First-Out) 방식을 기본으로 한다.

Queue는 Stack과는 다르게 선형의 모습으로 있어 Data가 Queue에 삽입되는 방향과 호출되는 방향이 반대에 있다.
즉, 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어진다.

큐의 기본연산

• enQueue() : 큐에 데이터를 넣는다.
• deQueue() : 큐에서 데이터를 빼낸다.
• empty() : 큐가 비어있는지 확인한다.
• full() : 큐가 꽉 차 있는지 확인한다.
• peek() : 앞에있는 원소를 삭제하지 않고 반환한다.
• rear : 큐의 꼬리로써 Queue의 Last Data를 의미한다.
• front : 큐의 머리로써 Queue의 First Data를 의미한다.

시간 복잡도 (Time complexity)

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert (Enqueue)	O(1)	O(1)
Delete (Dequeue)	O(1)	O(1)

Python에서의 Queue

파이썬에서는 Queue를 구현할 때 deque라는 것을 사용한다.
간단하게 deque를 알아보자면 다음과 같다.

Deque

Deque(Double-Ended Queue)는 이름 그대로 양쪽 출입구를 Queue로 사용할 수 있는 자료구조이다. 양끝 요소에서 접근하여 데이터 삽입과 삭제 연산을 이룰 수 있는 자료구조

Python에서는 Queue와 Deque 모두 지원을 해주지만 Queue에서는 thread-safe라는 추가적인 기능을 제공한다.
그렇기에 Deque로 구현하는 것보다 느리게 실행된다는 문제점이 있어 시간이 중요한 코딩테스트에서는 Deque를 사용하는 것이 일반적이다.

from collections import deque

queue=deque()
queue.append(123) #뒤쪽
queue.appendleft(456) #왼쪽 (앞)
queue.appendleft(789) #왼쪽 (앞)

print(queue.pop())  #뒤쪽
print(queue.popleft()) #왼쪽 (앞)

위 연산과 같이 Queue를 Python에서 사용한다.

Queue의 사용 예시

• 작업 큐(Task Queue)
• 메시지 큐(Message Queue)
• 버퍼(Buffer)
• 웹 요청 처리
• 너비 우선 탐색(BFS)
• 트리의 레벨 순회(Level Order Traversal)