Python Stack,Queue

< 스택 >

 

 스택(stack)은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 LIFO 방식입니다. 데이터를 넣는 작업을 푸시(push), 데이터를 꺼내는 작업을 팝(pop), 푸시와 팝이 이뤄지는 윗부분을 꼭대기(top)이라 하며 아랫부분을 바닥(bottom)이라고 합니다.  스택 배열은 stk, 푸시한 데이터를 저장하는 스택 본체인 list형 배열입니다. 인덱스가 0인 원소를 스택의 바닥이라고 하고, 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]입니다. 스택 크기는 capacity, 스택의 최대 크기를 나타내는 int형 정수이고 이 값은 배열 stk의 원소 수인 len(stk)와 일치합니다. 스택 포인터는 ptr, 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터라고 합니다. 스택이 비어 있으면 ptr값은 0이 되고, 가득 차 있으면 capacity와 같은 값이 됩니다.

 

 

 

#fixed_stack. py

 

 

 3행은 고정길이 스택 클래스를 정의하고 6~9행에서 스택의 상황에 따라 예외처리를 하는 클래스를 정의한다.

 

 13행의 __init__함수는 스택의 관련된 전체 크기, 스택 자체의 크기, 스택 포인터의 값을 초기화해주는 부분이다.

 

 19~30행은 스택 안에 놓인 데이터 개수를 알 수 있게 해주는 함수, 데이터로 가득 차있는지 비어 있는지 판단해주는 함수의 정의이다.

 

 32~37행은 스택에 value를 푸시하여 데이터를 집어넣는 함수인데, 만약 스택 안에 데이터로 가득 차 더 이상 푸시가 불가능한 상태라면 raise FixedStack.Full을 통해 예외처리를 발생시키고 아니라면 스택 포인터에 값을 푸시한 후 포인터를 +1 증가시킨다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 39~50행에서 pop함수는 스택 안의 맨위 top에서 데이터를 꺼내는 함수이다. 마찬가지로 스택이 비어있으면 꺼낼 수 있는 데이터가 존재하지 않기 때문에 raise FixedStack.Empty로 예외처리를 발생, 아니라면 포인터를 -1 감소 시킨 후 데이터를 pop한다. peek함수는 포인터의 변화는 없고, top의 데이터를 볼 수 있는 함수이다.

 

 52~54행은 스택안의 모든 데이터를 삭제하는 함수이다.

 

 56~61행은 스택 안에서 찾고자 하는 value를 검색 후 인덱스를 반환하는 함수이다. 실패하면 -1을 반환한다.

 

 63~69행은 0부터 포인터 크기만큼 for문을 통해 값이 있다면 c의 변수를 +1씩 증가시켜 스택 안의 값 개수를 알 수 있는 함수이다.

 

 71~77행은 스택 안에 값이 있는지 판단하는 함수, 스택 안의 값을 모두 출력해주는 함수이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

< 큐 >

 

 큐(queue)는 스택과 같이 데이터를 임시 저장하는 자료구조입니다. 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 FIFO구조입니다. 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue), 꺼내어지는 쪽을 프런트(front), 넣는 쪽을 리어(rear)라고 합니다. 복잡도를 봤을 때 enqueue과정에서는 비교적 적은 비용으로 구현할 수 있지만, dequeue과정에서는 데이터를 꺼낼 때마다 꺼내고 남은 원소를 모두 앞쪽으로 옮겨야 하기 때문에 효율성이 낮다. 때문에 dequeue과정에서 원소를 옮기지 않는 큐가 있는데 그것이 링 버퍼(ring buffer)입니다. 링 버퍼로 큐를 구현하면 front와 rear로 값을 업데이트하는 것만으로 enqueue와 dequeuef를 수행할 수 있다.

 

 

#fixed_queue. py

 

 

 

 3~9행은 고정된 큐의 클래스 정의, 큐의 비어있는, 가득 차 있는 상태에 따라 예외처리를 해준다. 

 

 11~30행은 큐 초기화 함수(데이터 개수의 변수, front, rear 값 , 큐의 크기 , 큐 본체 크기)와, 큐의 empty, full의 상태 그리고 안의 데이터 개수를 알 수 있는 함수로 구성되어 있다.

 

 32~40행은 큐에 데이터를 넣는 함수이고, 데이터가 가득 차있는 경우 예외처리를 발생시킨다. rear는 데이터의 가장 뒤쪽을 가리키며 그곳에 추가할 데이터를 입력한다. 그 후 rear를 +1 증가시키고 데이터의 개수 변수인 no도 +1 증가시킨다. 만약 rear 값이 capacity와 같다면 rear를 배열의 맨 앞 인덱스 0으로 되돌린다. 이렇게 하면 다음에 인큐 하는 데이터가 que [0] 위치에 제대로 저장되기 때문이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 42~51행은 큐가 비어있는 경우 예외처리를 발생, x의 변수에 현재 큐 front의 값을 담은 후, front는 +1 증가, no는 -1 감소시킨다. 하지만 dequeue 하는 과정에서 front가 배열의 맨 끝인 경우 front를 증가시키면 그 값이 capacity와 같아져서 배열 인덱스의 한계를 넘어갑니다. 그래서 front의 값이 큐의 크기인 capacity와 같을 경우 front를 1 증가시켜 배열의 맨 앞 인덱스인 0으로 되돌려 다음 dequeue를 수행할 때 데이터를 que [0] 위치에서 제대로 꺼낼 수 있습니다.

 

 53~ 75행은 데이터의 맨 앞 데이터인 front를 볼 수 있는 함수, 원하는 value를 찾아 인덱스를 구하는 함수, 큐 안에 있는 value개수를 구하는 함수이다. idx = (i+self.front)% self.capacity를 주의 깊게 살펴보면 될 것 같다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 77~89행은 큐 안에 데이터가 들어있는지 없는지 확인하는 함수, 현재 큐에 들어 있는 모든 데이터를 삭제하는 함수, 큐의 전체 데이터를 출력하는 함수로 구성되어 있다.