[DataStructure] 스택(stack)

스택이란 ?

한 쪽 끝에서만 입, 출력 가능한 LIFO(Last In First Out) 형식의 자료 구조

연산

스택(Stack)은 LIFO(Last In First Out)를 따른다.
즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

구현

문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.
하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.
스택(Stack)은 연결리스트 로 구현할 수 있다.
-> 연결리스트의 같은 방향에서 아이템을 추가하고 삭제하도록 구현한다.

Python을 이용한 stack 구현

class Stack:
    #리스트를 이용하여 스택 생성
    def __init__ (self):
        self.top = []
        
Stack 클래스를 생성하고 init method를 이용하여 멤버 변수를 만들어준다.
top 변수 안에는 파이썬에 내장되어 있는 리스트(list)를 이용하여 스택을 만들어 준다.

#스택의 크기를 출력
    def __len__(self):
        return len(self.top)

    #스택 내부 자료를 string으로 변환하여 반환
    def __str__(self):
        return str(self.top[::1])
        
__len__과 __str__를 작성한다.
len은 스택의 크기(길이)를 반환하고
str은 스택 내부에 저장된 모든 데이터를 string형태로 변환하여 반환하도록 한다.

PUSH
    def push (self, item):
        self.top.append(item)
파이썬 list에 내장되어 있는 append함수를 사용하여 리스트 끝에 값을 추가한다.

POP
    def pop(self):
        #if Stack is not empty
        if not self.isEmpty():
            #pop and return 
            return self.top.pop(-1)
        else:
            print("Stack underflow")
            exit()
            
먼저 isEmpty를 호출하여 스택이 비어있는지 확인한다.
isEmpty는 직접 작성해주어야한다.

파이썬 list 안에 내장되어 있는 함수 pop에 -1이라는 인자를 넘겨
리스트 가장 마지막에 있는 데이터를 꺼낸다.

CLEAR
#스택 초기화
    def clear(self):
        self.top=[]
Stack클래에 멤버변수인 top을 새로운 리스트로 초기화해준다.
기존 top에 있던 모든 데이터는 더이상 포인팅할 수 없다.

isContain
#자료가 포함되어 있는지 여부 반환
    def isContain(self, item):
        return item in self.top
        
peek
#스택에서 top의 값을 읽어온다
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
        else:
            print("underflow")
            exit()
리스트 인덱싱을 이용하여 top리스트의 가장 마지막 원소(자료)를 반환시킨다.

isEmpty
#스택이 비어있는지 확인
    def isEmpty(self):
        return len(self.top)==0
        
size
 #스택 크기 반환
    def size(self):
        return len(self.top)

출처

동적 배열 스택

위의 python 구현 방식으로는 MAX_SIZE라는 최대 크기가 존재해야 함
why? 스택 포인터와 MAX_SIZE를 비교해서 isFull 메소드로 비교해야되기 때문 !

최대 크기가 없는 스택을 만들기 위해서는,
arraycopy를 활용한 동적배열을 사용해야 한다.

public void push(Object o) {
    
    if(isFull(sp)) {
        
        Object[] arr = new Object[MAX_SIZE * 2];
        System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
        stack = arr;
        MAX_SIZE *= 2; // 2배로 증가
    }
    
    stack[sp++] = o;
}

기존 스택의 2배 크기만큼 임시 배열(arr)을 만들고
arraycopy를 통해 stack의 인덱스 0부터 MAX_SIZE만큼을 arr 배열의 0번째부터 복사한다
복사 후에 arr의 참조값을 stack에 덮어씌운다
마지막으로 MAX_SIZE의 값을 2배로 증가시켜주면 된다.
이러면, 스택이 가득찼을 때 자동으로 확장되는 스택을 구현할 수 있음

연결리스트로 구현하기

public class Node {

    public int data;
    public Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Stack {
    private Node head;
    private Node top;

    public Stack() {
        head = top = null;
    }

    private Node createNode(int data) {
        return new Node(data);
    }

    private boolean isEmpty() {
        return top == null ? true : false;
    }

    public void push(int data) {
        if (isEmpty()) { // 스택이 비어있다면
            head = createNode(data);
            top = head;
        }
        else { //스택이 비어있지 않다면 마지막 위치를 찾아 새 노드를 연결시킨다.
            Node pointer = head;

            while (pointer.next != null)
                pointer = pointer.next;

            pointer.next = createNode(data);
            top = pointer.next;
        }
    }

    public int pop() {
        int popData;
        if (!isEmpty()) { // 스택이 비어있지 않다면!! => 데이터가 있다면!!
            popData = top.data; // pop될 데이터를 미리 받아놓는다.
            Node pointer = head; // 현재 위치를 확인할 임시 노드 포인터

            if (head == top) // 데이터가 하나라면
                head = top = null;
            else { // 데이터가 2개 이상이라면
                while (pointer.next != top) // top을 가리키는 노드를 찾는다.
                    pointer = pointer.next;

                pointer.next = null; // 마지막 노드의 연결을 끊는다.
                top = pointer; // top을 이동시킨다.
            }
            return popData;
        }
        return -1; // -1은 데이터가 없다는 의미로 지정해둠.

    }

}