[자료구조/개념] Java API를 이용한 Stack과 Queue 구현

Stack과 Queue개념

Stack과 Queue는 List보다 좀 더 제한된 Data Structure입니다.

Element가 List처럼 순차적으로 배열되지만,

추가 및 삭제시 컬렉션의 끝에서만 실행할 수 있습니다.

아래 그림을 보고 좀더 구체적으로 알아봅시다.

Stack은 LIFO (Last in, First out) 구조로서,

엘리먼트가 추가될 때 stack에 쌓이고, 꺼내 쓸때는 위에서부터 꺼내쓰기 때문에

마지막에 들어갔던 엘리먼트가 처음으로 꺼내지는 구조입니다.

반대로 Queue는 FIFO (First Out, First In) 구조로서,

엘리먼트가 컬랙션의 끝(꼬리)에 하나씩 추가되고,

꺼내질때는 컬랙션의 다른 끝(머리)에서 제거되므로

처음에 들어갔던 엘리먼트가 처음으로 꺼내지는 구조입니다.

Java에서의 Stack과 Queue 구현법

stack클래스를 사용하기 위해서 new 연산자를 사용하여 stack 클래스의 생성자를 호출합니다.

Stack mystack = new Stack();

public class	메소드	설명	예
void	push(Item item)	Object를 스택 맨 위에 추가합니다.	서류 더미 위에 다른 종이를 놓는 것
Item	pop()	스택 맨 위에서 객체를 제거하고 리턴합니다.	서류 더미 위에서 종이를 가져옴
Item	peek()	스택 맨 위에 있는 객체를 제거하지 않고 리턴합니다.	서류 더미 맨 위에 있는 종이만 읽음.
boolean	isEmpty()	현재 스택이 비어있는지 확인합니다.
int	size()	스택의 사이즈를 리턴합니다.

실제로 구현해 봅시다.

import java.util.Stack;

public class StackDemo {
	public static void main(String args[]) {
		// Create a new, empty stack
		Stack lifo = new Stack();

		// Let's add some items to it
		for (int i = 1; i <= 10; i++) {
			lifo.push(new Integer(i));
		}
		// Last in first out means reverse order
		while (!lifo.empty()) {
			System.out.print(lifo.pop());
			System.out.print(", ");
		}
		// Empty, let's lift off!
		if(lifo.isEmpty()){
			System.out.println("LIFT-OFF!");
		}
	}
}

아래는 실제 출력 결과입니다.

10, 9, 8, 7, 6, 5, 4, 3, 2, 1, LIFT-OFF!

다음은 Queue의 구현법에 대해 알아봅시다.

대부분 Queue는 LinkedList를 이용하여 구현이 되는데요.

LinkedList를 이용하여 Queue를 구현할 경우 데이터가 저장될 Queue의 크기를 미리 지정하지 않아도 되며

배열처럼 삭제한 공간을 낭비하지 않아도 되는 장점이 있어요.

Queue클래스를 사용하기 위해서 아래와 같이 LinkedList() 생성자를 호출해줍니다.

Queue는 인터페이스이므로, 명시적으로 Queue를 구성할 수 없으며,

LinkedList와 같은 구현 클래스 중 하나로 인스턴스화해야합니다.

Queue queue = new LinkedList();

유형	메소드	설명
Enqueuing	add(e)	Item이 Queue의 뒤에 추가됩니다. 만약 fail시 exception을 던집니다.
Enqueuing	offer(e)	Item이 Queue의 뒤에 추가됩니다. 만약 fail시 false를 리턴합니다.
Dequeuing	remove()	대기열 앞에 있는 Item이 리턴되고, Queue에서 삭제됩니다.  Queue가 빈 상태일 때 exception을 던집니다
Dequeuing	poll()	대기열 앞에 있는 Item이 리턴되고, Queue에서 삭제됩니다.  Queue가 빈 상태일 때 null을 리턴합니다
조회	element()	대기열 앞에 있는 Item이 리턴되고, Queue에서 삭제되지는 않습니다.  Queue가 빈 상태일 때 exception을 던집니다.
조회	peek()	대기열 앞에 있는 Item이 리턴되고, Queue에서 삭제되지는 않습니다.  Queue가 빈 상태일 때 null을 리턴합니다.
boolean	isEmpty()	현재 Queue가 비어있는지 확인합니다.
int	size()	Queue의 사이즈를 리턴합니다.

Java로 구현한 소스입니다.

import java.util.LinkedList;
import java.util.Queue;
public class QueueDemo{
	public static void main(String[] args) {
	    //Creating queue would require you to create instannce of LinkedList and assign 
	    //it to Queue
	    //Object. You cannot create an instance of Queue as it is abstract
		Queue pipo = new LinkedList();
		for(int i=1; i<=10; i++){
			//you add elements to queue using add method
			pipo.add(new Integer(i));
		}
		while(!pipo.isEmpty()){
		    //.poll() method retrieves and removes the head of this queue
		    //or return null if this queue is empty. Here .NET would be printed and then would 
		    //be removed
		    //from the queue
			System.out.print(pipo.poll());
			System.out.print(", ");
		}
		// Empty, let's lift off!
		if(pipo.isEmpty()){
			System.out.println("LIFT-OFF!");
		}		
	}
}