스택

---

스택(stack)은 임시 데이터를 처리할 때 사용할 수 있는 간결한 도구다. 스택은 자료 구조이지만 기존에 있는 자료구조인 배열과 같다. 다만 제약을 갖고 있는데, 이러한 제약 덕분에 스택은 매우 간결해진다.

스택이 데이터를 저장하는 방법은 배열과 같지만 다음과 같은 세 가지 제약이 있다.

• 데이터는 스택의 끝에만 삽입할 수 있다.

• 데이터는 스택의 끝에서만 삭제할 수 있다.

• 스택의 마지막 원소만 읽을 수 있다.

스택의 끝을 위(top) 스택의 시작을 밑(bottom)이라고 부른다.

밑의 그림으로 이해해보자.

스택에 새 값을 삽입하는 것을 스택에 푸시한다고 한다.

6을 스택에 푸쉬했다.

3을 스택에 푸시해보자.

그 다음 2를 푸시해보자.

이처럼 스택에서 데이터의 삽입은 스택의 위에서 이루어지고 있다.
스택의 중간이나 아래에 삽입하고 싶어도 스택의 제약 때문에 그럴 수 없다.

스택에서 원소를 제거하는 것을 팝(pop)한다고 한다.

팝도 마찬가지로 스택의 위에서만 가능하다.

그림으로 살펴보자.

먼저 가장 위의 원소인 6을 팝한다.

다음의 원소인 3을 팝한다.

스택에는 6만 남아있다.

스택 연산을 묘사하는 데 자주 쓰이는 말이 있다. "Last In, First Out"을 뜻하는 LIFO다. 이는 스택에 푸시된 마지막 항목이 곧, 스택에서 팝될 첫 번째 항목이라는 의미다.

스택은 마지막에 들어 온 데이터부터 먼저 처리해야 할 때 유용하다.
우리는 문서 작업을 할 때 "되돌리기"(예의 ctrl+z)를 무척 자주 쓴다. "되돌리기"함수가 스택의 훌륭한 활용 사례라고 볼 수 있다.

스택 구현

---

다음은 자바로 구현해본 스택이다.

class stack{

	int top;
	int size;
	int[] stack;
    // 생성자
	public Main( int size ) {
		this.size = size;
		top = -1;
		stack = new int[this.size];
	}
    // 값 삽입 메소드
	public void push( int number ) {
		stack[++top] = number;		
	}
    // 값 삭제 메소드
	public int pop() {
		int tmp = stack[top];
		stack[top--] = 0;	
		return tmp;
	}
    
}

예제

---

만약 문자열을 거꾸로 만드는 함수를 작성해야한다면 스택이 유용한 도구가 될 수 있다.

int top;
	int size;
	char[] stack;
	public Main( int size ) {
		this.size = size;
		top = -1;
		stack = new char[this.size];
	}
	public void push( char content ) {
		stack[++top] = content;		
	}
	public char pop() {
		char tmp = stack[top];
		stack[top--] = '\0';	
		return tmp;
	}
	public static void main(String[] args) {
		// 문자열 abcde
		String input = "abcde";
		// 문자열만큼의 배열 크기 
		Main S = new Main( input.length() );
		// 푸시
		for(int i = 0; i < input.length(); i++) 
			S.push(input.charAt(i));
		// 삭제한 결과를 result에 합친 후 출력
		String result = "";
		for(int i = 0; i< input.length(); i++)
			result += S.pop();
		
		System.out.println(result);
		
	}

스택에서는 가장 나중에 들어온 값이 가장 먼저 나간다고 했다. 이 규칙은 문자열을 거꾸로 만드는데 매우 효과적이다.

abcde문자열의 각 문자를 스택에 푸시한 후 전부 팝을 하여 출력하면 간단히 해결된다.