[코딩 인터뷰]자료구조 - 스택과 큐

 

[ 스택 구현하기 ]

👀 스택

: 제한적으로 접근할 수 있는 나열 구조로 LIFO(Last-In-First-Out)에 따라 자료를 배열합니다. 재귀 알고리즘을 사용할 때 유용하게 사용됩니다.

⭐ LIFO : 가장 최근에 추가한 항목이 가장 먼저 제거될 항목

⭐ 재귀 알고리즘을 사용할 때 임시 데이터를 스택에 넣어놓고 재귀 함수 완료 후 스택에 넣어 두었던 임시 데이터를 빼는 형식으로 주로 사용됩니다.

 

👀 Java로 구현

public class MyStack{
    private static class StackNode{
        private T data;
        private StackNode next;
        public StackNode(T data){
            this.data = data;
        }
    }
    
    private StackNode top;
    public T pop(){
        if(top == null) throw new EmptyStackException();
        T item = top.data;
        top = top.next;
        return item;
    }
    
    public void push(T item){
        StackNode t = new StackNode(item);
        t.next = top;
        top = t;
    }
    
    public T peek(){
        if(top==null) throw new EmptyStackException();
        return top.data;
    }
    
    public boolean isEmpty(){
        return top == null;
    }
    
}

 

👀 Python으로 구현(굳이 class로 구현한다면)

class MyStack:
    def __init__(self):
        self.items = []

    def pop(self):
        try:
            return self.items.pop()
        except Exception as e:
            return e

    def push(self, item):
        self.items.append(item)

    def peek(self):
        try:
            return self.items[-1]
        except Exception as e:
            return e

    def isEmpty(self):
        return not self.items

 

⭐ 연산

• pop() : 가장 위에 있는 항목 제거
• push(item) : item 하나를 가장 위에 추가
• peek() : 가장 위의 항목 반환
• isEmpty() : 비어 있을 때 true 반환

⭐ T

: 제네릭(Generic)의 Type에 해당됩니다.

 

Java에서 제네릭(Generic)이란?

→ 클래스 내부에서 지정하는 것이 아닌 사용자에 의해 지정되는 것을 의미합니다. 

 

장점

1. 클래스나 메소드 내부에서 사용되는 객체의 타입 안정성 증가
2. 반환값에 대한 타입 변환 및 타입 검사에 들어가는 노력 감소

 

타입	설명
<T>	타입(Type)
<E>	원소(Element)
<K>	키(Key)
<V>	값(Value)
<N>	숫자(Number)

---

 

 

[ 큐 구현하기 ]

👀 큐

: 제한적으로 접근할 수 있는 나열 구조로 FIFO(First-In-First-Out)에 따라 자료를 배열합니다. 너비 우선 탐색(BFS: Breadth-First Search)을 하거나 캐시를 구현할 때 사용됩니다.

⭐ FIFO : 추가한 항목 순서대로 제거

⭐ 너비 우선 탐색을 하는 경우 처리해야 할 노드의 리스트를 저장하는 용도로 사용했습니다. 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장하고 순서대로 처리합니다.

 

👀 Java로 구현

public class MyQueue{
    private static class QueueNode{
        private T data;
        private QueueNode next;
        public QueueNode(T data){
            this.data = data;
        }
    }
    
    private QueueNode first;
    private QueueNode last;
    
    public void add(T item){
        QueueNode t = new QueueNode(item);
        if(last != null){
            last.next = t;
        }
        last = t;
        if(fist == null){
            first = last;
        }
    }
    
    public T remove(){
        if(first == null) throw new NoSuchElementException();
        T data = fist.data;
        first = first.next;
        if(first == null){
            last = null;
        }
        return data;
    }
    
    public T peek(){
        if(first == null) throw new NoSuchElementException();
        return first.data;
    }
    
    public boolean isEmpty(){
        return first == null;
    }
}

 

👀 Python으로 구현(굳이 class로 구현한다면)

class MyQueue:
    def __init__(self):
        self.items = []

    def add(self, item):
        self.items.append(item)

    def remove(self):
        try:
            self.items.pop(0)
        except Exception as e:
            return e

    def peek(self):
        try:
            return self.items[0]
        except Exception as e:
            return e

    def isEmpty(self):
        return not self.items

 

⭐ 연산

• add(item) : item을 끝부분에 추가
• remove() : 첫 번째 항목 제거
• peek() : 가장 위에 있는 항목 반환
• isEmpty() : 비어 있을 때에 true 반환