[자료구조] 자바 - 스택(Stack)이란?

안녕하세요 이번 포스팅은 바로

"자료구조 중 스택"

입니다

 

자료구조는 컴퓨터공학과처럼 코딩하는 전공을

진학하면 배우는 과목입니다.

​

지금 배우는 주제인 스택은 가장 기초적이면서도

다른 곳에서도 많이 쓰인다고 보시면됩니다.

​

이러한 스택을 두가지 방법으로 해보겠습니다.

하나는 직접 스택함수(POP,PUSH)를 만들어보는 것이고

​

또 다른 하나는 기존에 있던 라이브러리를 통해

스택의 함수(POP,PUSH)를 써보는 것입니다.

 

스택(Stack)의 정의

 

 

스택은 삽입과 삭제가 "top"이라 불리는 한쪽 끝 지점에서

발생하는 순서화 리스트이다.

그리고 나중에 들어온 데이터가 먼저 나가는 형태인데

이는 Last In, First Out(LIFO)라 불린다.

​

POP,PUSH와 같은 두 가지 기본 연산이 존재한다.

POP의 경우 top에 있는 데이터를 삭제하고

PUSH의 경우 top위에 데이터를 삽입한다.

 

 

​위의 그림처럼 스택은 top의 위치만 변경시키면서 삽입과 삭제가 일어난다.

 

 

 

 

스택(STACK) 직접 구현 - JAVA

<변수선언>​

static int top = -1;
	static int full;
	static Integer[] stack;

스택에서 top의 초기값은 -1로 줍니다.

그 이유는 아래 pop,push에서 설명드리겠습니다.

​

full의 경우는 스택이 가득찼는 지 확인을 위해 선언해줍니다.

​

리스트가 아닌 배열로 스택을 구현합니다.

​

​

<pop>

static void pop() {
		if (top == -1)
			System.out.println("스택이비었습니다.");
		else 
			System.out.println(stack[top--]);		
	}

pop의 경우 top의 위치를 후위연산자를 이용합니다.

보시는 거처럼 top의 값을 빼 출력을 하고 그 다음에 top을 감소시킵니다.

top이 0을 가리키고 있을 때도 마찬가지이므로 top을 감소시키면 -1이 됩니다.

따라서 top의 초기값을 -1로 설정합니다.

​

또한, push없이 pop을 사용하거나 데이터가 없을 때 pop의 사용을 막기 위해

아래 보시는 거처럼 조건문을 통해 스택이 비었다고 설명해줍니다.

pop();
pop();
pop();
pop();

 

 

 

<push>

static void push(int num) {
		if (top == full-1)
			System.out.println("꽉찼습니다!");
		else 
			stack[++top] = num;
	}

push의 경우 값을 전위연사자를 이용합니다.

그 이유는 바로 삽입하거나 후위연산자를 이용할 경우 기존의 데이터를 덮고

새로운 데이터가 삽입되는 상황이 발생합니다.

그렇기 때문에 top을 증가시켜 기존의 데이터 보다 높은 위치에 삽입을 시킵니다.

​

push의 경우도 pop처럼 full의 도달했을 때 꽉찼음을 알려줍니다.

이때 top == full-1로 조건을 주었는데 이는 push가 전위연산자를 이용하기 때문에

전위연산자를 사용했을 때 배열의 경계를 넘지 않는 지 비교하기 위함입니다.

​

아래의 경우 배열의 크기를 5로 했기 때문에 5개 넘어서는 "꽉찼습니다"를 출력합니다.

 

push(10);
push(20);
push(30);
push(40);
push(50);
push(60);
push(70);
push(80);

 

 

 

 

 

스택(STACK) 직접 구현 - 최종코드

import java.util.Scanner;

public class Stack {
	static int top = -1;
	static int full;
	static Integer[] stack;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		full = sc.nextInt();
		stack = new Integer[full];		
		/*
		  push		
		  pop
		 */		
	}
	static void pop() {
		if (top == -1)
			System.out.print("스택이비었습니다.");
		else 
			System.out.println(stack[top--]);	
	}
	static void push(int num) {
		if (top == full-1)
			System.out.println("꽉찼습니다!");
		else 
			stack[++top] = num;
	}
}

 

scanner를 이용해 스택의 크기를 조절했습니다.

​

끝으로

이상으로 자료구조에 있어 가장 기초적이라고 할 수 있는

스택에 대해 알아보고 직접 구현해 보았습니다.

​

이보다 더 좋은 코드가 많기 때문에 작성된 코드는

단순 참고용으로 보시면 될 거 같습니다.

​

궁금한 점이나 문제점이 있으시면 댓글 남겨주시면 감사하겠습니다.

​

이상으로 읽어주셔서 감사합니다!!