[자료구조] Stack & Queue

Stack 코드 구현

• Last In First Out
• pop(): 맨 마지막에 넣은 데이터를 가져오면서 지운다.
• push(): 새로운 데이터를 맨 위에 쌓아 올리는 것.
• peek(): 맨 마지막 데이터를 봄.
• isEmpty(): Stack에 데이터가 있는지 없는지 확인하는 것.

# Stack 구현 코드
import java.util.EmptyStackException;

class Stack<T>{
	class Node<T>{
    	private T data;
        private Node<T> next;
        
        public Node(T data){
        	this.data = data
        }
    }
    
    private Node<T> top;
    
    public T pop(){
    	if(top == null){
        	throw new ExptyStackException();
        }
        
        T item = top.data;
        top = top.next;
        return item;
    }
    
    public void push(T item){
    	Node<T> t = new Node<T>(item);
        t.next = top;
        top = t;
    }
    
    public T peek(){
    	if(top == null){
        	throw new ExptyStackException();
        }
        return top.data;
    }
    
    public boolean isEmpty(){
    	return top == null;
    }
}

# 테스트 클래스
public class StackTest{
	public static void main(String[] args){
    	Stack<Integer> s = new Stack<Integer>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.pop());
        System.out.println(s.pop());
        System.out.println(s.peek());
        System.out.println(s.pop());
        System.out.println(s.isEmpty());
        System.out.println(s.pop());
        System.out.println(s.isEmpty());
    }
}

# 결과 값
4
3
2
2
false
1
true

Queue 코드 구현

• First In First Out
• add(): 맨 끝에 데이터를 넣음
• remove(): 맨 앞에서 데이터를 꺼냄
• peek(): 맨 앞에 있는 데이터를 봄
• isEmpty(): Queue가 비었는지 확인

# Queue 구현 코드
import java.util.NoSuchElementException;

class Queue<T>{
	class Node<T>{
    	private T data;
        private Node<T> next;
        
        public Node(T data){
        	this.data = data;
        }
    }
    
    private Node<T> first;
    private Node<T> last;
    
    public void add(T item){
    	Node<T> t = new Node<T>(item);
        
        if(last != null){
        	last.next = t;
        }
        last = t;
        if(first == null){
        	first = last;
        }
    }
    
    public T remove(){
		if(first == null){
        	throw new NoSuchElementException();
        }
        
        T data = first.data;
        first = first.next;
        
        if(first == null){
        	last = null;
        }
        return data;
	}
    
    public T peek(){
    	if(first == null){
        	throw new NoSuchElementException();
        }
        return first.data;
    }
    
    public boolean isEmpty(){
    	return first == null;
    }
}

# 테스트 클래스
public class QueueTest{
	public static void main(String[] args){
    	Queue<Integer> q = new Queue<Integer>();
        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);
        System.out.println(q.remove());
        System.out.println(q.remove());
        System.out.println(q.peek());
        System.out.println(q.remove());
        System.out.println(q.isEmpty());
        System.out.println(q.remove());
        System.out.println(q.isEmpty());
	}
}

# 결과 값
1
2
3
3
false
4
true