티스토리 뷰
728x90
반응형
지난시간에 Queue 자료구조는 Data를 지울 경우 Queue의 Max Capacity가 감소한다고 했습니다.
Queue
Queue는 Array를 활용한 사용자 자료구조 중 하나입니다. Queue의 원리는 First In First Out(FIFP) 가장 먼저 들어온 Element가 가장 먼저 나간다 입니다. 정수기의 종이컵 / 놀이공원 대기열을 생각하면 쉽습
teus-kiwiee.tistory.com
Circular Queue는 이러한 단점을 극복하기 위해서 고안된 특이한 Case의 Queue라고 할 수 있습니다.

원형Queue는 선형Queue의 Input과 Output이 서로 붙어있는 구조라고 할 수 있습니다.
이렇게되면 FIFP의 원칙을 유지하되, Element가 삭제되어도 Capacity가 줄어들지 않습니다.
이때 Queue의 Empty상태와 Full상태를 구분하기 위해서 한칸의 공백을 유지하여
Input Pointer == Output Pointer -> Empty
input Pointer - Output Pointer == 1 -> Full
의 방법을 통해서 Queue의 Status를 확인할 수 있게됩니다.
Python으로 구현된 원형 Queue 소스코드입니다 :)
class c_queue:
def __init__(self, Max_size):
self.Max_size = Max_size
#Status 확인을 위해서 Input_pointer의 초기값이 0이 아닌 1로 할당
self.input_pointer = 1
self.out_pointer = 0
self.list = []
def add(self, element):
#1차원 구조상의 양 끝이 붙어있다고 추상화
if (self.input_pointer == self.out_pointer-1) or (self.input_pointer-self.out_pointer==self.Max_size):
return print("queue is full")
else:
if self.input_pointer>=self.Max_size:
self.input_pointer = (self.input_pointer - self.Max_size)
self.list= self.list + [element]
else:
self.input_pointer = self.input_pointer+1
self.list= self.list + [element]
def delete(self):
#1차원 구조상의 양 끝이 붙어있다고 추상화
if (self.input_pointer-self.out_pointer==1) or (self.out_pointer-self.input_pointer==self.Max_size):
return print("queue is empty")
else:
if self.out_pointer>=self.Max_size:
self.out_pointer = self.Max_size - self.out_pointer
del(self.list[0])
else:
self.out_pointer = self.out_pointer+1
del(self.list[0])
def is_full(self):
if (self.input_pointer == self.out_pointer-1) or (self.input_pointer-self.out_pointer==self.Max_size):
return True
else:
return False
def is_empty(self):
if (self.input_pointer-self.out_pointer==1) or (self.out_pointer-self.input_pointer==self.Max_size):
return True
else:
return False
import random
data = [i for i in range(20)]
random.shuffle(data)
test_que = c_queue(19)
for i in data:
test_que.add(i)
==> queue is full
test_que.input_pointer
==> 19
for i in data:
test_que.delete()
test_que.is_empty()
==> True
728x90
반응형
'컴퓨터과학 > Python 자료구조' 카테고리의 다른 글
Binary Tree (0) | 2021.01.30 |
---|---|
Connect List 응용(원형, 이중) (0) | 2021.01.29 |
Connect List(연결리스트) (0) | 2021.01.28 |
Queue (0) | 2021.01.26 |
Stack (0) | 2021.01.26 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 자료구조
- react
- 완전탐색 알고리즘
- 알고리즘
- 청첩장
- stack
- prime number
- Search알고리즘
- 프로그래머스
- SIMD
- GPT
- 사칙연산
- hash
- Sort알고리즘
- ai
- 동적계획법
- AVX
- LLM
- 모바일청첩장
- 분할정복
- 코딩테스트
- 이분탐색
- 병렬처리
- 셀프모청
- Greedy알고리즘
- GDC
- git
- Python
- javascript
- ChatGPT
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
글 보관함