[자료구조] 스택(Stack) 개념과 구현

1. 스택(Stack)

스택의 사전적 의미는 '쌓다'입니다. 쌓여있는 접시, 책상 위에 쌓아 둔 책과 같이 차곡차곡 쌓아 올린 형태의 구조를 스택(Stack)이라 부릅니다.

 

이와 같이 일상에서 사용하는 스택의 개념을 추상화하여 자료구조로 만든 것이 스택 자료구조입니다.

2. 스택의 특징

1) 데이터의 삽입과 삭제는 top이라고 부르는 한쪽 끝에서만 이루어지도록 제한하여 만든 자료구조입니다.

스택의 구조

· 삽입 연산은 top의 위치를 하나 증가시킨 뒤 top이 가리키는 위치에 데이터를 삽입합니다.

· 삭제 연산은 top이 가리키고 있는 데이터를 스택에서 삭제하고 top의 위치를 하나 감소시킵니다.

 

2) 스택은 시간순서에 따라 데이터가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되므로 후입선출(LIFO, Last-In-First-Out)의 구조를 갖습니다.

 

후입선출(LIFO, Last-In-First-Out) 구조

3. 스택 알고리즘

· 삽입 연산(push)

push(S, x)
    top ← top + 1;				// ①
    if(top > STACK_SIZE) then overflow;
    else
    	S(top) ← x;				// ②
end push()

① top ← top + 1;

스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 데이터를 삽입하려면 먼저 top의 위치를 하나 증가시킵니다. 이때 top의 위치가 스택의 크기(STACK_SIZE)보다 크다면 오버플로우(overflow) 상태가 되므로 삽입 연산을 수행하지 못하고 연산이 종료됩니다.

 

② S(top) ← x;

오버플로우(overflow) 상태가 아니라면 스택의 top이 가리키는 위치에 x를 삽입합니다.

 

· 삭제 연산(pop)

pop(S)
    if(top = 0) then error;
    else{
    	x ← S(top);
        top ← top -1;
        return x;
    }
end pop()

빈 스택이 아니라면 top이 가리키고 있던 데이터를 저장한 뒤 top의 위치를 하나 감소시킵니다. 그리고 x값을 반환합니다.

4. 스택 구현

· Stack

public interface Stack {
	boolean isEmpty();
	void push(char data);
	char pop();
	char peek();
	void delete();
}

 

· ArrayStack

public class ArrayStack implements Stack {
	private int top;
	private int stackSize;
	private char[] stack;

	// 스택 초기화
	public ArrayStack(int stackSize) {
		this.top = -1;
		this.stackSize = stackSize;
		this.stack = new char[this.stackSize];
	}

	@Override
	public boolean isEmpty() {
		return (top == -1); // top이 -1이면 공백상태
	}

	public boolean isFull() {
		return (top == this.stackSize - 1); // top이 스택 사이즈와 같다면 포화상태
	}

	@Override
	public void push(char data) {
		if (isFull()) {
			System.out.println("스택이 포화상태입니다.\n");
		} else {
			stack[++top] = data; // top의 위치를 1 증가시킨 뒤 삽입
		}
	}

	@Override
	public char pop() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
			return 0;
		} else {
			return stack[top--]; // 데이터를 반환 후 top의 위치 1 감소
		}
	}

	@Override
	public char peek() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
			return 0;
		} else {
			return stack[top]; // top이 가리키는 데이터 반환
		}
	}

	@Override
	public void delete() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
		} else {
			top--; // top의 위치를 1 감소
		}
	}

	// 스택 출력
	public void printStack() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
		} else {
			System.out.printf("Stack : ");
			for (int i = 0; i <= this.top; i++) { // 인덱스 0부터 top까지 데이터를 출력
				System.out.printf("%c ", stack[i]);
			}
			System.out.printf("(top의 위치: %d)\n\n", getTop());
		}
	}

	// top의 위치 반환
	public int getTop() {
		return this.top;
	}
}

 

· MainForArrayStack

public class MainForArrayStack {
	public static void main(String[] args) {
		ArrayStack s = new ArrayStack(5);
		char data = 0;

		System.out.println("1. 스택에 원소 5개 삽입");
		for (char i = 'A'; i <= 'E'; i++) {
			s.push(i);
		}
		s.printStack();

		System.out.println("2. top이 가리키고 있는 원소 알아내기");
		System.out.printf("%c\n\n", s.peek());

		System.out.println("3. 스택의 원소 3개 팝");
		for (int i = 0; i < 3; i++) {
			data = s.pop();
			System.out.printf("삭제된 원소 : %c\n", data);
			s.printStack();
		}

		System.out.println("4. 스택의 원소 삭제");
		s.delete();
		s.printStack();
	}
}

 

· 실행 결과