자료구조 Queue(큐)
위키백과
Queue (영어단어 : 대기 줄)
기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다.
먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.
나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.
Enqueue : 데이터를 넣는다
Dequeue : 큐에서 제거하고 데이터를 가져온다
Peek : 큐에서 제거하지 않고 데이터를 가져온다
Count : 큐에있는 데이터의 갯수를 가져온다
head와 tail는 데이터의 위치를 가리킨다!
head는 데이터를 Dequeue할 수 있는 위치를,
tail은 데이터를 Enqueue할 수 있는 위치를 의미한다
큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우를 언더플로우(Underflow)라고 한다.
큐가 비어 있는 경우 InvalidOperationException
1.Enqueue
큐가 비어있을 때 경우, 비어있지 않을 경우
(1)알고리즘
2.순서도(코드)
-데이터 삽입을 안함
-새 노드를 만들고 맴버변수 삽임을 안함.
-새 노드를 생성하고, 또 생성해버림.
2.순서도(수정)
3.코드화
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Helloworld1
{
class Queue
{
public Node tail;
public Node head;
//생성자
public Queue()
{
}
public void Enqueue(int data)
{
Node node = new Node(data);
if (this.head == null)
{
this.head = new Node(data);
this.tail = head;
return;
}
else
{
this.tail.next = new Node(data);
this.tail = this.tail.next;
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Helloworld1
{
class Node
{
public int data;
public Node next;
//생성자
public Node(int data)
{
this.data = data;
}
}
}
2.Dequeue(순서도-1개이상일때, 2개이상일때 수정하기)
큐가 비어있을 경우, 비어있지 않은 경우
1.알고리즘
2.순서도(코드화)
3.코드화
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Helloworld1
{
class App
{
public App()
{
Queue queue = new Queue();
queue.Enqueue(3);
queue.Enqueue(5);
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Helloworld1
{
class Queue
{
public Node tail;
public Node head;
public int data;
public Node temp;
//생성자
public Queue()
{
}
public void Enqueue(int data)
{
Node node = new Node(data);
if (this.head == null)
{
this.head = new Node(data);
this.tail = head;
return;
}
else
{
this.tail.next = new Node(data);
this.tail = this.tail.next;
}
}
public int Dequeue()
{
if(this.head == null)
{
throw new InvalidOperationException();
}
else
{
int data = this.head.data;
head = head.next;
if(this.head == null)
{
this.tail = null;
this.head = null;
}
return data;
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Helloworld1
{
class Node
{
public int data;
public Node next;
//생성자
public Node(int data)
{
this.data = data;
}
}
}
3.Peek
큐가 비어있을 경우, 비어있지 않을 경우
(1)알고리즘
2.순서도(코드화)
3.코드화
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Helloworld1
{
class Queue
{
public Node tail;
public Node head;
public int data;
public Node temp;
//생성자
public Queue()
{
}
public void Enqueue(int data)
{
Node node = new Node(data);
if (this.head == null)
{
this.head = new Node(data);
this.tail = head;
return;
}
else
{
this.tail.next = new Node(data);
this.tail = this.tail.next;
}
}
public int Dequeue()
{
if(this.head == null)
{
throw new InvalidOperationException();
}
else
{
int data = this.head.data;
head = head.next;
if(this.head == null)
{
this.tail = null;
this.head = null;
}
return data;
}
}
public int Peek()
{
if(this.head == null)
{
throw new InvalidOperationException();
}
return head.data;
}
}
}
4.Count
큐에 있는 노드 카운트 세기
1.알고리즘
2.순서도(코드화)
3.코드화