[면접을 위한 CS 전공지식 노트][자료구조] Stack(스택)

0. 개요

 배열과 리스트에 대한 정리가 끝났으니, 다음 자료구조는 스택과 큐이다. 그 중 스택을 먼저 정리하려고 한다.

 

1. Stack

 스택의 구조는 간단하다. LIFO(Last In First Out)가 핵심이다. 이것을 알고 있다면 이미 스택에 대해서 99.9%는 이해했다고 생각해도 무방하다. 스택에서는 push를 할 경우 스택에 데이터가 쌓이고, pop을 할 경우에는 가장 최근에 push된 데이터를 꺼내는 구조이다. 그리고 peek을 하게 되면 스택에 최 상위 top에 있는 데이터의 정보를 읽어올 수 있다.

 

 스택의 기능을 명세한 인터페이스

 

스택이 가지고 있는 기능의 핵심을 명세했다.

 

push: data를 스택에 집어 넣는다.

pop: 가장 최근에 넣은 데이터를 스택에서 꺼낸다.

peek: 가장 최근에 넣은 데이터를 꺼내지 않고 읽어온다.

size: 스택의 크기를 int 값으로 반환.

isEmpty: 스택이 비어있는지 boolean 값으로 반환.

public interface IStack<T> {
    void push(T data);
    T pop();
    T peek();
    int size();
    boolean isEmpty();
}

 

 스택 인터페이스를 바탕으로 구현한 스택

public class MyStack<T> implements IStack<T> {

    private int size;
    private Node head;

    public MyStack() {
        this.size = 0;
        this.head = new Node(null);
    }

    @Override
    public void push(T data) {
        Node node = new Node(data, this.head.next);
        head.next=node;
        size++;
    }

    @Override
    public T pop() {
        if(isEmpty()){
            return null;
        }
        Node curr = head.next;
        head.next=curr.next;
        curr.next=null;
        size--;
        return curr.data;
    }

    @Override
    public T peek() {
        if(isEmpty()){
            return null;
        }
        return head.next.data;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return head.next==null;
    }

    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

2.  시간복잡도

자료구조	접근	탐색	삽입	삭제	비고
스택	O(n)	O(n)	O(1)	O(1)	링크를 타고 순회

1) 접근

 스택에서 원하는 데이터에 접근한다고 가정했을 때 그 데이터가 맨 처음 넣은 데이터 일 경우 n번 pop을 해야하기 때문에 시간복잡도는 O(n)

 

2) 탐색

 접근과 마찬가지로 탐색 한다고 했을 때 모든 노드를 순회해야할 수 있으므로 시간복잡도는 O(n).

 

3) 삽입, 삭제

 스택은 LIFO이기 때문에 삽입삭제는 맨 마지막에 삽입하거나, 맨 마지막에 들어온 데이터를 삭제하게 된다. 이 경우는 한번만 연산을 실행하면 되므로 시간복잡도는 O(1).

3. 정리

 스택은 맨 나중에 들어온 데이터가 맨 처음 나오는 LIFO 구조이며, 재귀를 사용하는 함수나 알고리즘에 사용되며 웹브라우저 방문기록 등에 사용된다.

 구현된 push, pop, peek, isEmpty, size 메서드를 잘 이용하기만 한다면 스택을 사용하는 것에는 크게 문제가 없을 듯 하다. 이 스택이라는 자료구조를 이해하고, 어디에 응용할 수 있는지 문제를 풀어보면서 경험을 쌓는 것이 중요할 듯 하다.

 

 

참조

면접을 위한 CS 전공지식 노트

야놀자 테크스쿨 패스트캠퍼스 온라인 강의 - 자료구조/알고리즘