[자료구조/파이썬] 스택(Stack) / 큐(Queue) 개념 및 구현

본문 내용은 <이것이 취업을 위한 코딩테스트다> 도서를 참고했습니다. 

 

 

1. 자료구조 (Data Structure)

- 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

 

2. 스택과 큐 

- 스택과 큐는 삽입(push) 과 삭제(pop) 함수로 구성된다. 

- 삽입(push)함수는 자료구조에 데이터를 삽입하는 역할을 하고, 삭제(pop)함수는 자료구조에서 데이터를 삭제하는 역할을 한다. 

 

스택과 큐를 사용할 때 주의해야하는 부분 → 오버플로우와 언더플로우 

- 오버플로우(overflow)는 특정 자료구조에 수용할 수 있는 데이터의 크기를 넘어선 상태에서 삽입연산을 수행하는 경우 발생한다. → 저장공간을 벗어나 데이터가 넘칠(over)때 발생한다. 

- 언더플로우(underflow)는 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제연산을 수행하는 경우 발생한다. 

 

 

3. 스택 (Stack)

1) 스택이란? 

출처 : https://yadon079.github.io/2020/cs/stack

- 스택은 입구와 출구가 동일한 형태로 후입선출(Last In First Out) 구조를 가진다. 나중에 들어온 값이 먼저 나가는 구조.

- 파이썬에서는 스택을 리스트 자료형으로 간단하게 구현할 수 있다.

 

2) 스택 구현 

stack = list() #stack이라는 이름의 비어있는 리스트 생성

#값 5 삽입
stack.append(5)

#값 2 삽입
stack.append(2)

#값 3 삽입
stack.append(3)

#값 7 삽입
stack.append(7)

#삭제
stack.pop()  #리스트의 pop 메소드 :  리스트에 맨 마지막으로 입력된 값이 return 

#값 1 삽입
stack.append(1)

#값 4 삽입
stack.append(4)

#삭제
stack.pop() 

print("final list value : ", stack)

- 파이썬 리스트 자료형의 append 메소드와 pop 메소드 만으로 스택을 구현할 수 있다. 

- append() : 리스트의 가장 뒤쪽(맨 끝)에 데이터를 삽입

- pop() : 리스트의 가장 뒤쪽(맨 끝)의 데이터를 삭제 

 

 

4. 큐 (Queue) 

1) 큐란?

출처 : https://galid1.tistory.com/483

- 큐는 한 쪽 끝(rear)에서 데이터가 삽입이 되고 다른 한 쪽 끝(front)에서는 데이터가 삭제 되는 구조 

- 먼저 들어온 데이터가 먼저 나가는 선입선출(First In First Out) 구조

- 파이썬에서 collections 모듈의 deque 자료구조를 사용하면 빠르게 큐를 구현할 수 있다. from collections import deque

 

2) 큐 구현

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7) #deque([5,2,3,7])
queue.popleft() #queue에 맨 첫번째 값인 5를 삭제(pop)한다. deque([2,3,7])
queue.append(1)
queue.append(4)	#deque([2,3,7,1,4])
queue.popleft() #맨 첫번째 값인 2를 삭제(pop)한다. deque([3,7,1,4])

print(queue) #deque([3,7,1,4])
print(list(queue)) #[3,7,1,4]

- deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이고, queue 라이브러리를 이용하는 것보다 간단하다. 

- collections 라이브러리는 파이썬에서 제공하는 기본 라이브러리이므로 코딩테스트에서 사용이 가능하다. 

- deque 객체를 리스트로 변경하고 싶으면 deque 객체를 list로 감싸주면 된다. → list(deque())