Introduction

자료구조의 대표주자 중 하나 스택을 구현하고자 합니다. 코딩 테스트 실전용으로 구현하는 것을 목표로 합니다.

Stack?

자바 실행 과정 및 구조에서도 스택을 볼 수 있고 개발자의 기술 스택이라는 용어등 다양한 곳에서 "스택" 이라는 단어를 볼 수 있습니다. 그러면 스택이란 무엇일까요?

사전적인 의미로는 "쌓여있다", "무더기"를 의미합니다. 즉 기본적으로 쌓여있는 형태를 넓은 의미로 스택이라 합니다. 자료구조에서 스택도 동일한 의미를 지닙니다.

무엇인가 쌓여있을 때 소위 말하는 밑장빼기를 하면 무더기가 균형을 잃어 무너질 수 있습니다. 즉 우리는 무엇인가를 위에서부터 넣고 위에서부터 뺍니다. 다시 생각하면 맨 나중에 넣은 것은 맨 위에 있어 제일 먼저 뺄 수 있습니다. 이를 후입선출(LIFO, Last-In-First-Out)이라 하며 스택은 대표적인 후입선출 자료구조입니다. 흔히 스택을 그림으로 표현하면 다음과 같습니다.

스택의 활용

대표적인 스택의 활용들은 아래와 같습니다.

• 웹 브라우저 방문기록(뒤로 가기) : URL 정보를 쌓아서 하나씩 꺼내는 방식
• 깊이 우선 탐색(DFS)
• 후위 표현법 계산(백준 1918번)

구현 아이디어

우선 들어가고 나가는 곳이 맨 끝으로 동일하다는 것을 알 수 있습니다. 즉 스택을 구현할 때 맨 끝을 나타내는 포인터 하나가 필요하다는 것을 알 수 있습니다. 포인터, 어디선가 들어본 것 같은데 바로 연결 리스트에서 언급한 바 있습니다.

바로 연결 리스트에서 헤드는 따로 지정하지 않고 끝부분만 자료가 이동하는 형태로 생각한 것이 바로 스택입니다. 그래서 사실상 연결 리스트만 구현을 제대로 해도 스택, 후에 언급할 큐나 덱 같은 것도 아주 쉽게 구현 가능합니다.

연결 리스트는 이미 이 포스팅에서 구현을 해 두었습니다. 따라서 백준 문제 풀이와 동시에 스택을 구현하고자 합니다.

백준 문제

백준 10828번 스택 문제입니다. 이 문제의 링크를 아래에 첨부합니다.
https://www.acmicpc.net/problem/10828

구현 및 문제 풀이

기본적으로 백준에서 설명한 바와 같이 기본적인 스택의 명령은 크게 다음과 같습니다.

push X: 정수 X를 스택에 넣는 연산
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력.
size: 스택에 들어있는 정수의 개수를 출력.
empty: 스택이 비어있으면 1, 아니면 0을 출력.
top: 스택의 가장 위에 있는 정수를 출력. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력.

물론 자바에서는 stack, queue, deque 자료구조를 Collections에서 제공하고 있지만, 연습을 위해 연결 리스트에서 구현했던 방법을 응용해서 구현하겠습니다.

import java.io.*;

/*
 * push X: 정수 X를 스택에 넣는 연산
 * pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력.
 * size: 스택에 들어있는 정수의 개수를 출력.
 * empty: 스택이 비어있으면 1, 아니면 0을 출력.
 * top: 스택의 가장 위에 있는 정수를 출력. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력.
 */
class MyStack {
	int size;
	StackNode last;
	
	public MyStack() {
		this.size = 0;
		this.last = null;
	}
	
	class StackNode {
		int data;
		StackNode prev;
		StackNode next;
		
		public StackNode(int data) {
			this.data = data;
			this.prev = null;
			this.next = null;
		}
	}
	
	public void push(int x) {
		StackNode node = new StackNode(x);
		node.prev = this.last;
		this.last = node;
		size++;
	}
	
	public int pop() {
		if(this.last == null) {
			return -1;
		}
		
		StackNode node = this.last;
		this.last = node.prev;
		size--;
		return node.data;
	}
	
	public int size() {
		return this.size;
	}
	
	public int empty() {
		return (size == 0) ? 1 : 0;
	}
	
	public int top() {
		if(this.last == null) {
			return -1;
		}
		
		return last.data;
	}
}

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		MyStack stack = new MyStack();
		
		for(int i = 0; i < n; i++) {
			String[] command = br.readLine().split(" ");
			switch (command[0]) {
			case "push":
				stack.push(Integer.parseInt(command[1]));
				break;
			case "pop":
				sb.append(stack.pop()).append("\n");
				break;
			case "size":
				sb.append(stack.size()).append("\n");
				break;
			case "empty":
				sb.append(stack.empty()).append("\n");
				break;
			case "top":
				sb.append(stack.top()).append("\n");
				break;
			}
		}
		
		System.out.print(sb.toString());
		br.close();
	}
}

제출 결과

첨언

백준 28278 스택 2 역시 비슷한 문제로 동일하게 해결이 가능합니다. 다만 switch문에 들어갈 요소가 "1", "2", "3", "4", "5" 로만 바뀌면 완벽하게 동일한 문제입니다.

삼성 B형같이 라이브러리 제한이 있는 코딩 테스트 대비해서 최대한 import java.io.* 외에 다른 라이브러리는 사용하지 않을 계획입니다. 이를 대비하려면 앞으로 모든 자료 구조에 대해서 자다 깨면 바로 작성 가능할 정도로 연습할 필요성을 느낍니다.