[Algorithm] List - Queue

★한쪽으로는 넣기만 하고, 반대쪽 끝으로는 빼기만 하는 자료구조. 선입선출 방식이다. 추상구조인 큐는 다양한 방식으로 구현할 수 있고, 자바에서는 LinkedList로 구현하고 있기에 나도 LinkedList로 Queue를 만들어 봤다. 배열로 만들기도 하는데 tail이 배열의 마지막 위치에 있으나 head가 0에 있지 않은 경우 앞으로 당겨줘야 하는 비효율이 생기기 때문에 안했다.

public class MyQueue<T> {
	
	private Node head;
	private Node tail;
	private int size = 0;
	
	public MyQueue() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
	
	public void enqueue(T v) {
		Node newNode = new Node(v);
		if (size == 0) {
			head = newNode;
			tail = newNode;
		} else {
			Node tmp = tail;
			tail = newNode;
			tmp.next = tail;
		}
		
		size++;
	}
	
	public T dequeue() {
		if (size == 0) {
			return null;
		} else if (size == 1) {
			Node tmp = head;
			head = null;
			tail = null;
			size--;
			return tmp.data;
		} else {
			Node tmp = head;
			head = tmp.next;
			size--;
			return tmp.data;
		}
	}
	
	public T peek() {
		return head.data;
	}

	private class Node {
		private T data;
		private Node next;
		
		public Node(T data) {
			this.data = data;
			this.next = null;
		}
	}
	
	public int getSize() {
		return size;
	}
	
	public void print() {
		if (size == 0) {
			System.out.println("Queue is EMPTY");
			return;
		}
		
		Node node = head;
		System.out.print("[" + head.data + " -> " + tail.data + "]");
		while (node != null) {
			System.out.print(node.data + " ");
			node = node.next;
		}
		System.out.println();
	}
}

★기타 선형 자료구조

1. Deque : 양쪽 끝으로 넣거나 뺄 수 있다.
2. Scroll : 입력은 한쪽으로, 출력은 양쪽으로 가능.
3. Shelf : 입력은 양쪽으로, 출력은 한쪽으로 가능.
4. 원형 큐 : 배열로 큐를 구현했을 때, index가 배열의 크기를 초과할 경우 다시 0으로 돌아가는 큐.