Stack(push/pop)

이번 시간에는 stack에 대하여 알아보려 합니다.

Stack은 ‘쌓아 올림’, ‘더미’ 라는 뜻을 가진 단어입니다.

선형 메모리 공간에 데이터를 쌓아 저장하면서 후입선출(LIFO)의 시멘틱을 따르는 자료 구조입니다.

맨 처음 들어간 데이터가 바닥에 쌓이고, 맨 마지막에 저장된(push) 데이터가 제일 먼저 인출되어(pop) 삽입/삭제/수정이 가능합니다.

프링*스 과자를 생각하면 이해하기 쉬울 것 같네요.

통에 과자를 넣을 때, 맨 나중에 들어간 과자를 맨 처음 먹게 될 것입니다.

스택도 같은 원리입니다.

맨 위 데이터를 top이라고, 맨 아래는 bottom이라고 부르며, 보통의 경우 bottom의 값은 0으로 고정됩니다.

stack에서 자주 사용되는 메소드는 다음과 같습니다.

메소드	설명
boolean empty()	해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
E peek()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.
E pop()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.
E push(E item)	해당 스택의 제일 상단에 전달된 요소를 삽입함.
int search(Object o)	해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함. 이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.

예제와 같이 stack을 구현해 보았습니다.

package jaryogujo;
import java.util.Stack;

public class prog {
	public static void main(String[] args) {
		Stack<Integer> st = new Stack<Integer>();	// 스택의 생성
		
		// push() 메소드를 이용한 요소의 저장
		st.push(4);
		st.push(2);
		st.push(3);
		st.push(1);
		
		// peek() 메소드를 이용한 요소의 반환
		System.out.println(st.peek());
		System.out.println(st);

top에 1이 저장되어 있음을 peak()을 통해 알 수 있었습니다.

그리고 st에 저장된 순서대로 [4, 2, 3, 1] 이 출력됩니다.

// pop() 메소드를 이용한 요소의 반환 및 제거
		System.out.println(st.pop());
		System.out.println(st);

Pop()으로 맨 위 stack의 1을 빼내어 출력했습니다.

그리고 남은 stack을 출력했더니 위와 같은 결과가 나왔습니다.

// search() 메소드를 이용한 요소의 위치 검색
		System.out.println(st.search(4));
		System.out.println(st.search(3));

Search(찾는 값) 메서드의 결과는 해당 값이 갖는 인덱스 주소입니다.

(그림에서는 작은 정사각형에 인덱스 주소를 표시했습니다.)

비어 있으면 -1을, 그렇지 않다면 맨 위 요소부터 1에서 시작하는 인덱스 값을 출력합니다.

Stack에서는 인덱스 주소 값은 반환할 수 있지만, 어떤 값이 어디에 들어있는 지 탐색하는 기능은 없습니다.

따라서 삽입, 삭제 외에 다른 기능이 없습니다.

맨 윗층에 무엇이 들었는지만 보이고, 내용물은 알 수 없는 상자로 생각할 수 있을 것 같네요.

방향성도 없다보니, 삽입과 삭제 모두에서 시간복잡도는 O(1)이겠죠.

 

이번 시간에는 stack에 대해 알아보았습니다.

다음 시간에는 queue에 대해 알아보도록 하겠습니다.