17. 스택(Stack)과 큐(Queue)

자료구조는 특징이 있는 정보를 메모리에 효율적으로 저장 및 반환하는 메모리 구조를 가지는 저장 공간(체계)으로, 데이터를 관리하는 방식이다.

예로, 이름이 성만 기억난다고 했을 때, 그 사람을 전화번호부에서 찾는다고 가정하자. 전화번호부에서 데이터를 사람이 빠르게 찾으려면(=효율적으로 찾으려면) ㄱ,ㄴ,ㄷ 순으로 배열이 되어 있다면 무작위로 저장되어 있는 것보다 빠르게 접근이 가능해진다.

 

이러한 자료구조는 리스트, 스택, 큐, 튜플, 세트, 딕셔너리, collections 모듈 등이 있다. 그중 스택에 대해 알아볼 것이다.

 

스택의 정의

스택은 마지막에 들어간 데이터가 가장 먼저 나오는 형태로 데이터의 저장 공간(체계)을 구현한다.

스택에서 데이터를 저장하는 것을 푸시(push), 데이터를 추출하는 것을 팝(pop)이라고 한다. 아래는 인프런 강좌에서 예시를 든 그림을 가져왔다. 

출처 : 인프런 강좌 - 파이썬 기초부터 실무까지 제10강 자료구조 중 스택과 큐 - 스택 자료 사진

4라는 값이 먼저 쌓이고, 그다음 10, 15가 차례로 쌓인다. 그 후 4를 다시 꺼내려 한다면 위에 쌓인 15, 10을 꺼낸 후 마지막인 4의 값을 가져오게 된다. 현실 예로는 인터넷 뒤로 가기가 있다. 네이버 -> 다음 -> 유튜브로 검색을 하고 다시 네이버로 돌아간다고 하면 우리는 뒤로 가기를 두 번 눌러야 될 것이다.

 

파이썬으로 스택을 구현해보자.

리스트(list) 자료구조를 이용해 스택 자료구조를 표현할 수 있다. 아래는 append()와 pop()으로 스택을 구현한 것이다.

a = [1,2,3,4,5,6,7,8,9,10]
a.append(11)
print(a) # 결과 : [1,2,3,4,5,6,7,8,9,10,11]

순서

1. 리스트의 참조값의 위치가 a라는 별칭으로 저장이 된다. 

2. append() 함수가 a라는 변수 끝에 10을 추가로 저장(push)하라고 명령한다. -> 들어온 순서가 맨 뒤로 가게 한다.

3. pop() 함수가 a라는 변수의 끝을 추출(pop)하라고 명령한다. -> 추출할 때 맨 뒤(가장 최근에 대입된 값)를 가져온다.

 

스택의 응용

입력한 값을 역순으로 출력해주는 프로그램은 스택의 예다. 

word = input("단어 입력 : ")
word_list = list(word)
print(word_list)

result = []
for _ in range(len(word_list)):
    result.append(word_list.pop())
print(result)
print(word[::-1])

1. input() 함수로 저장된 값이 word 변수에 저장된다. 여기에  puzzle이라는 단어를 입력해보자.

2. word를 리스트로 바꾸면 아래와 같이 word_list에 저장(push)된다.

['p', 'u', 'z', 'z', 'l', 'e']

3. result에 빈 리스트를 생성한다.

4. word_list의 원소 개수만큼 반복하겠다는 for문을 진행한다.

• 참고 : for 문의 _ 는 for 하위 명령어를 world_list의 갯수 만큼 반복하겠다라는 의미로 쓸 때 사용한다. 즉, _는 for문에서 생성되는 값(ex. 여기서는 p, u, z, z, l, e 값 들)을 명령어 내에서 사용하지 않겠다는 의미이다.

4-1. word_list.pop() 함수가 실행된다 : word_list에서 맨 끝 값인 'e' 값을 추출(pop)한다.

4-2. 가져온 'e'값을 result.append() 함수가 인수로 받는다. : result 리스트의 마지막 값에 추가한다.

5. word_list의 맨 처음 원소인 'p'까지 4-1, 4-2가 반복된다.

6. 이후 print(result) 값은 다음과 같다.

['e', 'l', 'z', 'z', 'u', 'p']

 

위의 스택을 응용하는 과정을 요약하면,

• list(word) 함수를 쓰면 word에 입력된 글자가 순서대로 저장된다. 즉 마지막 값은 가장 최근에 입력된 값이다.
• pop 함수는 기존의 word_list의 맨 마지막 값(가장 최근에 들어왔던 값)을 가져오며 그 값을 word_list에서 삭제한다.

 list(word)를 쓰고 pop을 쓴다 = 맨 마지막에 입력한 값(가장 최근의 값)을 순서대로 꺼내고 삭제하겠다 라는 스택의 메모리 구조 체계를 표현한 것이다.

 

큐(Queue)

큐는 먼저 들어간 데이터가 먼저 나오는 메모리 구조를 가지는 저장 체계이다. 아래는 인프런 강좌에서 예시를 든 그림을 가져왔다. 

출처 : 인프런 강좌 - 파이썬 기초부터 실무까지 제10강 자료구조 중 스택과 큐 - 큐 자료 사진

메모리에 값이 쌓이는 과정은 스택과 마찬가지이나 만약 A, B, C가 쌓인 상태에서 값을 꺼낸다고 하면, 맨 처음 값이 쌓인 A값이 꺼내지고 삭제된다. 

 

큐와 스택의 차이점

• 큐와 스택은 반대 개념이다. 큐는 맨 처음 입력된 값을 가져오고 삭제하지만, 스택은 가장 최근에 입력된 값을 가져오고 삭제한다.
• 스택은 메모리가 시작하는 지점이 고정되어 있다. 그러나 큐는 맨 처음 값을 뽑을 때마다 메모리 주소가 계속 바뀌게 된다. 따라서 스택보다 큐의 구현에 더 많은 신경을 써야 한다.

 

파이썬에서의 큐 구현

파이썬에서 큐를 구현하는 것은 매우 간단한데, pop() 함수에서 인덱스가 0번째인 값을 가져온다는 뜻으로 pop(0)을 쓰면 된다.

a = [1,2,3,4,5,6,7,8,9,10]
a.append(11)
print(a)
a.append(12)
print(a)
a.pop(0) # 결과값 : 1
a.pop(0) # 결과값 : 2