[Python] 큐 운영하기 (Queue)

Sony·2022년 7월 29일

python 자료구조

📚 자료구조

목록 보기

5/6

📌 What to do?

문자가 입력되어 큐에 쌓이는 시스템에서 필요한 수만큼 문자를 가져오는 프로그램을 작성한다.

⚡️ 조건

해당 프로그램은 문자가 큐로 들어온다.
사용자가 필요한 데이터의 개수를 입력하면 큐에서 해당 데이터를 가져온다.
사용되는 큐의 크기는 20(문자)이다. 큐의 크기를 초과한 데이터는 받아들일 수 없다. (에러 표시)
사용되는 큐는 원형 큐이다. 직접 원형 큐를 만들어야 한다.

⚡️ 큐 입력

사용자가 입력한 n 개의 문자 (A~Z, a~z) 를 순차적으로 큐에 넣는다.

⚡️ 큐 출력

사용자가 숫자 (1~9) 를 넣으면 큐에서 해당 수만큼 가져와 화면에 표시한다.
0 을 넣으면 큐에서 가져오지 않고 큐의 상태를 화면에 표시한다.

완성된 프로그램의 실행 예시는 다음과 같다.

📌 큐의 형태

원형 큐의 Empty와 Full상태를 구별하기 위한 방식은 두가지가 있다.

별도의 flag 변수를 사용한다.
⚡️ flag == True : 원소가 존재, flag == False : 원소가 존재하지 않는다
큐의 한칸은 비워둔다.

그 중 첫번째 방식을 통해, 즉 별도의 flag 변수를 사용하여 큐를 만들어 보았다.

📌 Code 설명

🛠 flag 변수

self.flag = False

큐의 Empty와 Full상태를 구분하기 위한 변수 flag를 선언하고 그 값을 False로 초기화해주었다.
큐에 값이 들어있을 경우엔 True값을, 없을 경우엔 False값을 가진다.

🛠 is_Empty(self)

def is_Empty(self):
	return not self.flag

큐가 비었는지 판단해주는 함수로, flag와 반대의 값을 반환한다.

Flag == True : 큐에 값이 존재하므로 -> is_Empty == False
Flag == False : 큐에 값이 존재하지 않으므로 -> is_Empty == True

🛠 is_Full(self)

def is_Full(self):
	if self.flag:
		return self.front == self.rear % QSIZE
	else:
		return False

만약 flag == True이면,
즉 큐에 값이 있을 경우엔 큐의 front의 위치와 rear(% QSIZE)의 위치가 같은지 판단하여
그 결과값을 반환한다.

아닌 경우엔 False를 반환한다.

🛠 push_Queue(self, item)

def push_Queue(self, item):
	for i in range(len(item)):
		if not self.is_Full():
			self.items[self.rear] = item[i]
			self.rear = (self.rear + 1) % QSIZE
			print("(SYSTEM) ADDQUEUE(%s)" % item[i],
				"F=%d R=%d" % (self.front, self.rear))
			self.flag = True

큐가 가득 차 있지 않은 경우에 (not self.is_Full( )) 문자열을 입력 받으면(ex. “ABC”),
이를 문자별로 쪼개서 큐에 담아준다.
그리고 입력 받은 문자열의 문자의 개수 만큼 rear의 위치도 이동시켜준다.
이때, 원형 큐 이므로 항상 rear의 값에 “% QSIZE”연산을 수행해준다.
그리고나서 각 문자별로 입력되었음을 확인시켜주는 문장을 출력해준다.
마지막으로 flag의 값을 True로 바꿔주고 메소드를 종료시킨다. (큐에 값이 들어왔으므로)

🛠 pop_Queue(self, n)

def pop_Queue(self, n):
	for i in range(n):
		if not self.is_Empty():
			pop = self.items[self.front]
			self.front = (self.front+1) % QSIZE
			print("DELETEQUEUE() =%s," % pop, "F=%d R=%d" % (self.front,
				self.rear))
			if self.flag and self.front == self.rear:
				self.flag = False
		else:
			print("DELETEQUEUE() FAIL. QueueEmpty")

큐가 비어 있지 않은 경우에 (not self.is_Empty( )) 외부로부터 n 이라는 정수를 입력 받고,
n 만큼 반복하면서 큐에 들어있는 값들을 하나씩 가져오고,
각 문자별로 꺼냈음을 확인시켜주는 문장을 출력해준다.
그리고 가져올때마다 front의 위치도 한 칸 씩 앞으로 옮겨준다.
이때, flag의 위치와 rear의 위치가 같아지면 이는 큐가 비었음을 의미하므로,
flag의 값도 False로 바꿔주고 메소드를 종료 시킨다.
큐가 비어 있는 경우엔 값을 더이상 가져올 수 없다는 문장을 출력해주고 메소드를 종료 시킨다.

🛠 display(self)

def display(self):
	if self.front < self.rear:
		str = self.items[self.front:self.rear]
	else:
		str = self.items[self.front:QSIZE] + self.items[0:self.rear]
        
	if not self.is_Empty():
		str = ''.join(str)
		print("QUEUE =", str, "(%d)" % len(str))
	else:
		print("QUEUE = (0)")

rear의 위치가 front보다 앞에 있을 경우,
front부터 rear까지 해당하는 문자들을 가져와서 str리스트에 담아준다.
아닐 경우엔 front부터 큐의 끝까지 해당하는 문자들과,
큐의 시작점부터 rear까지 해당하는 문자들을 가져와 str리스트에 담아준다.

이렇게 케이스가 나뉘는 이유는, 해당 큐가 원형이기 때문이다.
원형 큐는 큐를 운영하다 보면, 즉 큐에 요소를 삽입하거나 빼내는 과정에서 rear의 위치가 front의 위치보다 앞에 오는 경우가 발생 할 수도 있기 때문이다.

큐가 비어 있지 않은 경우엔 (not self.is_Empty( )),
str에 들어있는 문자들을 합쳐서 하나의 문자열로 변환한 뒤,
해당 문자열과 문자열의 길이를 출력해준다.
큐가 비어 있을 경우엔 "QUEUE = (0)"을 출력해준다.

📌 실행결과

📌 전체코드

QSIZE = 10

class Queue:
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.flag = False
        self.items = [None] * QSIZE

    def is_Empty(self):
        return not self.flag

    def is_Full(self):
        if self.flag:
            return self.front == self.rear % QSIZE
        else:
            return False

    def clear(self):
        self.front = self.rear
        self.flag = False

    def push_Queue(self, item):
        for i in range(len(item)):
            if not self.is_Full():
                self.items[self.rear] = item[i]
                self.rear = (self.rear + 1) % QSIZE
                print("(SYSTEM) ADDQUEUE(%s)" % item[i], "F=%d R=%d" % (self.front, self.rear))
                self.flag = True

    def pop_Queue(self, n):
        for i in range(n):
            if not self.is_Empty():
                pop = self.items[self.front]
                self.front = (self.front+1) % QSIZE
                print("DELETEQUEUE() = %s," % pop, "F=%d R=%d" % (self.front, self.rear))
                if self.flag and self.front == self.rear:
                    self.flag = False
            else:
                print("DELETEQUEUE() FAIL.QueueEmpty")

    def peek(self):
        if not self.is_Empty():
            return self.items[self.front % QSIZE]

    def display(self):
        if self.front < self.rear:
            str = self.items[self.front:self.rear]
        else:
            str = self.items[self.front:QSIZE] + self.items[0:self.rear]

        if not self.is_Empty():
            str = ''.join(str)
            print("QUEUE =", str, "(%d)" % len(str))
        else:
            print("QUEUE = (0)")

q = Queue()

print("시스템이 시작됩니다.")
while True:
    enter = input(">>>")

    if enter == '0':
        q.display()
    elif enter in '123456789':
        enter = int(enter)
        q.pop_Queue(enter)
    else:
        q.push_Queue(enter)