JAVA Stack과 Queue구현하기

https://rightx2.tistory.com/17

JAVA Node로 Doubly Linked List 구현하기

이번에는 이전에 구현했던 Doubly Linked List로 Stack과 Queue자료구조를 구현할 것이다.

 

1. Stack

stack은 명사로는 무더기, 동사로는 쌓다 등 여러가지 의미를 갖는다.

stack 자료구조는 Last In First Out으로 LIFO구조라고 한다.

즉 가장 최근(마지막)에 삽입된 데이터가 가장 우선적으로 제거되는 구조다.

 

예를 들어 편의점 직원이 냉장고에 음료수를 채운다면 손님은 직원이 가장 마지막으로 넣은 음료수를 꺼낼 것이다.  

이런 구조를 stack이라고 한다.

 

class Stack<T>{
	DoublyLinkedList<T> list;
	
	public Stack() {
		list = new DoublyLinkedList<T>();
	}
	
	public Node<T> top() {
		if(list.getSize()==0) return null;
		return list.top();
	}
	
	public T add(T element) {
		list.add(element);
		return element;
	}
	
	public Node<T> pop() {
		if(list.getSize()==0) return null;
		Node<T> top = list.top();
		list.remove(list.top().getElement());
		return top;
	}
	
	public int getSize() {
		return list.getSize();
	}
}

class Book{
	private String name;
	private int date;
	
	public Book(String name, int date) {
		this.name = name;
		this.date = date;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getDate() {
		return date;
	}

	public void setDate(int date) {
		this.date = date;
	}
}

public class Test014 {
	public static void main( String[] args ) {
		Stack<Book> stk = new Stack<>();
		
		stk.add(new Book("The Old Man and Sea",1952));
		stk.add(new Book("Effective Java",2009));
		stk.add(new Book("Slam Dunk",1996));
		stk.add(new Book("One Piece",2019));
		
		System.out.println(stk.top().getElement().getName()+"("+stk.top().getElement().getDate()+")"); 
        	//One Piece(2019)
		stk.pop();
		stk.pop();
		System.out.println(stk.top().getElement().getName()+"("+stk.top().getElement().getDate()+")"); 
        	//Effective Java(2009)
		System.out.println(stk.getSize());//2
	}
}

 

북카트를 예시로 스택을 구현해봤다.

 

1. Book 클래스로 생성된 객체들은 책이름인 name변수와 발행년도인 date변수를 갖는다.

2. 생성된 책들은 카트에 차례로 쌓인다. 

3. 가장 마지막에 쌓인 책이 One Piece이므로 카트의 top은  One Piece가 된다.

4. 카트의 책들이 정리가 된다면 pop이 실행되고, 가장 위에 있는 책들부터 차례로 카트에서 없어진다.

5. 두번의 pop이 실행된다면 카트의 top은 Effective Java가 된다.

 

스택 함수 구현

class Stack<T>{
	DoublyLinkedList<T> list;
	
	public Stack() {
		list = new DoublyLinkedList<T>();
	}
	
	public Node<T> top() {
		if(list.getSize()==0) return null;
		return list.top();
	}
	
	public T add(T element) {
		list.add(element);
		return element;
	}
	
	public Node<T> pop() {
		if(list.getSize()==0) return null;
		Node<T> top = list.top();
		list.remove(list.top().getElement());
		return top;
	}
	
	public int getSize() {
		return list.getSize();
	}
}

 

스택은 Doubly Linked List로 구성됐기 때문에 리스트를 생성해주어야 한다.

 

1. top 메소드

: Doubly Linked List내의 top함수는 head의 pre 노드 즉 가장 마지막에 추가된 노드를 리턴한다. 

그렇기 때문에 따로 구현해줄 필요 없이 list의 함수 top그대로 사용했다.

 

2. add 메소드

: 데이터를 추가할 때 Doubly Linked List는 head 바로 전 노드에 삽입되기 때문에 list의 add메소드를 그대로 사용했다.

 

3. pop 메소드

: pop 메소드는 가장 마지막에 삽입된 데이터를 제거하는 메소드다. 따라서 top메소드를 사용해서 가장 최근에 삽입된 노드를 찾아 Doubly Linked List에 구현된 remove 메소드를 사용해서 해당 노드를 제거했다.

 

2. Queue

큐는 줄이나 대기행렬의 뜻을 갖고 있다.

queue 자료구조는 First In First Out으로 FIFO구조라고 한다.

즉 가장 먼저 삽입된 데이터가 가장 우선적으로 제거되는 구조다.

 

영화관 매표소를 예를 들 수 있다.

영화관에서 예매를 할 때 가장먼저 줄을 선 사람부터 예매가 가능하듯이 Queue는 가장 먼저 삽입된 데이터먼저 제거되는 구조라 할 수 있다.

 

class Queue<T> {
	
	DoublyLinkedList<T> list;
	
	public Queue() {
		list = new DoublyLinkedList<T>();
	}
	
	public Node<T> front() {
		if(list.getSize()==0) return null;
		return list.bottom();
	}
	
	public T add(T element) {
		list.add(element);
		return element;
	}
	
	public Node<T> pop() {
		if(list.getSize()==0) return null;
		Node<T> bottom = list.bottom();
		list.remove(list.bottom().getElement());
		return bottom;
	}
	
	public int getSize() {
		return list.getSize();
	}	
}

class Movie{
	private String name;
	private int entry;
	
	public Movie(String name, int entry) {
		this.name = name;
		this.entry = entry;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getEntry() {
		return entry;
	}

	public void setEntry(int entry) {
		this.entry = entry;
	}
}

public class Test014 {
	public static void main( String[] args ) {
    
		Queue<Movie> ticketBox = new Queue<>();
		
		ticketBox.add(new Movie("1917",3));
		ticketBox.add(new Movie("Parasite",1));
		ticketBox.add(new Movie("The IrishMan",2));
		ticketBox.add(new Movie("Joker",4));
		
		System.out.println("name: "+ticketBox.front().getElement().getName()+" entry:"+ticketBox.front().getElement().getEntry());
       		//name: 1917 entry:3
		ticketBox.pop();
		ticketBox.pop();
		ticketBox.pop();
		System.out.println("name: "+ticketBox.front().getElement().getName()+" entry:"+ticketBox.front().getElement().getEntry());
        	//name: Joker entry:4
	}
}

영화관 매표소를 예로 들어봤다.

 

1. Movie 클래스로 생성된 객체들은 영화이름인 name변수와 극장번호인 entry변수를 갖는다.

2. 사람들이 각자 예매할 영화를 선택하고 줄을 선다.

3. 가장 먼저 줄을 선 사람이 예매하고자 하는 영화는 1917이므로 ticketBox의 front의 movie name은 1917이 된다.

4. 예매를 한다면 사람이 줄에서 빠지기 때문에 pop이 실행된다.

5. 세명의 예매가 진행됐다면 즉 세번의 pop이 실행된다면 ticketBox의 front의 movie name은 Joker가 된다.

 

큐 함수 구현

class Queue<T> {
	
	DoublyLinkedList<T> list;
	
	public Queue() {
		list = new DoublyLinkedList<T>();
	}
	
	public Node<T> front() {
		if(list.getSize()==0) return null;
		return list.bottom();
	}
	
	public T add(T element) {
		list.add(element);
		return element;
	}
	
	public Node<T> pop() {
		if(list.getSize()==0) return null;
		Node<T> bottom = list.bottom();
		list.remove(list.bottom().getElement());
		return bottom;
	}
	
	public int getSize() {
		return list.getSize();
	}	
}

큐는 Doubly Linked List로 구성됐기 때문에 리스트를 생성해주어야 한다.

 

1. front 메소드

: Doubly Linked List내의 bottom함수는 tail의 next 노드 즉 가장 먼저 추가된 노드를 리턴한다. 

그렇기 때문에 따로 구현해줄 필요 없이 list의 함수 front그대로 사용했다.

 

2. add 메소드

: 데이터를 추가할 때 Doubly Linked List는 head 바로 전 노드에 삽입되기 때문에 list의 add메소드를 그대로 사용했다.

 

3. pop 메소드

: pop 메소드는 가장 먼저 삽입된 데이터를 제거하는 메소드다. 따라서 front메소드를 사용해서 가장 먼저 삽입된 노드를 찾아 Doubly Linked List에 구현된 remove 메소드를 사용해서 해당 노드를 제거했다.