스택

스택

스택은 나중에 삽입한 데이터가 먼저 나오는 후입선출(LIFO: Last In First Out)의 구조을 가지고 있는 자료구조이다. 스택에서 삽입과 삭제가 일어나는 가장 위에 있는 곳을 top이라고 한다.

---

스택 ADT

데이터
element E

메소드	내용
push(E e)	스택의 맨 위에 데이터를 추가한다.
pop()	스택의 맨 위의 데이터를 제거하고 반환한다.
peek()	스택의 맨 위의 데이터를 반환한다.
size()	스택의 크기를 반환한다.
isEmpty()	스택이 비어있는지 검사한다.

---

스택의 삽입 연산

스택의 가장 위에 데이터를 추가한다.

---

스택의 삭제 연산

스택 가장 위의 데이터를 삭제한다.

---

스택 구현

스택은 배열과 연결리스트를 이용하여 구현할 수 있다. 배열을 이용해 구현할 경우, 구현이 간단하다는 장점이 있지만 크기가 고정된다는 단점이 있다. 물론 스택이 전부 차면 메모리를 새로 할당 받아서 스택을 만드는 방법도 있지만, 예전 스택에서 새로운 스택으로 데이터를 옮기는 과정에서 복사를 해야하므로 데이터가 많으면 많을수록 시간이 많이 필요하다. 연결리스트를 이용하여 스택을 구현할 경우 구현이 복잡하고 메모리를 더 많이 쓴다는 단점이 있지만, 크기가 가변적이라는 장점이 있다.

배열을 이용한 스택의 삽입 연산

스택의 맨 위 원소를 가리키는 변수 top에 1을 더해주고, data[top]에 원소를 대입한다.

---

배열을 이용한 스택의 삭제 연산

스택의 맨 위 원소를 가리키는 변수 top에서 1을 뺀다. top 뒤의 원소에 접근할 일은 없으므로 실제로 원소를 삭제하지 않아도 된다.

---

배열을 이용한 구현

class Stack<E> {
	private E[] data;
	private int capacity; // 스택의 용량
	private int top; // 마지막 데이터의 위치
	
	Stack() {
		capacity = 100; 
		top = -1;
		data = (E[]) new Object[capacity];
	}

	private void grow() { 
		capacity += 100;
		E[] newData = Arrays.copyOfRange(data, 0, capacity);
		data = newData;
	} // 스택의 처음 용량은 100으로 설정하고, 스택이 꽉 찼을 때 push연산을 시도하면 용량을 추가로 100 늘린다.
	
	public void push(E e) {
		if(top == capacity - 1) {
			growCapacity();
		}
		
		data[++top] = e;
	}
	
	public E pop() {
		if(isEmpty()) {
			throw new NullPointerException();
		}
		else {
			return data[top--];
		}
	}
	
	public E peek() {
		if(isEmpty()) {
			throw new NullPointerException();
		}
		else {
			return data[top];
		}
	}
	
    public int size() {
		return top + 1;
	}
    
	public boolean isEmpty() {
		if(top < 0) {
			return true;
		}
		else {
			return false;
		}
	}
}

---

연결 리스트를 이용한 스택의 삽입 연산

top은 연결 리스트의 맨 앞 노드, 즉 스택의 맨 위의 노드를 참조한다. 스택의 삽입 연산은 연결 리스트에서의 addFront()연산과 동일하다.

---

연결 리스트를 이용한 스택의 삭제 연산

삽입의 역순이다. 연결리스트의 remove(0) 연산과 동일하다.

---

연결 리스트를 이용한 구현

class Stack<E> {
	Node<E> top = null;
	int stackSize = 0;
	
	private class Node<E> {
		private E data;
		private Node<E> next;
		
		Node(E data) {
			this.data = data;
			this.next = null;
		}
	}
	
	public void push(E e) {
		Node<E> node = new Node<>(e);
		
		if(top == null) {
			top = node;
		}
		else {
			node.next = top;
			top = node;
		}
		
		stackSize++;
	}
	
	public E pop() {
		if(top == null) {
			throw new NullPointerException();
		}
		else {
			E ret = top.data;
			top = top.next;
			stackSize--;
			return ret;
		}
	}
	
	public E peek() {
		if(top == null) {
			throw new NullPointerException();
		}
		else {
			return top.data;
		}
	}
	
	public int size() {
		return stackSize;
	}
	
	public boolean isEmpty() {
		if(top == null) {
			return true;
		}
		else {
			return false;
		}
	}
}

---

컬렉션 프레임워크

Stack

Stack

자바 공식문서에서 LIFO 연산을 하기 위해서는 Stack 대신 Deque를 사용하라고 한다.