[알고리즘] 자료구조 스택(Stack)

스택(Stack)

• 데이터를 제한적으로 접근할 수 있는 구조
  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
  • 큐: FIFO 정책
  • 스택: LIFO 정책

 

용도 및 예제

대표적으로 많이 사용하는 곳이 브라우저이다. 인터넷 서칭 중 뒤로 가고 싶을 때 뒤로 가기 버튼을 누른다. '뒤로 가기' 버튼이 바로 스택으로 구현된 메소드 중 하나이다.

 

스택 구조

• 스택은 LIFO(Last In, First Out) 또는 FIFO(Frist In, Last Out) 데이터 관리 방식을 따름
• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  • 
• 주요 기능
  • push(): 데이터를 스택에 넣기
  • pop(): 데이터를 스택에서 꺼내기
  • peek(): 마지막 위치에 해당하는 데이터 읽기(변화는 없다)

 

자료 구조 스택의 장단점(참고만 하기)

• 장점
  • 구조가 단순해서, 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점
  • 데이터 최대 갯수를 미리 정해야 한다.
  • 저장 공간의 낭비가 발생할 수 있다.
    • 미리 최대 갯수만큼 저장 공간을 확보해야 한다.

스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. 이 경우, 위에서 열거한 단점이 있을 수 있다.

 

Java에서의 스택 자료 구조 사용

• 자료구조와 알고리즘은 주요 개념을 이해하고, 알고리즘은 변수, 조건, 반복문으로 직접 구현할 수 있어야 한다.

import java.util.Stack;

import javax.lang.model.element.Element;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();//push, pop, peek, empty, seach 지원
        for(int i=1; i<=5 ; i++) {
            stack.push(i);
            System.out.println(stack.peek());
        } //1, 2, 3, 4, 5 출력
        stack.pop();
        System.out.println("Pop()");
        System.out.println(stack.peek());    //4출력
        System.out.println(stack.search(3));    //2출력
        System.out.println(stack.empty());    //false출력
    }

• For문을 통해 1~5 숫자를 스택에 Push 한다.
• stack.pop()으로 제일 최근에 들어간 값을 제거한다.
• stack.peek()으로 가장 최근에 들어간 값을 출력한다.(5가 pop()으로 제거되었으니 가장 최근에 넣은 값은 4이므로, 4가 출력되게 된다.
• stack.search(3)은 3의 인덱스를 출력해준다. 맨 밑부터 인덱스가 0,1,2,3 이므로 '3'은 현재 인덱스 2에 위치해 있다
• stack.empty()는 현재 스택이 비었으면 True, 값이 들어가 있으면 False를 출력해준다. 현재 스택에 값이 들어가 있으므로 출력 값은 False이다.

 

스택의 구현 방법은 배열을 사용하는 것과 연결 리스트를 사용하는 것 두 가지가 있다.

두 방법 모두 장단점이 존재한다. 배열의 장점은 구현이 쉽고, 원하는 데이터의 접근 속도가 빠르다. 만약 내가 원하는 데이터가 배열의 3번째 위치에 있다면 arr [2]를 사용한다면 한 번에 접근이 가능하기 때문이다. 하지만 단점으로는 데이터 최대 개수를 미리 정해야 하기 때문에 데이터의 삭제와 삽입에 있어서 매우 비효율 적이다.
만약 데이터가 10000개의 데이터가 있다고 가정하다. 중간의 데이터를 삭제하거나 삽입해야 할 때 그 뒤에 있는 모든 데이터를 한 칸씩 옮겨야 한다. 이것은 시간적으로 엄청난 손해이다.

연결 리스트의 장점으로는 데이터의 최대 개수가 한정되어 있지 않고, 데이터의 삽입 삭제가 용이하다. 연결리스트의 구조는 배열과 다르게 데이터들이 순차적으로 나열되어 있지 않다. 아래 그림처럼 연결리스트를 구성하고 있는 요소를 노드라고 한다. 이 노드는 데이터와 다음 위치에 해당하는 노드의 주소값을 갖는다. 이러한 구조 때문에 연결리스트 중간에 데이터를 삽입하는 방법은 쉽다. 다음 위치에 해당하는 노드의 주소 값만 바꿔주면 되기 때문이다. 하지만 치명적인 단점은 배열과 다르게 한 번에 원하는 데이터의 접근이 불가능하다는 것이다. 연결되어 있는 링크를 따라 차근차근 하나씩 확인하며 데이터를 찾아야 하기 때문이다.

 

배열로 스택 구현

public class ArrayStack {
    int top;    //인덱스
    int size;    //스택 배열의 크기
    int [] stack;
    public ArrayStack(int size) {
        this.size = size;
        stack = new int[size];
        top = -1;
    }
}

멤버 변수에 top, size, [] stack을 지정해 준다. 생성자로 멤버 변수들을 초기화해주면서 stack배열을 size만큼 초기화해준다.

public class ArrayStack {
    int top;    //인덱스
    int size;    //스택 배열의 크기
    int [] stack;
    public ArrayStack(int size) {
        this.size = size;
        stack = new int[size];
        top = -1;
    }

    public void push(int item) {
        stack[++top] = item;
        System.out.println(stack[top] + " Push!");
    }
    public void pop() {
        System.out.println(stack[top] + " Pop!");
        int pop = stack[top];
        stack[top--] = 0;
    }
    public void peek() {
        System.out.println(stack[top] + " Peek!");
    }
}

배열을 초기화해줄 때 int [] stack = new int [5]을 하게 되면 배열의 크기는 5가 되고 값은 null 초기화된다. 배열의 값들을 제거할 때는 배열의 데이터 형태가 int형태이므로 null이 아닌 0 값을 임의로 넣어줬다.

 

LinkedList로 스택 구현

public class Node {
    private int item;
    private Node node;

    public Node(int item) {
        this.item = item;
        this.node = null;
    }

    protected void linkNode(Node node) {//가르킬 노드를 지정
        this.node = node;
    }
    protected int getData() {
        return this.item;
    }
    protected Node getNextNode() { //다음 노드를 리턴
        return this.node;
    }
}

//LinkedListStack을 관리하는 클래스
public class NodeManager {
    Node top; //가장 최근에 들어온 노드를 가리킴

    public NodeManager() {
        this.top = null;
    }
    public void push(int data) {
        Node node = new Node(data);    //노드를 생성
        node.linkNode(top);    //새로 생성된 노드가 top이 가르키고 있는 노드를 맄크로 연결하게 함
        top = node;    //top의 값을 가장 최근에 생성된 node로 바꿈
    }
    public void pop() {
        top = top.getNextNode(); // 현재 top이 가리키고 있는 노드를 가리키게 함
    }
    public int peek() {
        return top.getData();
    }
}

 

 

이처럼 배열, 연결 리스트의 각각의 장단점이 있다. 배열은 데이터 양이 많지만 삽입/삭제가 거의 없고. 데이터의 접근이 빈번히 이뤄질 때 유리하다. 반대로 연결 리스트는 삽입/삭제가 빈번히 이뤄지고, 데이터의 접근이 거의 없을 때 유리하다.
각각의 상황에 맞게 배열을 사용할지, 연결 리스트를 사용할지가 중요할 것이다.