선형 큐, 환형 큐

laoshanlong

2011.09.24 11:06:22

조회 259 추천 0 댓글 1

보통 선형큐를 배열로 만들면 입출력을 위한 오버헤드는 없지만 값을 하나 빼서 배열내의 아이템을 쉬프트할때 시간이 걸림. 그래서 오버헤드는 발생하지만 추가적인 복사, 삭제 작업이 없는 리스트로 만듬.

근데 여기서 논리적인 확장을 통해 물리적으론 선형 배열이지만 논리적으론 환형 형태로 동작하는 서클러 큐를 만들게 된거임. 환형 큐는 오버헤드도 없고 쉬프트도 안하거든, 커서만 움직이지.

근데 이쯤에서 환형큐가 왜 보통 동적으로 확장을 안하냐하면 큐가 꽉차거나 큐 내부 아이템 비율이 적어서 동적으로 확장이나 축소를 하게되면 필연적으로 배열내의 아이템을 모조리 복사해야하거든. 만약 저런 확장, 축소빈도가 빈번하게 일어나는 경우에선 선형큐를 배열로 만드는거랑 큰 차이가 없게됨.

여튼 내가 알기론 보통 이래서 환형 큐는 보통 확장이 없는거임.

근데 자기가 환형큐가 필요하고 확장, 축소빈도가 적다고 생각되면 그거 구현해서 쓰면되는 요런 문제. 케바케인듯

왜쓰는지는 물어본사람만 알거임

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	반응이 재밌어서 자꾸만 놀리고 싶은 리액션 좋은 스타는?	운영자	25/07/28	-	-
AD	휴대폰 액세서리 세일 중임!	운영자	25/07/28	-	-
277855	노는 스마트 폰에 os 설치 불가능 할까?? [10]	거칠게	11.10.04	166	0
277853	USB로 윈7 까는데 도움좀.. [6]	에드라드(121.187)	11.10.04	87	0
277851	소스인사이트쓰는 횽들 질문 [3]	3(116.42)	11.10.04	243	0
277850	형들 오픈지엘 텍스쳐 Disable하면 아예 죽게하는법 없어?	+어게인	11.10.04	40	0
277849	안녕!	ㅁㄴㄻㄹ	11.10.04	46	0
277848	자바에서 메소드 클릭하면 이렇게 뜨는데 왜그런지 알아? [5]	좋은아버지	11.10.04	104	0
277846	정규식 알려주세요 [8]	정규식(58.184)	11.10.04	128	0
277843	혹시 시스템 프로그래머가 될려면 어떻게 준비해야 하는지 알아? [4]	좋은아버지	11.10.04	135	0
277841	스탠포드 무료 기계학습 과정 좋다 진짜 [2]	멸자(130.126)	11.10.04	105	0
277836	그런데 궁금한게 있는데 말이지 [3]	좋은아버지	11.10.04	68	0
277835	형들 비베 코딩 for문 좀 알려줄수 잇어요? [2]	ㅇㅂ(218.237)	11.10.04	93	0
277834	워그화 신었는데 [1]	Adelposs	11.10.04	59	0
277833	안드로이드로 숫자야구 앱 만들었는데 [3]	?(124.199)	11.10.04	115	0
277832	혹시 소프트웨어 마에스트로 에 대해서 잘 아는 형 있어? [1]	좋은아버지	11.10.04	70	0
277831	횽들 한글로 된 언어는 외쿡인들이 안 써줘서 망했다고 그랬자낭.. [1]	LazyGyu	11.10.04	103	0
277830	좋은아침입니다 다들출근은했지요	三didas	11.10.04	44	0
277829	ㅋㅋ 너무 졸려서 [5]	Adelposs	11.10.04	81	0
277827	내일이 지나면 나는 이제 3개월 차 에 돌입해. [5]	좋은아버지	11.10.04	117	0
277826	클래스 다이어그램 그릴일이 있는데.. [4]	쿄스케	11.10.04	125	0
277825	개발자 동호회 같은거 하고 싶은데 [23]	좋은아버지	11.10.04	225	0
277824	닌자파워어쌔신.zip [3]	회전매니아	11.10.04	127	0
277823	샘숭이말하는 대항마라는게	ㅂㅈㄷ(210.178)	11.10.04	53	0
277822	출근 is 죽고 싶다. [6]	좋은아버지	11.10.04	103	0
277819	크하하하하 만들었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ	forhappiness	11.10.04	49	0
277818	아게이 도대체 어디감?	Adelposs	11.10.04	30	0
277816	아니 시발 ktx 개객기	Adelposs	11.10.04	45	0
277815	프갤여러분들 안녕!	AnonyMous	11.10.04	38	0
277813	강남비트 자바 고급반 정보좀 줘~~부탁해,.,	밥팅이야(59.10)	11.10.04	105	0
277812	1000원짜리 버스	막장갤신학생	11.10.04	52	0
277811	형들살려줘 [3]	Adelposs	11.10.04	74	0
277810	아 시발 진ㄴ짜 지려온다	Adelposs	11.10.04	36	0
277809	아 피곤해 시발	Adelposs	11.10.04	28	0
277808	아 진짜 졸렵다	Adelposs	11.10.04	36	0
277807	C++ 오류 질문좀 드릴게요 [3]	라마(71.82)	11.10.04	61	0
277806	(c/c++)이게 왜 오류야? ㄷㄷ; [3]	forhappiness	11.10.04	85	0
277805	오브젝티브 ㅆ ㅣ 공부하다가 [1]	돌아이바	11.10.04	63	0
277804	자바하는데 객체가 너무어렵다... [6]	^0^	11.10.04	145	0
277803	Bodhi(보디,버디) 리눅스를 써봤다 [3]	로하로하알로하	11.10.04	184	0
277802	내일이 대망의 프레젠테이션 발표인데 [3]	일광면(119.198)	11.10.04	90	0
277801	그냥 인증서 좀 백업하겠다는데	로하로하알로하	11.10.04	38	0
277800	밑에 스택프레임 보세요 [1]	일광면(119.198)	11.10.04	57	0
277799	카이스트나 서울대 컴공/대학원 나오면..	으아(121.145)	11.10.04	500	0
277798	뒤늦게 이제서야 크라이시스를 해봤는데 [1]	ㅋㄱ(183.96)	11.10.04	74	0
277797	6! (팩토리얼) 스택프레임 으로 그려오라는데 좀 알려줘	뀨읭(124.28)	11.10.04	120	0
277796	형들 WINHTTP를통해서 헤더PHPSESSID적용하려면어떻게해야하나요? [3]	uxp	11.10.04	76	0
277794	C++ 도 폼을 볼수있나요? [1]	박구	11.10.04	74	0
277792	고작한시반인데 정전인척하는거야??? [1]	김호도	11.10.04	36	0
277791	데이터마이닝에서 .. nearest neighbor 알고리즘말인데....	김호도	11.10.04	48	0
277790	좋은 아버지 짤 정했어 [10]	좋은아버지	11.10.04	179	0
277789	내일 과제 제출이냨ㅋㅋㅋ 조공 존나 많네	로하로하알로하	11.10.04	73	0
뉴스	‘한끼합쇼’ 김희선, 얼굴 벌게질 때까지 띵동! 첫 실패도 박수 받는 폭염 투혼! 이것이 ‘그녀의 품격’!	디시트렌드	10:00