[자료구조] stack 구현

주재완·2024년 3월 16일

Java 자료구조

자료구조

목록 보기

4/10

Introduction

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

Stack?

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

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

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

stack

스택의 활용

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

웹 브라우저 방문기록(뒤로 가기) : 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();
	}
}