공부/알고리즘

[자료구조 알고리즘] - Stack 과 Queue 구현하기

마라토너 2020. 6. 22. 21:50
반응형

 

안녕하세요.

Stack과 Queue라는 단어는 많이 들어보셨을 거예요.

그래서 오늘 살펴볼 기본 자료구조 알고리즘은 Stack과 Queue입니다.

정말 쉬운 알고리즘 중 하나이지만, 기초 개념입니다.

1. Stack

Stack은 영어 단어에서 알 수 있듯이 데이터를 쌓는 알고리즘입니다. Stack은 나중에 들어간 데이터가 먼저 나오는 구조인데요, 이것을 LIFO(Last In First Out)이라고 합니다. 마지막으로 들어가고 첫 번째 데이터부터 나오는 알고리즘입니다.
Stack은 데이터를 차곡차곡 쌓았다가 뒤에서부터 꺼내서 사용할 때 유용합니다.

Stack은 크게 4가지 함수로 구성되어 있습니다.

  1. pop()
  2. push()
  3. peek()
  4. isEmpty()

위 4가지 함수로 되어있고, 첫 번째 pop() 데이터의 맨 마지막의 데이터를 가져오면서 지우는 함수입니다. 두 번째 push()는 데이터에 차곡차곡 뒤에서부터 데이터를 쌓는 역할을 합니다. 세 번째 peek()은 마지막 데이터를 확인하는 용도로 사용합니다. 마지막 네 번째 isEmpty()는 데이터가 존재하는지를 확인하는 용도로 사용됩니다.

이제 간단하게 Stack에 대해서 알아봤으니 코드로 구현해 보아야겠지요? 다음 코드는 Java로 작성된 코드입니다.

class Stack<T> {
    class Node<T> {
        private T data;
        private Node<T> next;

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

    private Node<T> top;

    public T pop() {
        if (top == null) {
            throw new ExptyStackException();
        }

        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {
        Node<T> t = new Node<T>(item);
        t.next = top;
        top = t;
    }

    public T peek() {
        if(top == null) {
            throw new ExptyStackException();
        }

        return top.data;
    }

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

public class Test {
    public static void main (String[] args) {
        Stack<Integer> s = new Stack<Integer>();

        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.pop());         // 4
        System.out.println(s.pop());         // 3
        System.out.println(s.peek());         // 2
        System.out.println(s.pop());         // 2
        System.out.println(s.isEmpty());     // false
        System.out.println(s.pop());         // 1
        System.out.println(s.isEmpty());     // true
    }
}

다음 코드는 Python으로 구현을 해봤습니다.

class Stack(data):

    def__init__(self):
        self.stack = [];

    def pop(self):
        if len(self.stack) == 0:
            return -1
        return self.stack.pop()

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

    def peek(self):
        return self.stack[-1]

    def is_empry(self):
        if len(self.stack) == 0:
            return True
        return False

Python은 위와 같이 구현이 가능합니다.

Queue

다음은 Queue입니다.

Queue는 Stack과 반대로 앞의 데이터부터 꺼내서 사용하는 알고리즘입니다. 따라서 Queue는 FIFO(First In First Out) 앞에서부터 데이터를 쌓고 앞에서부터 데이터를 꺼내며 동작합니다.

Queue를 구성하는 4가지 함수는 다음과 같습니다.

  1. add()
  2. remove()
  3. peek()
  4. isEmpty()

우선 첫 번째 add()는 이름에서 알 수 있다시피 데이터를 순차적으로 저장하는 역할을 하는 함수입니다. 두 번째 remove()는 데이터의 맨 앞에서부터 꺼내서 삭제하는 역할을 하고, 세 번째 peek()은 첫 번째 데이터를 확인하는 용도로 사용됩니다. 마지막 isEmpty()는 Stack과 마찬가지로 데이터가 존재하는지를 확인하는 함수입니다.

Queue도 Java코드로 구현을 해보면 다음과 같이 구현을 할 수 있습니다.

class Queue<T> {
    class Node<T> {
        private T data;
        private Node<T> next;

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

    private Node<T> first;
    private Node<T> last;

    public void add(T item) {
        Node<T> t = new Node<T>(item);

        if(last != null) {
            last.next = t;
        }
        last = t;
        if(first == null) {
        first = last;
    }

    public T remove() {
        if (first == null) {
            throw new NoSuchElementException();
        }

        T data = first.data;
        first = first.next;

        if(first == null) {
            last = null;
        }
        return data;
    }

    public T peek() {
        if(first == null) {
            throw new NoSearchElementException();
        }
        return first.data;
    }

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


public class Test{
    public static void main (string[] args) {
        Queue<Integer> q = new Queue<Integer>();

        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);
        System.out.println(q.remove());         // 1
        System.out.println(q.remove());         // 2
        System.out.println(q.peek());         // 3
        System.out.println(q.remove());         // 3
        System.out.println(q.isEmpty());     // false
        System.out.println(q.remove());         // 4
        System.out.println(q.isEmpty());     // true

    }
}

위 와 같이 구현하여 데이터를 차곡차곡 쌓으면 앞에서부터 꺼내서 사용할 수 있습니다.

다음 코드는 Python으로 구현해 보았습니다.

class Queue(data):

    def__init__(self):
        self.queue = [];

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

    def remove(self):
        if len(self.queue) == 0:
            return -1
        return self.queue.pop(0)

    def peek(self):
        return self.stack[0]

    def is_empry(self):
        if len(self.queue) == 0:
            return True
        return False

결론

이번 글에서는 Stack과 Queue를 살펴봤습니다. 정말 간단하면서도 중요한 개념인데요. 위 Python뿐만 아니라 다른 많은 언어들에서는 간단한 자료구조는 내장 함수인 것도 상당히 많습니다. 알고리즘 대회나 실제로 알고리즘을 사용해서 구현해야 할 기능이 있다고 하면 직접 구현해서 쓰는 것보다는 기존 내장 함수를 사용하는 것이 더 안전하고 빠르다고 생각합니다. 이런 자료구조를 코드를 구현해보는 건 이해를 돕기 위해서입니다. 이해만 한다면 어디에서나 활용과 응용이 가능해질 테니깐요!☺️

 

앞으로도 각종 자료구조와 알고리즘을 공부하면서 글을 작성하려고 합니다. 한 번에 모든 걸 다 이해하고 기억할 수는 없는 것이기에 부담 없이 어떤 자료구조와 알고리즘이 있고 어떠한 상황에서 사용이 가능하다 정도만 알고 가는 게 목표입니다.

감사합니다.

반응형