Stack과 Queue

stack과 queue를 java와 python으로 구현해보자.

 

[Stack]

stack은 LIFO(Last In First Out)로 동작하는 자료구조다. 일반적으로 함수 호출 시 스택구조를 사용한다. 따라서 스택을 사용해야 하는 알고리즘은 함수의 재귀호출로 대체할 수도 있다.

 

stack with java

import java.util.EmptyStackException;

public class Stack_New<T> {

    public static class Node<T> {
        private final T data;
        private Node<T> next;

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

        public T getData() {
            return this.data;
        }

        public Node<T> getNext() {
            return this.next;
        }

        public void setNext(Node<T> next) {
            this.next = next;
        }
    }

    Node<T> topNode;

    public T pop() {
        if (this.topNode == null) {
            throw new EmptyStackException();
        }
        T temp = topNode.getData();
        this.topNode = topNode.getNext();

        return temp;
    }

    public T peek() {
        if (this.topNode == null) {
            throw new EmptyStackException();
        }
        return topNode.getData();
    }

    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        newNode.setNext(this.topNode);
        this.topNode = newNode;
    }

    public Boolean isEmpty() {
        return topNode == null;
    }
}

 

Python은 사실 별도로 stack을 구현할 필요가 없는데 list type에서 제공하는 append(), pop()을 사용하거나 기본으로 제공하는 컬렉션 타입 중 dequeue 타입을 사용해서 append(), pop()을 사용하면 Stack 구조로 동작하기 때문이다. 하지만 학습을 위해 여기서는 직접 구현해보도록 하겠다.

 

stack with python

class Stack:
    class Node:
        def __init__(self, data):
            self.__data = data
            self.__next = None

        def get_data(self):
            return self.__data

        def get_next(self):
            return self.__next

        def set_next(self, next_node):
            self.__next = next_node

    def __init__(self):
        self.__top_node = None

    def pop(self):
        try:
            temp = self.__top_node.get_data()
            self.__top_node = self.__top_node.get_next()
            return temp
        except Exception as e:
            print("Empty Stack Exception")

    def peek(self):
        try:
            return self.__top_node.get_data()
        except Exception as e:
            print("Empty Stack Exception")

    def push(self, item):
        new_node = self.Node(item)
        new_node.set_next(self.__top_node)
        self.__top_node = new_node

    def is_empty(self):
        if self.__top_node is None:
            return True
        else:
            return False

 

 

 

 

 

[Queue]

queue는 FIFO(First In First Out)로 동작하는 자료구조다. OS의 명령대기줄 등에 사용된다.

 

queue with java

package me.dave;

import java.util.NoSuchElementException;

public class Queue<T> {
    public static class Node<T> {
        private final T data;
        private Node<T> next;

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

    Node<T> firstNode;
    Node<T> lastNode;

    public void add(T item) {
        Node<T> newNode = new Node<>(item);
        if(firstNode == null) {
            firstNode = newNode;
            lastNode = firstNode;
        } else {
            lastNode.next = newNode;
            lastNode = newNode;
        }
    }

    public T remove() {
        if(firstNode == null) {
            throw new NoSuchElementException();
        }
        T data = firstNode.data;
        firstNode = firstNode.next;
        return data;
    }

    public T element() {
        if(firstNode == null) {
            throw new NoSuchElementException();
        }
        return firstNode.data;
    }

    public T peek() {
        if(firstNode == null) {
            return null;
        }
        return firstNode.data;
    }

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

 

queue with python

class Queue:
    class Node:
        def __init__(self, data):
            self.__data = data
            self.__next = None

        def get_data(self):
            return self.__data

        def get_next(self):
            return self.__next

        def set_next(self, next_node):
            self.__next = next_node

    def __init__(self):
        self.__first_node = None
        self.__last_node = None

    def add(self, item):
        new_node = self.Node(item)
        if self.__first_node is None:
            self.__first_node = new_node
            self.__last_node = self.__first_node
        else:
            self.__last_node.set_next(new_node)
            self.__last_node = new_node

    def remove(self):
        try:
            data = self.__first_node.get_data()
            self.__first_node = self.__first_node.get_next()
            return data
        except Exception as e:
            print("NoSuchElementException", e)

    def element(self):
        try:
            return self.__first_node.get_data()
        except Exception as e:
            print("NoSuchElementException", e)

    def peek(self):
        return self.__first_node.get_data()

    def is_empty(self):
        if self.__first_node is None:
            return True
        else:
            return False