Stack & Queue - 스택과 큐

Stack

public class Stack {
	
	// Stack의 로직과 LL의 로직은 몇 가지를 제외하고는 상당히 비슷함
	// Vertical LL ~~ Stack
	// 스택에서 head는 top으로 tail은 bottom으로 명칭이 바뀐다. 
	// 그런데 스택에서는 bottom에서 무언가를 remove-add 하는 기능 자체를 사용하지 않기에 
	// bottom pointer는 필요없으므로 쓰지 않는다.
	// 즉 Stack은 가장 최근에 추가된 윗 데이터부터 먼저 다루는 알고리즘 
	// LIFO : Last In First Out
	
	private Node top;
	private int height;

	class Node {
		int value;
		Node next;
		
		Node (int value) {
			this.value = value;
		}
	}
	
	// Stack 생성자를 사용하면  
	// Node 객체를 자동 생성하며 스택의 맨 밑에 놓여질 첫 번째 노드를 생성
	public Stack(int value) {
		Node newNode = new Node(value);
		top = newNode;
		height = 1;
	}
	
	// LL의 prepend와 같은 기능
	// 위에서 아이템 집어넣기
	public void push(int  value) {
		Node newNode = new Node(value);
		
		if (height == 0) {
			// case for an empty stack	
			top = newNode;
		} else {
			// case for a stack with more than a item
			newNode.next = top;
			// 위에 추가하고자 하는 노드의 포인터가, 
            // 기존의 top이 포인팅하던 것과 같은 것을 포인팅하게 만드는 작업
			// newNode를 넣기 전에 가장 위에 있던, 이제는 Second Top이 될 그 노드
			top = newNode;
			// 그럼 이제 top 포인터는 제일 위로 올려야 함 
			// 가장 위에 얹어진 새로 만들어진 노드 객체를 top이 포인팅하게 만드는 작업
		}
		height++;
	}
	
	public Node pop() { // 위에서 pop한 객체를 반환하는 메서드
			
		if(height == 0) return null; 
		// conditional portion에 head==null도 가능 
	
		Node temp = top;
		// since we're returning the top node, we'll need a variable that points to it
		top = top.next;
		// top이 삭제할 노드의 밑의 노드를 포인팅하게 만들기
		// vertical LL이기에 next는 아래를 향하는 방향
		temp.next = null;
		// 삭제할 노드가 null을 포인팅하게 만들어서 스택에서 떼내기
		// this code line breaks the first node off from out stack
		height--; // decrement by 1
		
		return temp; // 삭제한 노드 반환 
	}
	
	public void printStack() {
		Node temp = top;
		while (temp != null) {
			System.out.print(temp.value + " ");
			temp = temp.next;
		}
		System.out.println();
	}
	
	public void getTop() {
		System.out.println("Top : " + top.value);
	}
	
	public void getHeight() {
		System.out.println("Height : " + height);
	}
}

Queue

public class Queue {

	// Stack이 Vertical한 LL이었던 것과는 달리 Queue는 Horizontal하게 생각
	// Queue는 다 해도 되는데 LL의 가장 오른쪽에 있는 것을 제거하면 안 된다 - O(n).
	// 말하자면 LL의 removeLast() 함수를 사용해서는 안 된다는 것이다
	// 이 외에 양 끝단에서 벌어지는 다른 remove-add는 전부 O(1)이다.
	
	private Node first; // head
	private Node last; // tail
	private int length;
	
	class Node {
		int value;
		Node next;
		// next is a pointer that can point to an another node
		Node(int value) {
			this.value = value;
		}
	}
	
	public Queue(int value) {
		Node newNode = new Node(value);
		first = newNode;
		last = newNode;
		length = 1;
	}
	
	// 큐의 끝에서(오른쪽에서) 노드를 추가
	// append 메서드와 유사 
	public void enqueue(int value) {
		Node newNode = new Node(value);
		
		if(length == 0) {
			// first == null 로 조건절 작성 가능
			first = newNode;
			last = newNode;
		} else {
			last.next = newNode;
			last = newNode;
		}
		length++;
	}
	
	// removeFirst 메서드와 유사 
	public Node dequeue() {
		if(length==0) return null;
		
		Node temp = first;
		
		if(length == 1) {
			first = null; 
			last = null;
		} else {
			first = first.next;
			temp.next = null; 
		}
		length--;
		return temp;
	}
	
	public void printQueue() {
		Node temp = first;
		while (temp != null) {
			System.out.print(temp.value + " ");
			temp = temp.next;
		}
		System.out.println();
	}
	
	public void getFirst() {
		System.out.println("First : " + first.value);
	}
	
	public void getLength() {
		System.out.println("Length : " + length);
	}
}