파이썬으로 알고리즘, 자료구조 공부하기 - 스택과 큐(stack, queue)

파이썬으로 자료구조, 알고리즘 공부를 다시 하고 있다

너무 오랜만에 해서 뜨문뜨문 기억이 나면서 진행하고 있다

 

지난 포스팅까지는 연결 리스트(linked list)와 이중 연결 리스트(doubly linked list)를 다뤄봤다

이번에는 스택과 큐이다.

먼저 스택이다.

stack은 자료구조에서 정말 많이 보이는 그리고 많이 사용되기도 하는 자료구조이다

Last In First Out의 구조 즉 LIFO의 구조를 따른다

 

스택의 구조를 그림으로 설명하면 위와 같이 된다

A->B->C->D 순으로 들어오고 가장 맨 위를 top이 가리킨다. 그리고 마지막에 들어온 D부터 차례대로 out되는데 이 과정을 pop 이라고 한다. 또한, 스택에 들어오는 과정은 push라고 한다.

이 과정을 파이썬 코드로 작성하면 어떻게 될까?

아래와 같이 간단하게 구현할 수 있다.

 

 

stack이라는 바구니를 하나 만들고(빈 배열) 거기에 append를 하면서 데이터를 추가시킨다

그리고 출력할 때는 차례대로 출력을 해야하므로 pop을 이용한다.

이렇게 단순하게 하면 정말 간단하다

사실 C나 java로 구현하면 좀 더 복잡한데 파이썬이라서 가능한 코드이다

그럼 좀 더 자세하게 해볼까?

후위 계산법(postfix) 방법이 있다. 이거는 특히 어떤 연산을 할 때 많이 사용된다

예를 들어 (A+B) * (C + D)가 있다고 가정하자.

이거는 우리가 평소에 쓰는 방법이며 중위 표현법이라고 불리운다

이것을 후위 표현법으로 바꾸면

AB+CD+*와 같이 된다. 즉 연산자가 피연산자들 뒤에 위치하게 된다. 이걸 사용하면 계산기를 만들 수 있는 방법이 된다.

여기서! 피연산자는 숫자 등을 의미한다. 연산자는 +-/ 등을 의미한다!

이것을 구현해보자

 

 

 

먼저 들어오는 값이 (2+3)*4-5 라고 가정하자. 그래서 이 값들을 토크나이징해서 infix에 들어가있다고 가정한다

그 다음 표현법 순서를 담을 postfix와 연산자를 담을 stack을 둔다.

그 다음 operator 즉 연산자 목록과 bracket 목록을 담는다.

pref 함수를 만들어서 연산자들의 우선순위를 둔다. 괄호( (, ) )는 연산자 순위가 낮고 그 다음 덧셈, 뺄셈(+, -) 그 다음 곱셈, 나눗셈(*, /)가 우선순위가 높다.

이 우선순위에 따라서 표기법이 달라지기 때문이다. 그리고 덧셈, 뺄셈보다 곱셈, 나눗셈을 먼저 계산하기 때문에 이렇게 우선순위를 두는 것이다.

 

 

이제 후위 표기법으로 바꾸는 연산을 진행한다. 먼저 숫자 체크를 해서 숫자가 맞으면 postfix에 넣는다.

그게 아니라 연산자(operator)에 속하면 우선순위를 가져오고 stack 개수만큼 돌면서 값을 가져와 우선순위를 비교한다. 만약 가져온 값의 우선순위가 stack의 맨 위에 있는 우선순위보다 높으면 break를 걸고 stack에 그냥 쌓는다. 왜냐하면 우선순위가 높으니까. 그게 아니라면 stack에 있는 연산자를 하나 빼서 postfix에 넣어준다. 그리고 stack에 우선순위가 낮은 연산자를 넣어준다.

'(' 면 stack에 넣어주고 만약 닫히는 괄호(  ')'  ) 면  열리는 괄호 '(' 전까지 값들을 stack에서 빼내며 postfix에 넣어준다.

그리고 마지막으로 stack에 남아있는 애들을 postfix에 넣어주면 끝!

 

 

이렇게 결과를 볼 수 있을 것이다

 

다음은 큐(queue)다.

큐는 FIFO로 유명하다. First In First Out 구조이다.

즉 먼저 들어온 애들이 먼저 나가는 것이다. 매표소라고 생각하면 편하다.

먼저 온 사람들이 줄을 서서 있다가 먼저 표를 받는다

 

 

 

구조는 이렇게 된다.

넣는 것을 put또는 enqueue라고 하고 빼는 것을 get 또는 dequeue라고 한다

 

파이썬으로 구현하면 위와 같이 간단하게 구현이 가능하다.

거의 스택이랑 비슷하지만 get할 때 pop(0)를 가져오며 맨 처음 것을 가져 온다.