<div id="readability-page-1" class="page"><div><h2 id="큐"><a href="#%ED%81%90" aria-label="큐 permalink"></a>큐</h2>
먼저 집어넣은 데이터가 먼저 나오는 자료구조
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/1920px-Data_Queue.svg.png" alt="https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/1920px-Data_Queue.svg.png">
<h2 id="구현"><a href="#%EA%B5%AC%ED%98%84" aria-label="구현 permalink"></a>구현</h2>
by 배열
<ul>
<li>FIFO(First In First Out)</li>
<li>원소 추가, 제거 : O(1)</li>
<li>제일 앞, 뒤 원소 확인 : O(1)</li>
<li>맨 앞뒤 원소 제외 나머지 원소 확인, 변경 원칙적으로 불가능</li>
</ul>
<div data-language="cpp"><pre><code>const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;</code></pre></div>
제일 앞의 원소를 없앤다고 가정할 때, 원소를 다른 값으로 덮는 것이 아닌 head를 증가시킨다.
큐의 원소가 들어있는 자리 
<ul>
<li>dat[head] ~ dat[tail - 1]</li>
</ul>
큐의 크기
<ul>
<li>tail - head</li>
</ul>
배열로 구현했을 때 문제 : 삭제할 때 마다 쓸모없는 공간이 생김
→ 해결 : 원형 큐 (Circular Queue)
<h2 id="원형-큐circular-queue"><a href="#%EC%9B%90%ED%98%95-%ED%81%90circular-queue" aria-label="원형 큐circular queue permalink"></a>원형 큐(Circular Queue)</h2>
<img src="https://cdn.programiz.com/sites/tutorial2program/files/circular-increment.png" alt="https://cdn.programiz.com/sites/tutorial2program/files/circular-increment.png">
<h2 id="구현-1"><a href="#%EA%B5%AC%ED%98%84-1" aria-label="구현 1 permalink"></a>구현</h2>
head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 만든다
<div data-language="cpp"><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x) {
	dat[tail++] = x;
}
void pop() {
	head++;
}
int front() {
	return dat[head];
}
int back() {
	return dat[tail-1];
}</code></pre></div>
<h2 id="stl-queue"><a href="#stl-queue" aria-label="stl queue permalink"></a>STL Queue</h2>
<div data-language="cpp"><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;

int main(void) {
	queue&lt;int&gt; q;
	q.push(10);
	cout &lt;&lt; q.size();
	q.pop();
	cout &lt;&lt; q.front() &lt;&lt; " " &lt;&lt; q.back();
 }</code></pre></div></div></div>

Seulog💘

이예슬

큐
먼저 집어넣은 데이터가 먼저 나오는 자료구조
구현
by 배열
FIFO(First In First Out)
원소 추가, 제거 : O(1)
제일 앞, 뒤 원소 확인 : O(1)
맨 앞뒤 원소 제외 나머지 원소 확인, 변경 원칙적으로 불가능
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;
제일 앞의 원소를 없앤다고 가정할 때, 원소를 다른 값으로 덮는 것이 아닌 head를 증가시킨다.
큐의 원소가 들어있는 자리 
dat[head] ~ dat[tail - 1]
큐의 크기
tail - head
배열로 구현했을 때 문제 : 삭제할 때 마다 쓸모없는 공간이 생김
→ 해결 : 원형 큐 (Circular Queue)
원형 큐(Circular Queue)
구현
head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 만든다
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;
void push(int x) {
	dat[tail++] = x;
}
void pop() {
	head++;
}
int front() {
	return dat[head];
}
int back() {
	return dat[tail-1];
}
STL Queue
#include <bits/stdc++.h>
using namespace std;
int main(void) {
	queue<int> q;
	q.push(10);
	cout << q.size();
	q.pop();
	cout << q.front() << " " << q.back();
 }

Queue

댓글