자료구조와 알고리즘 with 파이썬 chapter2

1. 큐란?

가장 먼저 들어간 자료가 가장 먼저 나오는 자료구조(FIFO)

(1) 큐의 연산

• enqueue(e) : 새로운 요소 e를 큐의 맨 뒤에 추가
• depueue( ) : 큐의 맨 앞에 있는 요소를 꺼내서 반환
• isEmpty( ) : 큐가 비어 있으면 True를, 아니면 False를 반환
• isFull( ) : 큐가 가득 차 잇으면 True를, 아니면 False를 반환
• peek( ) : 큐의 맨 앞에 있는 요소를 삭제하지 않고 반환
• size( ) : 큐에 들어 있는 전체 요소의 수를 반환

2. 배열로 구현하는 큐

• array[ ] : 큐 요소들을 저장할 배열
• capacity : 큐에 저장할 수 있는 요소의 최대 개수
• rear : 맨 마지막(후단) 요소의 위치(인덱스)
• front : 첫 번째(전단) 요소 바로 이전의 위치(인덱스)

선형 큐의 문제점 : 새로운 요소를 삽입할 수 없을 때 큐의 요소들을 모두 최대한 앞으로 옮겨 후단에 공간을 확보한 다음 삽입해야 함-> 문제점 해결 => 원형 큐

원형 큐 : front와 rear을 원형으로 회전시키는 개념

• 전단 회전 : front ← (front + 1) %capacity
• 후단 회전 : rear ← (rear + 1) %capacity

원혀 큐: 클래스 정의와 생성자

class ArrayQueue :
	def __int__(self, capacity = 10):
    		self.capacity = capacity
        	self.array = [None] * capacity
        	self.front = 0
        	self.rear = 0

원형 큐: 공백 상태와 포화 상태 검사

def isEmpty(self) :
	return self.front == self.rear
def isFull(self):
	return self.front == (self.rear+1)%self.capacity

테스트 프로그램

import random
q = ArrayQueue(8)

q.display("초기상태")
while not q. isFull():
	q.enqueue(random.randint(0,100)
q.display("포화상태")

print("삭제순서: ", end='')
while not q.isEmpty():
	print(q.dequeue(), end = ' ')
print()

링 버퍼 : 최근의 자료를 유지 하는 용도로 사용. 가장 오래된 데이터를 삭제해서 큐를 계속 포화 상태로 유지.

q = ArrayQueue(8)
q.display("초기상태")
for i in range(6)
	q.enqueue2(i)
q.display("삽입 0-5")
q.enqueue2(6); q.enqueue2(7)
q.display("삽입 6,7")
q.enqueue2(8); q.enqueue2(9)
q.display("삽입 8,9")
q.dequeue(); q.dequeue()
q.display("삭제 x2")

3. 덱이란?

덱: 전단과 후단에서 모두 삽입과 삭제가 가능한 큐

덱의 연산

• addFront(e) : 새로운 요소 e를 전단에 추가
• addRear(e) : 새로운 요소 e를 후단에 추가
• deleteFront( ) : 덱의 전단 요소를 꺼내서 반환
• deleteRear( ) : 덱의 후단 요소를 꺼내서 반환
• getFront( ) : 덱의 전단 요소를 삭제하지 않고 반환
• getRear( ) : 덱의 후단 요소를 삭제하지 않고 반환
• isEmpty( ) : 덱이 비어 있으면 True를 아니면 False를 반환
• isFull( ) : 덱이 가득 차 있으면 True를 아니면 False를 반환
• size( ) : 덱이 들어 있는 전체 요소의 수를 반환

원형 덱은 반시계 방향 회전

원형 덱: 큐를 상속한 클래스 정의

class CircularDeque(ArrayQueue):
	def __int__(self, capacity=10) :
    		super().__int__(capacity)