record logo record

DataStructure

큐(Queue)

update: 22 July 2019

큐(Queue) 란?

큐(Queue)의 용도

큐(Queue)의 특징

큐(Queue)의 성질

큐(Queue)의 알고리즘 예시

C 언어를 이용한 Queue 구현

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	int data;
	Node *next;
} Node;

typedef struct Queue {
	Node *front;
	Node *rear;
	int len;
} Queue;

void put(Queue *q, int data) {
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = q->rear;
	
	if(q->len == 0) {
		q->front = q->rear = node;
	} else {
		q->rear->next = node;
		q->rear = q->rear->next;
	}
	q->len++;
}
int get(Queue *q) {
	if(q->front == NULL) {
		printf("UnderFlow\n");
		return -1;
	}
	Node *node = q->front;
	int data = node->data;
	q->front = node->next;
	free(node);
	q->len--;
	return data;
}

void show(Queue *q) {
	printf("\n----show----\n");
	int lentmp = q->len;
	Node *node = q->front;
	while(lentmp > 0) {
		printf("%d ",node->data);
		node = node->next;
		lentmp--;
	}
}

int main(void) {
	Queue q;
	q.front = NULL;
	q.rear = NULL;
	q.len = 0;
	
	put(&q, 1);
	put(&q, 2);
	put(&q, 3);
	put(&q, 4);
	show(&q);
	get(&q);
	show(&q);
	return 0;
}

Java 언어를 이용한 Queue 구현

public class myqueue {
	
	public static class Node {
		private Object data;
		private Node next;
		
		public Node(Object data) {
			this.data = data;
			this.next = null;
		}
		
	}
	private Node front;
	private Node rear;
	int len = 0;
	
	public void put(Object data) {
		Node node = new Node(data);
		
		if(len == 0) {
			front = node;
			rear = node;
			
		} else {
			rear.next = node;
			rear = rear.next;
		}
		len++;
	}
	
	public Object get() {
		if(front == null) {
			System.out.println("UnderFlow");
			return -1;
		}
		Object data = front.data;
		front = front.next;
		
		return data;
	}
	public Object peak() {
		Object data = front.data;
		
		return data;
	}
	public void show() {
		System.out.println("----show----");
		Node node = front;
		while(node!=null) {
			System.out.println(node.data);
			node = node.next;
		}
	}
	
}

C++ 배열을 이용한 큐 구현

// #include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define ll long long

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];
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    push(1);
    push(2);
    push(3);

    cout << front();
    return 0;
}

C++ STL Library를 사용한 Queue 구현

#include <iostream>
#include <queue>
using namespace std;

int main(void){
	queue<int> q;
	
	q.push(8);
	q.push(7);
	q.push(6);
	q.pop();
	q.push(5);
	q.pop();
	
	while(!q.empty()){
		cout << q.front() << ' ';
		q.pop();
	}
	return 0;
}

References