[Data Structure] 스택

스택은 삽입과 삭제가 한쪽 끝 top에서만 이루어지는 유한 순서 리스트이며 주로 사용하는 함수가 push, pop이기에 pushdown 리스트라고도 한다.

스택은 LIFO(Last In First Out) 방식이기 때문에 스택을 역순으로 만드는데 유용하다.

스택 ADT

ADT Stack
데이타 : 0개 이상의 원소를 가진 유한 순서 리스트
연산 :
    stack ∈ Stack; 
    item ∈ Element;
    createStack() ::= create an empty stack;

    push(stack, item) ::= insert item onto the top of the stack;

    isEmpty(stack) ::= if (stack is empty) then return true
    else return false;

    pop(stack) ::= if (isEmpty(stack)) then return null
    else { delete and return the top item of stack };

    delete(stack) ::= if (isEmpty(stack)) then return error    
    else delete the top item;

    peek(stack) ::= if (isEmpty(Stack)) then return error
    else return (the top item of stack);
End Stack

stack 생성자

stack 배열과 top 변수를 두어 스택의 top원소를 가리키게 한다. 스택을 생성하면 top = -1 로 초기화 시킨다.
top = -1 이라면 공백 스택임을 표시한다.

class Stack {
    private String stack[];
    private int top;
    public Stack(int n) {
        stack = new String[n];
        top = -1;
    }

isEmpty 연산자

top이 -1이라면 공백 스택임을 표시하는 것이기 때문에 top 변수안에 들어있는 값으로 스택이 비어있는지 확인할 수 있다.

public boolean isEmpty() {
    return (top < 0);
}

push 연산자

새로운 원소가 들어가면 top을 증가시키고 만약 top이 stack 배열크기보다 크다면 인덱스초과에러를 발생시킨다.

public void push(String item) {
    if (top >= stack.length) 
        throw new IndexOutOfBoundsException();
    top++;
    stack[top] = item;
}

pop 연산자

top이 0보다 작다면 스택이 비어있기 때문에 인덱스에러를 발생시키고 그렇지 않다면 top에 담겨있는 원소를 리턴하고 top을 1감소 시킨다.

public String pop() {
    if (top < 0) throw new IndexOutOfBoundsException();
    String item = stack[top];
    top--;
    return item;
}

peek 연산자

pop연산자와 다른 점은 연산을 실행 후 그 원소를 배열내에서 없애지만 peek연산자는 top에 있는 원소를 리턴해주기만 한다.

public String peek() {
    if (top < 0) throw new IndexOutOfBoundsException();
    return stack[top];
}

delete 연산자

pop연산자와 다른점은 top 원소를 리턴하면서 원소를 삭제시킨다면 delete는 원소를 리턴하지 않고 삭제시킨다.

public void delete() {
    if (top < 0) 
        throw new IndexOutOfBoundsException();
    top--;
}

연결 리스트를 이용한 스택

연결 리스트로 표현된 연결 스택으로 생각할 수 있다.

public class ListStack implements Stack {
    class ListNode {
        Object data;
        ListNode link;
    }

    private ListNode top;
    public boolean isEmpty() { // 스택이 공백인가를 검사
        return (top == null);
    }
    public void push(Object x) { // 스택에 원소 x를 삽입
        ListNode newNode = new ListNode();
        newNode.data = x;
        newNode.link = top;
        top = newNode;
    }
    27 public Object pop() { // 스택의 원소를 삭제하여 반환
        if (isEmpty()) 
            return null; // 공백인 경우
        else {
            Object item = top.data;
            top = top.link;
            return item;
        }
    }
    public void delete() { // 연결 스택의 top 원소를 삭제
        if (isEmpty()) 
            return;
        else 
            top = top.link;
        }
    public Object peek() { // 스택의 top 원소를 검색
        if (isEmpty()) 
            return null;
        else 
            return top.data;
        }
    }