스택(Stack)이란

스택(Stack)

 

스택이란?

한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조를 의미합니다. 즉 Last In First Out 특성을 가집니다.

 

스택은 다음과 같은 연산을 사용합니다.

    - pop() 스택에서 가장 위에 있는 데이터를 삭제합니다.

    - push(item) item 하나를 스택의 가장 윗 부분에 추가합니다.

    - peek() 스택에서 가장 위에 있는 데이터를 반환합니다. 탑 포인터가 가리키는 데이터를 반환만 할 뿐, 탑의 인덱스          는 변화시키지 않는 연산을 의미합니다.

    - isEmpty() 스택이 비어있을 때에 true를 반환합니다.

 

 

 

스택의 구현

 

스택은 배열이나 링크드리스트를 통해서 구현할 수 있습니다.

 

 

 

다음은 자바로 배열을 사용해 스택을 구현한 것입니다.

 

public class ArrayStack {
	private int top;
	private int maxSize = 0;
	private Object[] Stack;
	
	
	//maxSize로 스택을 생성
	public ArrayStack(int maxSize) {
		Stack = new Object[maxSize];
		this.maxSize = maxSize;
		this.top = -1;
	}
	
	public boolean isEmpty() {
		return (top==-1);
	}
	
	public boolean isFull() {
		return top==(maxSize-1);
	}
	
	public void push(Object item) {
		Stack[++top] = item;
	}
	
	public Object peek() {
		return Stack[top];
	}
	
	public Object pop() {
		Object temp = Stack[top--];
		return temp;
	}
	
	public static void main(String[] args) {
	
		ArrayStack test = new ArrayStack(5);	
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("스택이 비어있지 않습니다.");
		}
		
		test.push(1);
		test.push(2);
		test.push(3);
		
		System.out.println("스택의 맨 위에 들어있는 값은 : " + test.peek());
		test.pop();
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("스택이 비어있지 않습니다.");
		}
		
		System.out.println("스택의 맨 위에 들어있는 값은 : " + test.peek());
		
	}

}

 

 

다음은 자바로 LinkedList를 이용해 스택을 구현한 것입니다.

 

public class LinkedListStack {
	private StackNode top;

	class StackNode{
		private Object data;
		StackNode next;
		public StackNode(Object input) {
			this.data = input;
			this.next = null;
		}
		
	}
	
	 public LinkedListStack(){
	        this.top = null;
	    }

	public void push(Object data) {
		StackNode newStackNode = new StackNode(data);
		newStackNode.next = top;
		top = newStackNode;
	}
	
	public Object pop() {
		Object data = peek();
		top = top.next;
		
		return data;
	}
	
	public Object peek() {
		if(isEmpty()) throw new ArrayIndexOutOfBoundsException();
		return top.data;
	}
	
	public boolean isEmpty() {
		return (top==null);
	}
	
	public static void main(String[] args) {
		

		LinkedListStack test = new LinkedListStack();	
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("스택이 비어있지 않습니다.");
		}
		
		test.push(1);
		test.push(2);
		test.push(3);
		
		System.out.println("스택의 맨 위에 들어있는 값은 : " + test.peek());
		test.pop();
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("스택이 비어있지 않습니다.");
		}
		
		System.out.println("스택의 맨 위에 들어있는 값은 : " + test.peek());
		
		
	}
}

 

 

 

자바 Stack 클래스 사용법

 

이렇게 구현해본 스택은 자바의 util에 기본적으로 제공되기 때문에 따로 구현하지 않아도 됩니다. 그럼 이 클래스를 자바에서 사용하려면 어떻게 해야 할까요?

 

java.util.Stack을 import 한 뒤 Stack<Element> stack = new Stack<>(); 과 같은 형식으로 선언하면 됩니다.

 

자바의 스택 클래스를 활용해본 예제는 다음과 같습니다.

 

 

import java.util.Stack;

public class StackTest{
	public static void main(String[] args) {
    
		Stack<Integer> stack = new Stack<>();
		
		if(stack.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("스택이 비어있지 않습니다.");
		}
		
		stack.push(1);
		stack.push(2);
		stack.push(3);
		
		System.out.println("스택의 맨 위에 들있는 값은 : " + stack.peek());
		stack.pop();
		
		System.out.println("스택의 사이즈는 : " + stack.size());
		System.out.println("스택에 1이라는 값이 있는지 : "+ stack.contains(1));
	}
}