스택(Stack)

스택이란?

데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조.

LIFO(Last In First Out)형, 후입선출형이라고도 한다.

스택에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 한다.

PUSH와 POP이 이뤄지는 위치를 꼭대기(top)이라고 하고, 가장 아랫부분을 바닥(bottom)이라고 한다.

 

* 다중 스택 : 하나의 공간에 2개의 스택을 구현하여 각자 사용하는 것. 많이 사용되지는 않음.

 

구현 방법

배열이나 연결 리스트를 이용해서 구현한다.

 

용도

대표적으로 프로그램을 수행할 때 사용한다.

주 프로그램에서 메서드 A를 호출하면 주 프로그램 위에 메서드 A가 쌓이고, 메서드 A의 수행 중에 메서드 B가 호출되면 그 위에 메서드 B가 쌓인다. 메서드 B의 실행이 완료되면 메서드 A가 실행되고, 메서드 A의 실행이 완료되면 주 프로그램의 실행이 시작된다.

또는, 사람이 사용하는 수식(중위 표기법)을 컴퓨터가 사용하는 수식(후위 표기법)으로 바꾸고 연산할 때도 컴파일러들은 주로 스택을 사용한다.

 

자바에서 구현하기

public class IntStack {
	
	int max;	//스택 용량. 배열 stk의 요솟수와 동일.
	int ptr;	//스택 포인터. 스택에 쌓여있는 데이터 수와 동일.
	int[] stk;	//스텍 본체(실제로 자료가 저장될 곳)를 참조하는 배열 변수

	//실행 시 예외 : 스택이 비어있음
	public class EmptyIntStackException extends RuntimeException {
		public EmptyIntStackException() {}
	}
	
	//실행 시 예외 : 스택이 꽉 차있음
	public class OverflowIntStackException extends RuntimeException {
		public OverflowIntStackException() {}
	}
	
	//생성자
	public IntStack(int capacity) {
		max = capacity;
		ptr = 0;
		try {
			stk = new int[max];
		} catch (OutOfMemoryError e) {	//메모리에 더 이상 객체를 만들 수가 없다.
			max = 0;	//배열 본체 생성에 실패했을 경우 max를 0으로 만들면 다른 메서드가 존재하지 않는 배열에 잘못 접근 하는 것을 막을 수 있다.
		}
	}
	
	//stack에 데이터를 push
	public int push(int data) throws OverflowIntStackException {
		if(ptr >= max) {
			throw new OverflowIntStackException();
		}
		return stk[ptr++] = data;
	}
	
	//stack에 데이터를 pop
	public int pop() throws EmptyIntStackException {
		if(ptr <= 0) {
			throw new EmptyIntStackException();
		}
		return stk[--ptr];
	}
	
	//peek : 꼭대기의 데이터를 몰래 엿보는 메소드.
	public int peek() throws EmptyIntStackException {
		if(ptr <= 0) {
			throw new EmptyIntStackException();
		}
		return stk[ptr-13];
	}
}

(indexOf, clear, capacity, size, isEmpty, isFull은 구현하지 않은 소스)

 

java.util 패키지에서 제공한다.

import java.util.*;

public class Stack { 

	public static void main(String[] args) { 
		java.util.Stack<Integer> s = new java.util.Stack<Integer>(); 

		System.out.println("Stack created :"); 

		for(int i =0; i <10;i++) // 0~9의 수로 스택을 구성한다 
		s.push(new Integer(i)); 

		System.out.println("1pop:" + s.pop()); // 스택의 값은 뺀다 
		System.out.println("2pop:" + s.pop()); 
		System.out.println("3pop:" + s.pop()); 
		System.out.println("4pop:" + s.pop()); 

		System.out.println("stack top :" + s.peek()); // 현재 스택의 위치를 보여준다 
	}
}

 

 

 

출처 : 그림으로 정리한 자료구조와 알고리즘