[윤성우의 열혈 자료구조]스택(Stack) - 자바(Java) 구현

스택(Stack)

• 먼저 들어간 것이 나중에 나오는 자료구조
  • LIFO(Last-in, First-out) 구조

 

스택 자료구조의 추상 자료형(ADT)

	boolean SIsEmpty(); //스택이 비어있는지 확인하는 메소드

	void SPush(T data); //스택에 데이터를 저장하는 메소드

	T SPop(); //스택의 마지막에 저장된 요소를 삭제하는 메소드

	T SPeek(); //스택의 마지막에 저장된 요소를 조회하는 메소드

배열기반 스택

public class ArrayStack<T> {

	private static final int DEFAULT_ARRAY_SIZE = 8; 
	private T[] stackArr;
	private int top;
	
	public ArrayStack(Class<T> type) {
		stackArr = (T[]) Array.newInstance(type, DEFAULT_ARRAY_SIZE);
		top = -1;
	}

	/**
	 * 스택이 비었는지 확인
	 * @return
	 */
	public boolean SIsEmpty() {
		if(top == -1)
			return true;	
		
		return false;
	}
	
	/**
	 * 스택의 push 연산
	 * @param data
	 */
	public void SPush(T data) {
		top++;
		this.stackArr[top] = data;
	}
	
	/**
	 * 스택의 pop 연산
	 * @return
	 */
	public T SPop() {
		//Spop() 내부에서는 해당 위치가 유효한 데이터의 위치임을 보장한다.
		//배열에서의 삭제는 해당 위치의 값을 초기화 시켜주지 않아도 된다.
		//top의 위치가 변경되면 기존 위치에 데이터가 있더라도 유효한 데이터로 인정되지 못한다.
		if(SIsEmpty()) {
			new ArrayIndexOutOfBoundsException("Stack Memory Error!");
		}
		int rIdx = top;
		top--;
		return this.stackArr[rIdx];
	}
	
	/**
	 * 스택의 peek 연산
	 * @return
	 */
	public T SPeek() {
		if(SIsEmpty()) {
			System.out.println("Stack Memory Error!");
		}
		return this.stackArr[top];
	}
	
	public static void main(String[] args) {
		// Stack의 생성 및 초기화 ///////
		ArrayStack<Integer> stack = new ArrayStack<>(Integer.class);

		// 데이터 넣기 ///////
		stack.SPush(1);
		stack.SPush(2);
		stack.SPush(3);
		stack.SPush(4);
		stack.SPush(5);

		// 데이터 꺼내기 ///////
		while(!stack.SIsEmpty())
			System.out.printf("%d ", stack.SPop()); 
	}
}

 

배열기반 스택의 단점

• 배열의 특징을 가진다.

• 중간 삽입, 삭제 과정이 없으므로 불필요한 데이터의 이동이 발생하지 않으나 초기에 저장공간을 할당받아야 한다.
  저장공간을 모두 활용하지 않는다면 저장공간이 낭비될 수 있다.

 

배열기반 스택의 장점

• 배열의 특징을 가진다.

• 연결리스트기반 스택에 비해 데이터 저장 공간을 효율적으로 사용한다.

 

연결리스트기반 스택

public class LinkedListStack<T> {

	//노드를 표현한 클래스
	private class Node{
		private T data;
		private Node nextLink;
		
		private Node() {
			this.data = null;
			this.nextLink = null;
		}
		private Node(T data) {
			this.data = data;
			this.nextLink = null;
		}
	}
	
	private Node head;
	
	public LinkedListStack() {
		head = null;
	}

	/**
	 * 스택이 비었는지 확인
	 * @return
	 */
	public boolean SIsEmpty() {
		if(head == null)
			return true;	
		
		return false;
	}
	
	/**
	 * 스택의 push 연산
	 * @param data
	 */
	public void SPush(T data) {
		Node newNode = new Node(data);
		newNode.nextLink = head;
		head = newNode;
	}
	
	/**
	 * 스택의 pop 연산
	 * @return
	 */
	public T SPop() {
		if(SIsEmpty())
			new ArrayIndexOutOfBoundsException("Stack Memory Error!");
		
		T rdata = head.data;
		head = head.nextLink;
		return rdata;
	}
	
	/**
	 * 스택의 peek 연산
	 * @return
	 */
	public T SPeek() {
		if(SIsEmpty())
			new ArrayIndexOutOfBoundsException("Stack Memory Error!");
		
		return head.data;
	}
	
	public static void main(String[] args) {
		// Stack의 생성 및 초기화 ///////
		LinkedListStack<Integer> stack = new LinkedListStack<>();

		// 데이터 넣기 ///////
		stack.SPush(1);
		stack.SPush(2);
		stack.SPush(3);
		stack.SPush(4);
		stack.SPush(5);

		// 데이터 조회 ///////
		System.out.println(stack.SPeek());
		
		// 데이터 꺼내기 ///////
		while(!stack.SIsEmpty())
			System.out.printf("%d ", stack.SPop()); 
		
	}
}

 

연결리스트기반 스택의 단점

• 연결리스트의 특징을 가진다.

• 배열기반 스택에 비해 데이터 저장 시 활용하는 메모리가 더 크다. (데이터 + 연결리스트 주소)

 

연결리스트기반 스택의 장점

• 연결리스트의 특징을 가진다.

• 초기에 저장 공간을 할당받는 배열기반 스택과 달리 연결리스트기반 스택은 저장 공간의 제약이 없다.

---

[참고자료]

윤성우의 열혈 자료구조