현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

원형 큐 구현

읏짜의 이미지
글쓴이: 읏짜 / 작성시간: 수, 2021/09/08 - 3:57오후

원형 큐 구현할 때 front, rear 변수를 보통 int타입으로 선언해서 인덱스 접근을 하는데 front, rear를 포인터 변수로 선언해서 사용할 수 있나요?

Forums: 
프로그래밍 QnA
swish95의 이미지

글쓴이: swish95 / 작성시간: 목, 2021/09/09 - 8:11오전

원형 큐면 라운드 로빈 방식인가요?
int 혹은 포인트 인가는 문제가 없지 싶은데요?

------------------------------------------------------------
ProgrammingHolic

읏짜의 이미지

글쓴이: 읏짜 / 작성시간: 목, 2021/09/09 - 10:25오전

아래 링크처럼 구현을 했는데요,
https://blog.naver.com/sooftware/221512458414
front, rear를 포인터 변수로 사용하게 되면
enqueue, dequeue했을 때 rear, front를 이동시켜주는 걸 어떻게 표현해야 될까요?

나빌레라의 이미지

글쓴이: 나빌레라 / 작성시간: 목, 2021/09/09 - 11:33오전

해당 링크 예제처럼 배열을 기반으로 하면서 circular queue를 구현했을 때, front, rear를 굳이 포인터로 사용할 이유는 없습니다. 못할건 없는데 구현이 더 복잡해 집니다. 배열의 각 item 포인터를 따로 저장해서 끝에 닿았을 때 맨앞에 해당하는 포인터로 바꿔주는등의 코드를 추가해야 하거든요. 간단히 mod 연산만 하면 되는 방식 대비 이득이 없습니다.

구조체를 기반으로 해서 linked list로 circular quque를 만들어야 front, rear를 포인터로 쓰는게 의미있는 일이 됩니다.

----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라

swish95의 이미지

글쓴이: swish95 / 작성시간: 목, 2021/09/09 - 12:04오후

저는 단순히 해당 변수만 포인터로 만든다는 뜻인줄 알았네요

이걸 굳이 연결 리스트로 만들 이유가 없고 만든다면 front, rear 형태가 아니라
연결리스트의 크기를 조절하는, 그러니까 리스트 자체를 넣고 빼고 하는 식으로 해야 되는데
나빌레라님 댓글 처럼 하등 이익이 없습니다.

------------------------------------------------------------
ProgrammingHolic

라스코니의 이미지

글쓴이: 라스코니 / 작성시간: 목, 2021/09/09 - 12:56오후

차이가 없습니다. 어짜피 item의 길이만큼 옮겨 다니기 때문에 sizeof(item) 길이만 잘 처리해 주면 됩니다.
무조건 BASE는 포인터일텐데 FRONT, REAR가 포인터여도 차이가 없죠.

1) FRONT, REAR가 int 변수일 때
___new position of FRONT <- FRONT + i, 실제 FRONT 주소 <- BASE + (new FRONT) * sizeof(item)

2) FRONT, REAR가 포인터일 때
___new position of FRONT <- FRONT + i * sizeof(item), 실제 주소값임으로 그대로 액세스하면 됨

나빌레라의 이미지

글쓴이: 나빌레라 / 작성시간: 금, 2021/09/10 - 5:55오전

아! 그렇군요.
맞네요. 배열이니까 시작 주소 가져다가 포인터로 잡고 그냥 똑같이 하면 되네요..ㅎㅎ
배열 자체를 너무 리스트처럼 생각했나봅니다.

----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라

라스코니의 이미지

글쓴이: 라스코니 / 작성시간: 금, 2021/09/10 - 8:23오전

네. 맞습니다. 원형큐는 단일 리스트에서 중간 삽입, 삭제 같은 고급스러운 기능이 없기 때문에 이렇게 가능합니다.

Anti-Lock의 이미지

글쓴이: Anti-Lock / 작성시간: 금, 2021/09/10 - 3:19오후

"차이가 없습니다. 어짜피 item의 길이만큼 옮겨 다니기 때문에 sizeof(item) 길이만 잘 처리해 주면 됩니다."

그렇죠. 불가능한것은 없습니다.

그러나, 'FRONT, REAR가 포인터일 때'는 해당 포인터 타입이 무엇인지에 따라 처리해야 합니다.
FRONT, REAR가 'void *' 혹은 'char *' 타입 이라고 한다면, 예시하여 주신 코드가 맞겠으나,
FRONT, REAR가 'item *' 타입이라고 한다면, sizeof(item)을 곱하여 줄 필요가 없을 것 같습니다.
...
그렇죠. 실수하지 않고 해야합니다.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.