선형 큐, 환형 큐

laoshanlong

2011.09.24 11:06:22

조회 254 추천 0 댓글 1

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

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

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

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

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

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

고정닉 0

전체 댓글 0개

등록순

본문 보기

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

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	가족과 완벽하게 손절해야 할 것 같은 스타는?	운영자	24/06/24	-	-
공지	프로그래밍 갤러리 이용 안내 [71]	운영자	20.09.28	35878	62
2717934	코드 스타일 같은거 이해 안 되는데	프갤러(110.10)	04:11	1	0
2717933	경력 개발자 계약직 질문좀 [5]	프갤러(220.116)	03:51	18	0
2717932	어디게	B0@(117.111)	03:33	11	0
2717928	인스타그램 추천	발명도둑잡기	02:43	17	0
2717927	여기가 ㅈ병신갤이 이유는 발전이라는게 없음 [1]	ㅇㅇ(122.42)	02:40	33	0
2717926	그 사람이 제발	프갤러(211.112)	02:40	17	1
2717923	'27년 국정원출신' 정치인 "서울 심장부 광화문광장에 '이것'	발명도둑잡기	02:35	14	0
2717920	음기 충전	발명도둑잡기	02:18	25	0
2717919	박스 줍는 노인 입갤이요 ㅇㅅㅇ	ㅇㅅㅇ(106.102)	02:16	9	0
2717918	개발 10년차가 돼도 [1]	ㅇㅇ(223.38)	02:16	49	2
2717917	보도방 뻥튀기만 3년 다녔는데 연봉 안오름 [1]	프갤러(211.36)	02:13	35	0
2717916	인스타그램 새로고침 후 첫 추천	발명도둑잡기	02:01	25	0
2717913	조은 이분 패캠 강의 어떰 ?? [2]	프갤러(59.5)	01:35	27	0
2717912	시장이나 대통령 모가지를 광화문에 걸어라	발명도둑잡기	01:14	18	0
2717911	냥덩이 올린 게시물 "ㅁㅅ"	발명도둑잡기	01:06	21	0
2717910	Opgg 앱 뭘로 만든건임?? [2]	프갤러(116.121)	01:03	64	0
2717909	인스타그램 추천 저장 눌렀는데 저장 안됐다	발명도둑잡기	01:03	14	0
2717906	<태극기 휘날리며> 글 올린 후 내 방 노트북 인터넷이	발명도둑잡기	00:47	18	0
2717904	내 책상사진임 [1]	프갤러(14.39)	00:40	38	0
2717903	백준티어 믿을게 못되네 [1]	ㅇㅇ(125.241)	00:36	60	0
2717902	접거나 마는 스크린	발명도둑잡기	00:25	18	0
2717901	나님 찐막담	♥냥덩Pay♥	00:22	25	0
2717900	자신이 바보인지 아닌지 체크하는 확실한 방법	영혼추수	00:18	37	0
2717899	내적 동기 부여가 쉽지 않노 ㅇㅅㅇ	포항의봄	00:08	19	0
2717898	와 dlux8 나오내	♥냥덩Pay♥	00:06	21	0
2717896	나도 오타쿠나 될까 ㅇㅅㅇ	포항의봄	06.25	25	0
2717895	나님 넘나 순수행..❤+	♥냥덩Pay♥	06.25	17	0
2717894	후임이고 프리고 다 필요없다	포항의봄	06.25	26	0
2717893	개표방송 레전드	♥냥덩Pay♥	06.25	22	0
2717892	방금 전 인스타그램 첫 화면 [1]	발명도둑잡기	06.25	46	0
2717891	속보) 김포프 실성	♥냥덩Pay♥	06.25	53	0
2717890	지금 메서드 새로 만드는데 if에 조건 존나 거는중 ㅇㅅㅇ [2]	포항의봄	06.25	51	0
2717889	서태지와 아이들-발해를 꿈꾸며(Dreaming of Bal-Hae)	발명도둑잡기	06.25	12	0
2717888	내가 웹사이트만들면 그냥 해줄수도있는데 [5]	트렌더	06.25	58	1
2717887	모기새끼가 손가락 마디 물어서 너무 불편해 [2]	♥냥덩Pay♥	06.25	34	0
2717886	콘서트장 폭우, 알고 보니...관중들 '격분'	발명도둑잡기	06.25	15	0
2717883	수천억을 가져다 줄 미친 아이디어 앱을 생각해냈다.. [9]	딘퐁	06.25	64	0
2717882	시발 무슨 갤이 이렇노	유앤유	06.25	38	0
2717881	요새 자프링단많이없어졌네 ㅇㅅㅇ [1]	트렌더	06.25	46	0
2717879	컴공도 학력따짐? [1]	ㅇㅇ8	06.25	57	0
2717877	오늘 대구에서 6·25전쟁 74주년 행사...첫 지방 개최	발명도둑잡기	06.25	12	0
2717876	진짜 vba 죽여버리고싶다 [1]	Pack	06.25	35	0
2717875	오빠야들 나랑노라 ㅇㅅㅇ [3]	트렌더	06.25	34	0
2717874	C#은 비벼볼만 하겠지	프갤러(183.101)	06.25	28	0
2717873	ㅁㅅ	♥냥덩Pay♥	06.25	20	0
2717872	국비 듣다가 때려치고 창업준비중임 그리고 웹개발 외주하는데 [23]	비결경	06.25	123	1
2717871	모바일 앱 개발하려면 램 많이 필요해? [2]	프갤러(221.167)	06.25	28	0
2717870	더이상의 개발자 교육을 금지하고, 컴공과를 폐지해야 한다 [4]	ㅇㅇ(106.101)	06.25	68	1
2717867	망국 정치에서 탈출하는 비상구 진보당-민주노총	발명도둑잡기	06.25	10	0