[JAVA/자료구조] 스택(Stack) 구현하기/ Stack 클래스 사용법

스택(Stack)

후입선출(last in, first out) 자료구조

 

스택 구현하기

 

0. 인터페이스 구현

public interface Stack {
	void push(int item);
	int pop();
}

스택의 주요 기능인 push, pop만 구현한다.

 

1. 배열로 구현

class arrStack implements Stack {
	
	private int top;
	private int stackSize;
	private int[] itemArr;
	
	public arrStack(int stackSize) {
		top = -1;
		this.stackSize = stackSize;
		itemArr = new int[this.stackSize];
	}
	
	public boolean isEmpty() {
		return (top == -1);
	}
	
	public boolean isFull() {
		return (top==this.stackSize-1);
	}
    
	@Override
	public void push(int item) {
		if(isFull()) {
			System.out.print("Stack is full!");
		} else {
			itemArr[++top] = item;
		}
	}
    
	@Override
	public int pop() {
		if(isEmpty()) {
			System.out.print("Stack is Empty!");
			return 0;
		} else {
			return itemArr[top--];
		}
	}
	
}

 

2. ArrayList로 구현

import java.util.ArrayList;

public class arrayListStack implements Stack {
	
	private ArrayList<Integer> arrlist;
	
	public boolean isEmpty() {
		return (arrlist.size()==0);
	}
	
	public arrayListStack() {
		arrlist = new ArrayList<Integer>();
	}

	@Override
	public void push(int item) {
		arrlist.add(item);
	}

	@Override
	public int pop() {
		if(isEmpty()) {
			System.out.print("Stack is Empty!");
			return 0;
		} else {
			return arrlist.remove(arrlist.size()-1);
		}
	}

}

 

3. LinkedList로 구현

class stackNode {
	public int data;
	public stackNode link;
	
	public stackNode() {
		this.data = 0;
		this.link = null;
	}
	
}

public class linkedListStack implements Stack {
	
	private stackNode top;
	
	public linkedListStack() {
		top = null;
	}
	
	public boolean isEmpty() {
		return (top == null);
	}

	@Override
	public void push(int item) {
		
		stackNode newNode = new stackNode();
		newNode.data = item;
		
		if(!isEmpty()) {
			newNode.link = top;
		}
		
		top = newNode;
		
	}

	@Override
	public int pop() {
		if(isEmpty()) {
			System.out.print("Stack is Empty!");
			return 0;
		} else {
			int tmpitem = top.data;
			top = top.link;
			return tmpitem;
		}
	}

}

 

Stack 클래스

자바에서는 Stack 클래스를 제공한다. Stack 클래스를 사용하면 push(), pop()을 구현할 필요없이 바로 사용할 수 있다.

 

사용법

import java.util.Stack;

public class stackTest {
	
	public static void main (String[] args) {
		
		Stack<Integer> stack = new Stack<>();
		
		stack.push(1);
		stack.push(2);
		stack.pop();
		stack.pop();
		
		//이외 메소드
		stack.clear(); //스택 값 모두 제거
		stack.peek(); //스택 top 출력만
		stack.size(); //스택 크기 줄력
		stack.empty(); //스택이 비어있다면 true
		stack.contains(1); //해당 값이 있다면 true
	}

}