wiki/큐(자료구조).md

---
title: 큐(Queue)
description: 자료 구조 큐
published: true
date: 2020-09-22T08:12:23.058Z
tags: 컴퓨터
editor: markdown
dateCreated: 2020-09-22T07:25:17.866Z
---

# 큐(Queue)

FIFO(first in, first out)

```rust
trait Queue<T>{
  fn enqueue(&mut self,e: T) -> Result<()>;
  fn dequeue(&mut self) -> Result<T>;
  fn is_empty() -> bool;
  fn peek(&mut self) -> Result<&mut T>;
  fn size(&self) -> usize;
}
```

## 선형큐(linear queue)
```diagram
PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHhtbG5zOnhsaW5rPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5L3hsaW5rIiB2ZXJzaW9uPSIxLjEiIHdpZHRoPSIzMjFweCIgaGVpZ2h0PSIxNTFweCIgdmlld0JveD0iLTAuNSAtMC41IDMyMSAxNTEiIGNvbnRlbnQ9IiZsdDtteGZpbGUgaG9zdD0mcXVvdDtlbWJlZC5kaWFncmFtcy5uZXQmcXVvdDsgbW9kaWZpZWQ9JnF1b3Q7MjAyMC0wOS0yMlQwNzozNjo1OS41MTlaJnF1b3Q7IGFnZW50PSZxdW90OzUuMCAoV2luZG93cykmcXVvdDsgdmVyc2lvbj0mcXVvdDsxMy43LjMmcXVvdDsgZXRhZz0mcXVvdDtoeEhELTE3WVY2ZktkNklYSmoyQyZxdW90OyB0eXBlPSZxdW90O2VtYmVkJnF1b3Q7Jmd0OyZsdDtkaWFncmFtIGlkPSZxdW90O09LRUdfVjE4cld2NVFBSW5zaGt5JnF1b3Q7IG5hbWU9JnF1b3Q7UGFnZS0xJnF1b3Q7Jmd0OzNWZkxqdE13RlAyYUxFRjVOZE5aOWpFREd5UkVGOERTaW04VEN5Y09qdE9tZkQzWHRkMDhDeU1RbldHa1NyV1A3V3VmYzV4N0V5L2FGTzA3U2FyOGc2REF2ZENuclJkdHZUQU00akQwOU0rbko0TXN3NFVCTXNtb25kUUJPL1lETE9oYnRHRVU2c0ZFSlFSWHJCcUNxU2hMU05VQUkxS0s0M0RhWHZEaHJoWEpZQUxzVXNLbjZHZEdWZTVZM0hYNGUyQlo3bllPa25zelVoQTMyVEtwYzBMRnNRZEZEMTYwa1VJbzB5cmFEWEF0bnRQRnJIdThNbm81bUlSU1BXV0JOZUpBZUdPNTJYT3BreU43ekptQ1hVVlMzVCtpb1Y2MHpsWEJzUmRnazlTVmtYalBXc0NvYXhzUnBJTDI2cW1DQzFlOEpDQUtVUEtFVTQ0OU5hMUNlVTlJaHhIclgzWloyVkhFaG1VNXp6aWFZWnh3M0dDOUYzaTZQdlhrZXlQY3dKdjZmQXRYT0NHTXE3WWJ4RmFtL3dNWEJnOWdJaG44V2ZWc2g3cmRRTjc0SDhrYnZXQjVnK1IyK2k1ZTFnTnJGNFR4N1JSSWZxOEFadFZLTi9jYzJwWE85OGdTU21xYjI1U1R1bWJwVUJaa0trOWZzT08vWGJqdTEvN1lWblAxTDcyVDdabk5nVTRxeGtnN0xGRkVacUI2ZWZlWCtXOHhJNS9ESkhDaTJHRzQ0NXltZG9lUGdwMmZQZXVXTTh0VzN5QWN1VktMUnFaZ0YvV0x4empPS0ZBVWpBSVp4cE5BWjRjdnJKOWsrdDFyTUQxK1R0TkQvLzl6ZlRseC9aSEpXazJzeDhTbGhzYldTb3B2c0JGY1NFUktVWUl1Tkl6ekVVUTR5MHA5TzlBM1FIeXQweURETjcyVkhTZ1lwWHFiOVZ4V2xhSXBxYzZodlV2eGQzbDA1RkUwVGF2eHpCVVpXL2tuYWZYK2F1R203T0NxN1NjZ3NsZUlleU92MTVOZ2VUTlRzTnU5K3B2bnBmdUFpaDUrQWc9PSZsdDsvZGlhZ3JhbSZndDsmbHQ7L214ZmlsZSZndDsiPjxkZWZzLz48Zz48cmVjdCB4PSIwIiB5PSIwIiB3aWR0aD0iODAiIGhlaWdodD0iODAiIGZpbGw9IiNmZmZmZmYiIHN0cm9rZT0iIzAwMDAwMCIgcG9pbnRlci1ldmVudHM9ImFsbCIvPjxyZWN0IHg9IjgwIiB5PSIwIiB3aWR0aD0iODAiIGhlaWdodD0iODAiIGZpbGw9IiNmZmZmZmYiIHN0cm9rZT0iIzAwMDAwMCIgcG9pbnRlci1ldmVudHM9ImFsbCIvPjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKC0wLjUgLTAuNSkiPjxzd2l0Y2g+PGZvcmVpZ25PYmplY3Qgc3R5bGU9Im92ZXJmbG93OiB2aXNpYmxlOyB0ZXh0LWFsaWduOiBsZWZ0OyIgcG9pbnRlci1ldmVudHM9Im5vbmUiIHdpZHRoPSIxMDAlIiBoZWlnaHQ9IjEwMCUiIHJlcXVpcmVkRmVhdHVyZXM9Imh0dHA6Ly93d3cudzMub3JnL1RSL1NWRzExL2ZlYXR1cmUjRXh0ZW5zaWJpbGl0eSI+PGRpdiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94aHRtbCIgc3R5bGU9ImRpc3BsYXk6IGZsZXg7IGFsaWduLWl0ZW1zOiB1bnNhZmUgY2VudGVyOyBqdXN0aWZ5LWNvbnRlbnQ6IHVuc2FmZSBjZW50ZXI7IHdpZHRoOiA3OHB4OyBoZWlnaHQ6IDFweDsgcGFkZGluZy10b3A6IDQwcHg7IG1hcmdpbi1sZWZ0OiA4MXB4OyI+PGRpdiBzdHlsZT0iYm94LXNpemluZzogYm9yZGVyLWJveDsgZm9udC1zaXplOiAwOyB0ZXh0LWFsaWduOiBjZW50ZXI7ICI+PGRpdiBzdHlsZT0iZGlzcGxheTogaW5saW5lLWJsb2NrOyBmb250LXNpemU6IDEycHg7IGZvbnQtZmFtaWx5OiBIZWx2ZXRpY2E7IGNvbG9yOiAjMDAwMDAwOyBsaW5lLWhlaWdodDogMS4yOyBwb2ludGVyLWV2ZW50czogYWxsOyB3aGl0ZS1zcGFjZTogbm9ybWFsOyB3b3JkLXdyYXA6IG5vcm1hbDsgIj48Zm9udCBzdHlsZT0iZm9udC1zaXplOiAyNHB4Ij4xPC9mb250PjwvZGl2PjwvZGl2PjwvZGl2PjwvZm9yZWlnbk9iamVjdD48dGV4dCB4PSIxMjAiIHk9IjQ0IiBmaWxsPSIjMDAwMDAwIiBmb250LWZhbWlseT0iSGVsdmV0aWNhIiBmb250LXNpemU9IjEycHgiIHRleHQtYW5jaG9yPSJtaWRkbGUiPjE8L3RleHQ+PC9zd2l0Y2g+PC9nPjxyZWN0IHg9IjE2MCIgeT0iMCIgd2lkdGg9IjgwIiBoZWlnaHQ9IjgwIiBmaWxsPSIjZmZmZmZmIiBzdHJva2U9IiMwMDAwMDAiIHBvaW50ZXItZXZlbnRzPSJhbGwiLz48ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgtMC41IC0wLjUpIj48c3dpdGNoPjxmb3JlaWduT2JqZWN0IHN0eWxlPSJvdmVyZmxvdzogdmlzaWJsZTsgdGV4dC1hbGlnbjogbGVmdDsiIHBvaW50ZXItZXZlbnRzPSJub25lIiB3aWR0aD0iMTAwJSIgaGVpZ2h0PSIxMDAlIiByZXF1aXJlZEZlYXR1cmVzPSJodHRwOi8vd3d3LnczLm9yZy9UUi9TVkcxMS9mZWF0dXJlI0V4dGVuc2liaWxpdHkiPjxkaXYgeG1sbnM9Imh0dHA6Ly93d3cudzMub3JnLzE5OTkveGh0bWwiIHN0eWxlPSJkaXNwbGF5OiBmbGV4OyBhbGlnbi1pdGVtczogdW5zYWZlIGNlbnRlcjsganVzdGlmeS1jb250ZW50OiB1bnNhZmUgY2VudGVyOyB3aWR0aDogNzhweDsgaGVpZ2h0OiAxcHg7IHBhZGRpbmctdG9wOiA0MHB4OyBtYXJnaW4tbGVmdDogMTYxcHg7Ij48ZGl2IHN0eWxlPSJib3gtc2l6aW5nOiBib3JkZXItYm94OyBmb250LXNpemU6IDA7IHRleHQtYWxpZ246IGNlbnRlcjsgIj48ZGl2IHN0eWxlPSJkaXNwbGF5OiBpbmxpbmUtYmxvY2s7IGZvbnQtc2l6ZTogMTJweDsgZm9udC1mYW1pbHk6IEhlbHZldGljYTsgY29sb3I6ICMwMDAwMDA7IGxpbmUtaGVpZ2h0OiAxLjI7IHBvaW50ZXItZXZlbnRzOiBhbGw7IHdoaXRlLXNwYWNlOiBub3JtYWw7IHdvcmQtd3JhcDogbm9
```

## 원형큐(circular queue)

```diagram
PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHhtbG5zOnhsaW5rPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5L3hsaW5rIiB2ZXJzaW9uPSIxLjEiIHdpZHRoPSIzMTFweCIgaGVpZ2h0PSIyOTFweCIgdmlld0JveD0iLTAuNSAtMC41IDMxMSAyOTEiIGNvbnRlbnQ9IiZsdDtteGZpbGUgaG9zdD0mcXVvdDtlbWJlZC5kaWFncmFtcy5uZXQmcXVvdDsgbW9kaWZpZWQ9JnF1b3Q7MjAyMC0wOS0yMlQwNzo0NTozMi42MTlaJnF1b3Q7IGFnZW50PSZxdW90OzUuMCAoV2luZG93cykmcXVvdDsgZXRhZz0mcXVvdDsyejJBaXVKb1lUQy11UWhXU2lUSyZxdW90OyB2ZXJzaW9uPSZxdW90OzEzLjcuMyZxdW90OyB0eXBlPSZxdW90O2VtYmVkJnF1b3Q7Jmd0OyZsdDtkaWFncmFtIGlkPSZxdW90O2NjM2ZsaUFTamhpb29KTmVXa0taJnF1b3Q7IG5hbWU9JnF1b3Q7UGFnZS0xJnF1b3Q7Jmd0OzNWakprdHNnRVAwYUh6TWxJWGs3ZXBsTUxrbE5sUS9KSENuUmxxaGdvU0JzeS9uNmdJVVdrTGU0N0lrelZUN1FEYlRvOXg3UXVCZk1Wc1dMd0ZueWxSTmdQZVNSb2hmTWV3ajVJVUk5L2ZQSXJ2U01VTDkweElJU002aHhMT2h2TUU3UGVOZVVRRzRObEp3elNUUGJHZkUwaFVoYVBpd0UzOXJEbHB6Wlg4MXdEQjNISXNLczYvMU9pVXlxTElhTi93dlFPS20rN0EvR1pjOEtWNE5OSm5tQ0NkKzJYTUZ6TDVnSnptWFpXaFV6WUJxOENwZHkzdWNqdmZYQ0JLVHlrZ21HaUExbWE1T2JXWmZjVmNtcUNRcFhaVXkzQ1pXd3lIQ2tlN2FLV3VWTDVJb3B5MWRObkdjbDJFdGFnSW8vN1M3R3JHOERRa0xSY3BuRnZRQmZnUlE3TldUYjRJcENBMWJTd3JSMllzTmxYTTl0MGxVTmsvSGg3SU5IemQ3MGpreU9POXRzWVRNNkFNM29Cc2lFNTVGUjBzMTBjOG1nbU9oTnBYS0dsSmptUEdJNHoybGtnM1FVRXlEV2pqdXBoLzZCbkN1ZkFJWWwzZGo3OUJBUTVndXZuS3FWMUlEN1l4dHhOSFN3elBsYVJHQm10ZmVWRzJqb0JBcWNRQktMR0dRbjBKNlhPdTJMcUJwZUlPS0dscFNuWUhNQ0JaVS9XdTIzVm51dTAvRXFZMmVNb3l5VzZGZ25TNW1udGQwZWhPdkE0VHBFVjNJZGhuYWd3QlhON2JnZTNZRnI3Nmwva20xRnN0alZrN1RSbXFYTlp0cmUraXVWQkYyVm9JZFNDWEkyc24rdFNnTGZDZVRmVFNYait4emV0UkM4cC9Gd2JJdGhNQXJPeUdGdnZZS2dLaEVRNXpUeS93Z0NlWTkvYkZSU2F5bGlLV2d1TzdKUWRZbTBTYytsNEQ5aHhoa1h6WW15cEl3NUxzeG9uR3JsS0NZMXZWTmQ1VkJWTWs5TXg0b1N3bzdWVVlLdlU2S3JwdE9xdUx4eTZ0eS93Mjd0ZExDc3ZFSHQ1UHNkdEw4QkZoOFg3TTZXOE44UjdFTXZtQUhUd0JLNlVjMVk3cE1zWFV1KzM0RU5DWU5mYTE1MWZNcjNEODJKR29EQ3JHZzZxeWo5S294YVZCbkpqcTdjMWpjL0t0Kys4eTd4KysvSTl5VnZ0cE1sVUhPTDFSWE1XN3Z2WkRualhFSlgxemYvN1BaeTdweGIxYnloZXd0ZWZYa3BzL243b3h6ZS9Ja1VQUDhCJmx0Oy9kaWFncmFtJmd0OyZsdDsvbXhmaWxlJmd0OyI+PGRlZnMvPjxnPjxlbGxpcHNlIGN4PSIxMjAiIGN5PSIxMjAiIHJ4PSIxMjAiIHJ5PSIxMjAiIGZpbGw9IiNmZmZmZmYiIHN0cm9rZT0iIzAwMDAwMCIgcG9pbnRlci1ldmVudHM9ImFsbCIvPjxlbGxpcHNlIGN4PSIxMjAiIGN5PSIxMjAiIHJ4PSI0MCIgcnk9IjQwIiBmaWxsPSIjZmZmZmZmIiBzdHJva2U9IiMwMDAwMDAiIHBvaW50ZXItZXZlbnRzPSJhbGwiLz48cGF0aCBkPSJNIDE5NC4yNSAyNjcuMzIgTCAxODUuMyAyNzEuNzkgTCAxNzQuMjUgMjQ5LjY4IEwgMTY0Ljg2IDI1NC4zNyBMIDE3MC4yMiAyMzAuNDUgTCAxOTIuNTggMjQwLjUxIEwgMTgzLjE5IDI0NS4yMSBaIiBmaWxsPSJub25lIiBzdHJva2U9IiMwMDAwMDAiIHN0cm9rZS1saW5lam9pbj0icm91bmQiIHN0cm9rZS1taXRlcmxpbWl0PSIxMCIgcG9pbnRlci1ldmVudHM9ImFsbCIvPjxwYXRoIGQ9Ik0gMjA0Ljg1IDIwNC44NSBMIDE0OC4yOCAxNDguMjgiIGZpbGw9Im5vbmUiIHN0cm9rZT0iIzAwMDAwMCIgc3Ryb2tlLW1pdGVybGltaXQ9IjEwIiBwb2ludGVyLWV2ZW50cz0ic3Ryb2tlIi8+PHBhdGggZD0iTSAxNjAgMTIwIEwgMjQwIDEyMCIgZmlsbD0ibm9uZSIgc3Ryb2tlPSIjMDAwMDAwIiBzdHJva2UtbWl0ZXJsaW1pdD0iMTAiIHBvaW50ZXItZXZlbnRzPSJzdHJva2UiLz48cGF0aCBkPSJNIDI3My4yNCAxOTYuMTYgTCAyNjYuMDYgMjAzLjEyIEwgMjQ0Ljk2IDE4MS4zOSBMIDIzNy40MyAxODguNzEgTCAyMzUuMzEgMTY0LjI4IEwgMjU5LjY2IDE2Ny4xMSBMIDI1Mi4xMyAxNzQuNDMgWiIgZmlsbD0ibm9uZSIgc3Ryb2tlPSIjMDAwMDAwIiBzdHJva2UtbGluZWpvaW49InJvdW5kIiBzdHJva2UtbWl0ZXJsaW1pdD0iMTAiIHBvaW50ZXItZXZlbnRzPSJhbGwiLz48cmVjdCB4PSIxNzAiIHk9IjI3MCIgd2lkdGg9IjQwIiBoZWlnaHQ9IjIwIiBmaWxsPSJub25lIiBzdHJva2U9Im5vbmUiIHBvaW50ZXItZXZlbnRzPSJhbGwiLz48ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgtMC41IC0wLjUpIj48c3dpdGNoPjxmb3JlaWduT2JqZWN0IHN0eWxlPSJvdmVyZmxvdzogdmlzaWJsZTsgdGV4dC1hbGlnbjogbGVmdDsiIHBvaW50ZXItZXZlbnRzPSJub25lIiB3aWR0aD0iMTAwJSIgaGVpZ2h0PSIxMDAlIiByZXF1aXJlZEZlYXR1cmVzPSJodHRwOi8vd3d3LnczLm9yZy9UUi9TVkcxMS9mZWF0dXJlI0V4dGVuc2liaWxpdHkiPjxkaXYgeG1sbnM9Imh0dHA6Ly93d3cudzMub3JnLzE5OTkveGh0bWwiIHN0eWxlPSJkaXNwbGF5OiBmbGV4OyBhbGlnbi1pdGVtczogdW5zYWZlIGNlbnRlcjsganVzdGlmeS1jb250ZW50OiB1bnNhZmUgY2VudGVyOyB3aWR0aDogMzhweDsgaGVpZ2h0OiAxcHg7IHBhZGRpbmctdG9wOiAyODBweDsgbWFyZ2luLWxlZnQ6IDE3MXB4OyI+PGRpdiBzdHlsZT0iYm94LXNpemluZzogYm9yZGVyLWJveDsgZm9udC1zaXplOiAwOyB0ZXh0LWFsaWduOiBjZW50ZXI7ICI+PGRpdiBzdHlsZT0iZGlzcGxheTogaW5saW5lLWJsb2NrOyBmb250LXNpemU6IDEycHg7IGZvbnQtZmFtaWx5OiBIZWx2ZXRpY2E7IGNvbG9yOiAjMDAwMDAwOyBsaW5lLWhlaWdodDogMS4yOyBwb2ludGVyLWV2ZW50czogYWxsOyB3aGl0ZS1zcGFjZTogbm9ybWFsOyB
```

### 구현
```rust
const QUEUE_SIZE=128;
struct CircularQueue<T>{
	arr:[T;QUEUE_SIZE],
	first: u32,
  near : u32
};
```
isfull
```rust

impl CircularQueue<T>{
	fn new() -> CircularQueue<T>{
    CircularQueue<T>{
			[0;QUEUE_SIZE]
    }
	}
  fn is_full(&self) -> bool{
		(self.rear + 1) % QUEUE_SIZE == self.first;
  }
}
```

```rust
impl Queue<T> for CircularQueue<T>
{
  fn is_empty(&self){
		self.near == self.first
  }
	fn enqueue(&mut self, item: T) -> Result<()>{
    if self.is_full(){
      Error()
		}
    else{
    	self.rear = (self.rear +1) % QUEUE_SIZE;
			self.arr[self.rear + 1] = item;
      Ok(())
    }
  }
  fn dequeue(&mut self) -> Result<T>{
    if self.is_empty(){
			Error()
    }
    else{
			self.first = (self.first + 1) % QUEUE_SIZE;
      Ok(self.arr[self.rear])
    }
  }
}
```