Queue
ํ(Queue)
ํ์ชฝ ๋์์๋ง ์๋ฃ๋ฅผ ๋ฃ๊ณ ๋ค๋ฅธ ํ์ชฝ ๋์์๋ง ๋บ ์ ์๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
FIFO(First In First Out)๋จผ์ ๋ฃ์ ๊ฒ์ด ๊ฐ์ฅ ๋จผ์ ๋์จ๋ค.
์๋ฎฌ๋ ์ด์ ์ ๋๊ธฐ์ด(๊ณตํญ์์ ๋นํ๊ธฐ, ์ํ์์์ ๋๊ธฐ์ด)
ํต์ ์์์ ๋ฐ์ดํฐ ํจํท๋ค์ ๋ชจ๋ธ๋ง
ํ๋ฆฐํฐ์ ์ปดํจํฐ ์ฌ์ด์ ๋ฒํผ๋ง

์ฐ์ฐ
์ค๋ช
push / enQueue
ํ์ ์๋ฃ๋ฅผ ๋ฃ๋ ์ฐ์ฐ
pop / deQueue
ํ์์ ์๋ฃ๋ฅผ ๋นผ๋ ์ฐ์ฐ
front
ํ์ ๊ฐ์ฅ ์์ ์๋ ์๋ฃ๋ฅผ ๋ณด๋ ์ฐ์ฐ
back / rear
ํ์ ๊ฐ์ฅ ๋ค์ ์๋ ์๋ฃ๋ฅผ ๋ณด๋ ์ฐ์ฐ
empty
ํ๊ฐ ๋น์ด์๋์ง ์๋์ง๋ฅผ ์์๋ณด๋ ์ฐ์ฐ
size
ํ์ ์ ์ฅ๋์ด์๋ ์๋ฃ์ ๊ฐ์๋ฅผ ์์๋ณด๋ ์ฐ์ฐ
๋ฐฐ์ด
์ ํ ํ
1์ฐจ์ ๋ฐฐ์ด๋ก ๊ตฌํ์ด ์ฝ์ง๋ง, ์ฝ์ ์ ์๋ฃ์ ์ด๋์ด ๋ง๋ค.
์ํ ์ธ์์ ์ค๋ฅ๊ฐ ๋ฐ์ํ๊ณ ๋นํจ์จ์ ์ด๋ค. ๊ฑฐ์ ์ฌ์ฉํ์ง ์๋๋ค.
์ข ๋ฅ
์ฝ์ ์์น
์ญ์ ์์น
์์ฐจ ํ
rear = rear+1
front = front+1
์ด๊ธฐ์ํ : front = rear = -1
๊ณต๋ฐฑ์ํ : front = rear
ํฌํ์ํ : rear = n-1
์์ฐจ ํ๋ ๋์ค์ ๊ณต๊ฐ์ด ๋น์ด์๋๋ฐ ์ฌ์ฉํ์ง ๋ชปํ๋ ๊ฒฝ์ฐ๊ฐ ๋ฐ์ํ๋ค.
#include <iostream>
#include <string>
using namespace std;
struct Queue {
int data[10000];
int begin, end;
Queue() {
begin = 0;
end = 0;
}
void push(int num) {
data[end] = num;
end += 1;
}
bool empty() {
if (begin == end) {
return true;
} else {
return false;
}
}
int size() {
return end - begin;
}
int front() {
return data[begin];
}
int back() {
return data[end-1];
}
int pop() {
if (empty()) {
return -1;
}
begin += 1;
return data[begin-1];
}
};
int main() {
int n;
cin >> n;
Queue q;
while (n--) {
string cmd;
cin >> cmd;
if (cmd == "push") {
int num;
cin >> num;
q.push(num);
} else if (cmd == "pop") {
if (q.empty()) {
cout << -1 << '\n';
} else {
cout << q.front() << '\n';
q.pop();
}
} else if (cmd == "size") {
cout << q.size() << '\n';
} else if (cmd == "empty") {
cout << q.empty() << '\n';
} else if (cmd == "front") {
if (q.empty()) {
cout << -1 << '\n';
} else {
cout << q.front() << '\n';
}
} else if (cmd == "back") {
if (q.empty()) {
cout << -1 << '\n';
} else {
cout << q.back() << '\n';
}
}
}
return 0;
}
์ํ ํ
๋ ผ๋ฆฌ์ ์ผ๋ก ๋จธ๋ฆฌ์ ๊ผฌ๋ฆฌ๊ฐ ์ฐ๊ฒฐ๋์ด์๋ค๊ณ ๊ฐ์ ํ๋ค.
์ข ๋ฅ
์ฝ์ ์์น
์ญ์ ์์น
์ํํ
rear = (rear+1)mod n
front = (front+1) mod n
์ด๊ธฐ ๊ณต๋ฐฑ ์ํ : front = rear = 0
ํฌํ์ํ : ๋๋จธ์ง ์ฐ์ฐ์๋ฅผ ์ด์ฉํด์ ๊ตฌํ๋ค.
(rear+1)%n = front
void push(int num) {
data[end] = num;
end = (end+1)%MAX_QUEUE;
}
bool full() {
if (begin == (end+1)%MAX_QUEUE) {
return true;
} else {
return false;
}
}
int pop() {
if (empty()) {
return -1;
}
begin = (begin+1)%MAX_QUEUE;
return data[begin-1];
}
์ฐ๊ฒฐ๋ฆฌ์คํธ
[04. List]์ ๋จ์์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ฐธ๊ณ ํ์ฌ ๊ตฌํํ๋ฉด๋๋ค.
// queue.h
#ifndef queue_h
#define queue_h
#include <stdio.h>
#include <stdlib.h>
#include "position.h"
typedef struct node{
int data;
struct que * next;
}QNode;
typedef struct que{
QNode * front, * rear;
}Queue;
void enQueue(Queue * q,int data);
void deQueue(Queue * q,int data);
int front(Queue *queue);
int rear(Queue *queue);
int is_empty(Queue *queue);
Queue * creat_queue();
QNode * new_node(int data);
#endif /* queue_h */
// queue.c
#include "queue.h"
QNode * new_node(int data){
QNode * new = (QNode *)malloc(sizeof(QNode));
new->data = data;
new->next=NULL;
return new;
}
Queue * creat_queue(){
Queue * new = (Queue *)malloc(sizeof(Queue));
new->front=new->rear=NULL;
return new;
}
int is_empty(Queue *q){
return (q->front==NULL && q->rear==NULL);
}
int front(Queue *q){
if(is_empty(q)) return -1;
else return q->front->data;
}
int rear(Queue *q){
if(is_empty(q)) return -1;
else return q->rear->data;
}
//front ํฌ์ธํฐ๋ ์ญ์ , rear ํฌ์ธํฐ๋ ์ฝ์
ํ ๋ ์ฌ์ฉ
void enQueue(Queue * q,int data){
QNode * tmp = new_node(data);
if(q->rear==NULL){
q->front = q->rear = tmp;
return;
}
q->rear->next= tmp;
q->rear=tmp;
}
void deQueue(Queue * q,int data){
if(q->front==NULL){
return;
}
q->front = q->front->next;
if(q->front==NULL) q->rear=NULL;
}
<queue>
๋ผ์ด๋ธ๋ฌ๋ฆฌ
<queue>
๋ผ์ด๋ธ๋ฌ๋ฆฌ#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
queue<int> q;
while (n--) {
string cmd;
cin >> cmd;
if (cmd == "push") {
int num;
cin >> num;
q.push(num);
} else if (cmd == "pop") {
if (q.empty()) {
cout << -1 << '\n';
} else {
cout << q.front() << '\n';
q.pop();
}
} else if (cmd == "size") {
cout << q.size() << '\n';
} else if (cmd == "empty") {
cout << q.empty() << '\n';
} else if (cmd == "front") {
if (q.empty()) {
cout << -1 << '\n';
} else {
cout << q.front() << '\n';
}
} else if (cmd == "back") {
if (q.empty()) {
cout << -1 << '\n';
} else {
cout << q.back() << '\n';
}
}
}
return 0;
}
์ค์ต
์กฐ์ธํผ์ค ๋ฌธ์
1๋ฒ๋ถํฐ N๋ฒ๊น์ง N๋ช ์ ์ฌ๋์ด ์์ ์ด๋ฃจ๋ฉด์ ์์์๋๋ค.
์์ ์ ์ M(<=N)์ด ์ฃผ์ด์ง๋ค.
์์๋๋ก M๋ฒ์งธ ์ฌ๋์ ์ ๊ฑฐํ๋ค.
์ด๊ณผ์ ์ N๋ช ์ ์ฌ๋์ด ๋ชจ๋ ์ ๊ฑฐ๋ ๋๊น์ง ๊ณ์ํ๋ค.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main(){
int n,m,cnt=0;
scanf("%d %d",&n,&m);
queue<int> q;
for(int i=0;i<n;i++){
q.push(i+1);
}
while(!q.empty()){
for(int i =0;i<m-1;i++){
q.push(q.front());
q.pop();
}
cout << q.front();
q.pop();
}
}
๋ฑ(Deque)
์ ๋์์๋ง ์๋ฃ๋ฅผ ๋ฃ๊ณ ์ ๋์์ ๋บ ์ ์๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. Double-ended queue์ ์ฝ์์ด๋ค.
์ฐ์ฐ
์ค๋ช
push_front
๋ฑ์ ์์ ์๋ฃ๋ฅผ ๋ฃ๋ ์ฐ์ฐ
push_back
๋ฑ์ ๋ค์ ์๋ฃ๋ฅผ ๋ฃ๋ ์ฐ์ฐ
pop_front
๋ฑ์ ์์์ ์๋ฃ๋ฅผ ๋นผ๋ ์ฐ์ฐ
pop_back
๋ฑ์ ๋ค์์ ์๋ฃ๋ฅผ ๋นผ๋ ์ฐ์ฐ
front
ํ์ ๊ฐ์ฅ ์์ ์๋ ์๋ฃ๋ฅผ ๋ณด๋ ์ฐ์ฐ
back
ํ์ ๊ฐ์ฅ ๋ค์ ์๋ ์๋ฃ๋ฅผ ๋ณด๋ ์ฐ์ฐ
empty
ํ๊ฐ ๋น์ด์๋์ง ์๋์ง๋ฅผ ์์๋ณด๋ ์ฐ์ฐ
size
ํ์ ์ ์ฅ๋์ด์๋ ์๋ฃ์ ๊ฐ์๋ฅผ ์์๋ณด๋ ์ฐ์ฐ
์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ
์์ชฝ์์ ์ฝ์ , ์ญ์ ๊ฐ ๊ฐ๋ฅํ์ฌ์ผ ํ๋ฏ๋ก ์ผ๋ฐ์ ์ผ๋ก ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ๋ค.
[04. List]์ ์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ฐธ๊ณ ํ์ฌ ๊ตฌํํ๋ฉด๋๋ค.
<deque>
๋ผ์ด๋ธ๋ฌ๋ฆฌ
<deque>
๋ผ์ด๋ธ๋ฌ๋ฆฌ#include <iostream>
#include <string>
#include <deque>
using namespace std;
int main(){
int n;
cin >> n;
deque<int> dq;
while(n--){
string m;
cin >> m;
if(m=="push_front"){
int x;
scanf("%d",&x);
dq.push_front(x);
}else if(m=="push_back"){
int x;
scanf("%d",&x);
dq.push_back(x);
}else if(m=="pop_front"){
if(!dq.empty()){
cout << dq.front()<<"\n";
dq.pop_front();
}else{
cout << -1<<"\n";
}
}else if(m=="pop_back"){
if(!dq.empty()){
cout << dq.back()<<"\n";
dq.pop_back();
}else{
cout << -1<<"\n";
}
}else if(m=="size"){
cout << dq.size()<<"\n";
}else if (m=="empty"){
cout << dq.empty()<<"\n";
}else if(m=="front"){
if(dq.empty()){
cout << -1<<"\n";
}else{
cout << dq.front()<<"\n";
}
}else if(m=="back"){
if(dq.empty()){
cout << -1<<"\n";
}else{
cout << dq.back()<<"\n";
}
}
}
}
from collections import deque
# python์์ depue๋ผ์ด๋ธ๋ฌ๋ฆฌ ์ฌ์ฉํด Queue ๊ตฌํ ๊ฐ๋ฅ
queue = deque()
queue.append(5)
queue.append(3)
queue.popleft()
ํ์ด์ฌ์ผ๋ก ํ๋ฅผ ๊ตฌํํ ๋๋ collections
๋ชจ๋์์ ์ ๊ณตํ๋ deque์๋ฃ๊ตฌ์กฐ๋ฅผ ํ์ฉํ๋ ๊ฒ์ด ์ข๋ค. ๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ ๋นผ๋ ์๋๊ฐ ๋ฆฌ์คํธ ์๋ฃํ์ ๋นํด ํจ์จ์ ์ด๋ฉฐ, queue๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ์ด์ฉํ๋ ๊ฒ๋ณด๋ค ๋ ๊ฐ๋จํ๋ค.
Last updated
Was this helpful?