스택

• 스택은 자료를 접시처럼 쌓아올린 구조의 자료구조이다.
• LIFO(Last-In-Frst-Out) 의 특징을 갖는다.

1. 배열을 이용한 스택

생성자

public ArrayStack(int stackSize)
{
    top = -1;
    this.stackSize = stackSize;
    itemArray = new char[this.stackSize];
}

• 스택 첫 자료의 index는 '0' 이므로, 초기의 top index는 -1로 설정한다.
• 생성자의 매개변수로 배열의 크기를 입력받아, 배열을 생성한다.

isEmpty(), isFull()

public boolean isEmpty()
{
    return (top == -1);
}

public boolean isFull()
{
    return (top == stackSize -1);
}

• isEmpty() : 스택의 현재 index를 나타내는 top을 이용해, 스택이 비었는지 확인한다.
• isFull() : 스택의 top을 배열의 크기와 비교하여 스택이 꽉 찼는지 확인한다.

push()

public void push(char item)
{
    if(isFull())
    {
        System.out.println("stack full!");;
    }
    else
    {
        itemArray[++top] = item;
    }
}

• 스택이 꽉 찼는지 아닌지, isFull 메소드로 확인한다.
• 스택의 top을 증가시키고, item를 넣는다.

pop()

public char pop()
{
    if(isEmpty())
    {
        System.out.println("stack empty!");
        return 0;
    }
    else
    {
        return(itemArray[top--]);
    }
}

• 스택이 비어있는지 아닌지, isEmpty 메소드로 확인한다.
• 스택의 top index의 값을 반환하고, top을 감소시킨다.

delete()

public void delete()
{
    if(isEmpty())
    {
        System.out.println("stack empty!");
    }
    else
    {
        top--;
    }
}

• 스택이 비어있는지 아닌지, isEmpty 메소드로 확인한다.
• top을 감소시켜, 자료를 제거만 한다.

peek()

public char peek()
{
    if(isEmpty())
    {
        System.out.println("stack empty!");
        return 0;
    }
    else
    {
        return itemArray[top];
    }
}

• 스택이 비어있는지 아닌지, isEmpty 메소드로 확인한다.
• 스택의 꼭대기값을 반환만 한다.

2. 연결 리스트를 이용한 스택

스택의 노드 클래스

리스트 스택의 클래스

• stack의 down 멤버는, 해당 노드의 바로 아래 노드를 가리킨다.

isEmpty()

public boolean isEmpty()
{
    return (top == null);
}

isFull()

• 리스트를 이용한 스택은 배열처럼 크기가 고정적으로 정해지지 않았기 때문에, 스택이 꽉 찼는지 체크할 필요가 없다.

push()

public void push(char data)
{
    StackNode newNode = new StackNode();
    newNode.data = data;
    
    newNode.down = top;
    top = newNode;
}

• newNode의 down이 원래 top를 가리키도록 한다.
• newNode를 새로운 top으로 지정한다

delete()

public void delete()
{
    if(isEmpty())
    {
        System.out.println("stack empty!");
    }
    else
    {
        top = top.down;
    }
}

• 자료를 반환하지 않고, top만 아래로 이동시킨다.

peek()

public char peek()
{
    if(isEmpty())
    {
        System.out.println("stack empty!");
        return 0;
    }
    else
    {
        return top.data;
    }
}

• top을 움직이지 않고, top에 있는 자료만 반환한다.

참고문헌

[자바로 배우는 쉬운 자료구조] ,한빛아카데미