[Data Structure] Queue

2017-09-06

1. 배열(Array)로 구현한 Queue
2. Linked List로 구현한 Queue
3. 참조

Queue는 각 Data들을 순차적으로 넣었다가 순차적으로 빼내는 FIFO(First In First Out) 구조이다.

기본 연산으로 push로 rear에 데이터를 추가하고 pop으로 front의 데이터를 가져오는 방식을 가진다.

배열(Array)로 구현한 Queue

public class ArrayQueue {
	private int[] aQueue;
	private int mSize;
	
	private int mFront = 0;
	private int mRear = 0;
	
	ArrayQueue(int size) {
		mSize = size;
		aQueue = new int[mSize];
	}
	
	public void push(int data) {
		if (mRear >= mSize) {
			System.out.println("Queue is full.");
			return;
		}
		
		aQueue[mRear++] = data;
	}
	public int pop() {
		if (mFront >= mSize) {
			System.out.println("Queue is empty.");
			return -1;
		}
		return aQueue[mFront++];
	}
}

Main에서 아래와 같이 확인해보면

public class Main {
	public static void main(String[] args) {
		
		ArrayQueue aQueue = new ArrayQueue(5);
		
		aQueue.push(1);
		aQueue.push(2);
		aQueue.push(3);
		aQueue.push(4);
		aQueue.push(5);
		aQueue.push(6);
		aQueue.push(7);
		
		System.out.println(aQueue.pop());
		System.out.println(aQueue.pop());
		System.out.println(aQueue.pop());
		System.out.println(aQueue.pop());
		System.out.println(aQueue.pop());
		System.out.println(aQueue.pop());
		System.out.println(aQueue.pop());
	}
}

아래와 같은 결과를 얻을 수 있다.

Queue is full.
Queue is full.
1
2
3
4
5
Queue is empty.
-1
Queue is empty.
-1

Linked List로 구현한 Queue

Array로 구현한 Queue는 크기(size)에 한계가 있으므로 Linked list로 구현한다.

[Data Structure] Linked-list 에서 구현했던 SinglyLinkedList 를 상속하여 아래와 같이 구현한다.

public class LinkedListQueue extends SinglyLinkedList {
	LinkedListQueue(Node newNode) {
		super(newNode);
	}
	public void push(Node newNode) {
		super.addNode(newNode);
	}
	
	public Node pop() {
		if (mHead == null) {
			return null;
		}
		
		Node temp = mHead;
		mHead = mHead.getNext();
		
		return temp;
	}
}

Main에서 아래와 같이 확인해보면

public class Main {
	public static void main(String[] args) {
		LinkedListQueue llq = new LinkedListQueue(new Node(1));
		
		llq.push(new Node(2));
		llq.push(new Node(3));
		llq.push(new Node(4));
		llq.push(new Node(5));
		llq.push(new Node(6));
		llq.push(new Node(7));
		try {
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			llq.push(new Node(10));
			llq.push(new Node(11));
			llq.push(new Node(12));
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
			System.out.println(llq.pop().getData());
		} catch (NullPointerException e) {
			System.out.println("Queue is empty.");
		}
	}
}

아래와 같은 결과를 얻을 수 있다.

1
2
3
4
5
6
7
10
11
12
Queue is empty.

DevAlgorithm

배열(Array)로 구현한 Queue

Linked List로 구현한 Queue

참조