[자료구조론] 스택 & 큐

Stack

  선형 자료구조의 일종으로, 가장 마지막에 들어간 자료가 가장 먼저 출력되는 LIFO(Last In First Out) 구조를 갖는다.

스택은 기본적으로 push() 함수를 통해 데이터를 저장하고, pop() 함수를 통해 가장 마지막에 저장된 데이터를 꺼내온다. 

 

Implementing a Stack

  - pop() : 스택의 가장 위의 요소를 제거한다.

  - push(item) : 스택의 가장 위에 요소를 추가한다. 

  - peek() : 가장 위에 있는 요소를 반환해준다. (제거x)

  - isEmpty() : 스택이 비어있다면 true를 반환한다. 

 

*배열과는 다르게, 스택은 요소에 접근하는데 O(1)의 복잡도가 걸리지 않는다. 하지만 요소의 이동이 필요하지 않기 때문에 제거와 추가에서는 O(1) 의 시간이 걸린다. 

 

public class MyStack<T> {
     private static class StackNode<T> {
            private T data;
            private stackNode<T> next;
            
            public StackNode(T data) {
                this.data = data;
            }
            
            public StackNode<T> 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> t = new StackNode<T>(item);
               t.next = top;
               top = t;
            }
            
            public T peek(){
               if (top == null) throw new EmptyStackException();
               return top.data;
            }
            public boolean isEmpty(){
               return top == null;
            }
     }
}

Queue 

 선형 자료구조의 일종으로, FIFO (First In First Out)구조이다. '줄'을 의미하는 단어 그대로 처음 저장된 원소가 가장 먼저 출력된다. 

Implementing a Queue

  - enqueue(item) : 리스트의 끝에 요소를 넣어준다.

  - dequeue() : 리스트의 첫번째 요소를 제거한다. 

  - peek() : 큐의 정상에 있는 요소를 반환한다. 

  - isEmpty() : 큐가 비어있으면 true를 반환한다. 

public calss MyQueue<T> {
       private static class QueueNode<T> {
           private T data;
           private QueueNode<T> next;
           
           public QueueNode(T data) {
             this.data=data;
           }
           
           private QueueNode<T> first;
           private QueueNode<T> last;
           
           public void enqueue(T item) {
             QueueNode<T> t = enew QueueNode<T>(item);
             if (last != null) {
                 last.next = t;
             }
             last = t;
             if (first == null) {
                first = last;
             }
           }
           
           public T dequeue(){
                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 SuchElementExcepiton();
            return first.data;
          }
          public boolean isEmpty() {
            return first == null;
          }
       }
}