[Java] 스택(Stack) 정리 및 구현

이번 포스팅에서는 자료구조의 하나인 '스택(Stack)'을 다루고자 한다.

먼저 스택의 정의에 대해서 간략하게 설명하고 스택의 동작과 스택의 구현 방법을 JAVA코드를 참고해 구현해보겠다.

 

1. 스택(Stack)이란 무엇인가?                                                                 

우선 영어 단어 '스택(Stack)'이란 '쌓다' , '쌓아 올린 더미'를 의미하며, 자료구조의 '스택(Stack)' 역시 이러한 특징을 지닌다.

 

스택은 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식이며, 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조이다. 

 

즉, 마지막에 들어온 데이터가 가장 먼저 나가는 특징인 LIFO구조(Last In First Out, 후입 선출)를 갖는다.

네모 상자 안에 여러 개의 공을 넣고 빼는 생각을 하면 편리하다.

 

스택의 동작과정(마지막에 넣은 것을 먼저 뺀다.)

 

책을 쌓듯이 공을 밑에서부터 순서대로 쌓아가며 공을 넣는다(push).

뺄 때는 가장 마지막에 넣었던, 가장 위에 있는 공부터 빼내게 된다(pop). 

 

 

2. 스택(Stack)의 동작 (주요 기능)                                                            

(1) 삽입(집어넣기) - push

 

스택공간에 데이터를 순서대로 추가(저장)하는 기능.

top의 값을 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

 

(2) 추출(삭제, 꺼내기) - pop

 

스택 공간의 최상단에 위치한(top) 데이터를 꺼내는 기능(삭제).

데이터를 삭제한 후 top의 값을 하나 감소시키도록 구현한다.

 

(3) 읽기 - peek/top

 

제일 최근에 들어 간 데이터, 최상위 데이터를 의미한다.

top의 값은 변화가 없다.

 

 

3. 스택(Stack)의 구현                                                                            

대표적인 스택의 구현 방법은 2가지가 있다.

 

1) 1차원 배열을 이용한 구현 

구현이 상대적으로 쉬우나 Input 사이즈를 미리 알아야한다. 

 

2) 리스트

구현이 상대적으로 어려우나 제한된 사이즈로부터 자유롭다.

 

 

3.1) 1차원 배열을 이용한 구현 Code(Java)

public class AS {
	public static void main(String[] args) {
		int stackSize = 5;
		char deletedItem;
		ArrayStack S = new ArrayStack(stackSize);
		
		S.push('A');
		S.printStack();
		
		S.push('B');
		S.printStack();
		
		S.push('C');
		S.printStack();
		
		S.push('D');
		S.printStack();
		
		S.push('E');
		S.printStack();
		
		deletedItem = S.pop();
		if(deletedItem != 0) {
			System.out.println("deleted Item: " + deletedItem);
		}
		S.printStack();
	}
}
 
interface Stack{
	boolean isEmpty();
	void push(char item);
	char pop();
	void delete();
	char peek();
}

class ArrayStack implements Stack{
	private int top;
	private int stackSize;
	private char itemArray[];
	
	public ArrayStack(int stackSize){
		top = -1;
		this.stackSize = stackSize;
		itemArray = new char[this.stackSize];
	}
	
	public boolean isEmpty(){
		return (top == -1);
	}
	
	public boolean isFull(){
		return (top == this.stackSize-1);
	}

	public void push(char item){
		if(isFull()){
			System.out.println("Inserting fail! Array Stack is full!!");
		}
		else{ 			
			itemArray[++top] = item;
			System.out.println("Inserted Item : " + item);
		}
	}

	public char pop(){
		if(isEmpty()) {
			System.out.println("Deleting fail! Array Stack is empty!!");
			return 0;
		}
		else{ 
			return itemArray[top--];	
		}				
	}

	public void delete(){
		if(isEmpty()){
			System.out.println("Deleting fail! Array Stack is empty!!");			
		}
		else {
			top--;
		}
	}	

	public char peek(){
		if(isEmpty()){
			System.out.println("Peeking fail! Array Stack is empty!!");
			return 0;
		}
		else 
			return itemArray[top];		
	}
	
	public void printStack(){
		if(isEmpty())
			System.out.printf("Array Stack is empty!! %n %n");
		else{
			System.out.printf("Array Stack>> ");
			for(int i=0; i<=top; i++)
				System.out.printf("%c ", itemArray[i]);
			System.out.println();	System.out.println();
		}
	}
}

출력결과 : 

ArrayStack 출력결과

3.2) 리스트를 이용한 구현(JAVA)

public class LS {
	public static void main(String[] args) {
		char deletedItem;
		LinkedStack LS = new LinkedStack();
		
		LS.push('A');
		LS.printStack();
		
		LS.push('B');
		LS.printStack();
		
		LS.push('C');
		LS.printStack();
		
		LS.push('D');
		LS.printStack();
		
		deletedItem = LS.pop();
		
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem);
		}
		LS.printStack();
	}
}
 
interface Stack{
	boolean isEmpty();
	void push(char item);
	char pop();
	void delete();
	char peek();
}

class StackNode{
	char data;
	StackNode link;
}

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

	public void push (char item) {
		StackNode newNode = new StackNode();
		newNode.data = item;
		newNode.link = top;
		top = newNode;
		System.out.println("Inserted Item : " + item);
	}

	public char pop() {
		if(isEmpty()) {
			System.out.println("Deleting fail! Linked Stack is empty!!");
			return 0;
		}
		else {
			char item = top.data;
			top = top.link;
			return item;
		}
	}

	public void delete() {
		if(isEmpty()) {
			System.out.println("Deleting fail! Linked Stack is empty!!");
		}
		else {
			top = top.link;
		}
	}
	
	public char peek() {
		if(isEmpty()) {
			System.out.println("Peeking fail! Linked Stack is empty!!");
			return 0;
		}
		else 
			return top.data;
	}

	public void printStack() {
		if(isEmpty())
			System.out.println("Linked Stack is empty!! %n %n");
		else {
			StackNode temp = top;
			System.out.println("Linked Stack>> ");
			while(temp != null) {
				System.out.printf("\t %c \n", temp.data);
				temp = temp.link;
			}
			System.out.println();
		}
	}
}

출력 결과 : 

LinkedStack 출력결과