Stack(스택) & Queue(큐)

Stack

• 선형 자료구조의 일종으로 후입 선출(Last In First Out :LIFO) 방식이다. 즉, 나중에 들어간 원소가 먼저 나오는 특징을 가지고 있다.
• 데이터를 쌓아 올리는 구조로 먼저 Stack에 들어간 데이터는 맨 바닥에 깔린다. 따라서 늦게 들어간 원소는 맨 위에 놓이게 되고 호출시 가장 먼저 나가게된다.
• 입력(push), 출력(pop-java에서는 poll), 가장 위에 있는 데이터 확인(peek), 해당 값이 스택에서 몇번째 있는지(search) 등이 있다.
• 스택은 Random Access(비순차적 접근)이 불가능하다.
• 삽입/삭제는 O(1)의 시간 복잡도를 갖는다.
• 스택은 재귀 알고리즘을 사용할 때 유용하다.
  • 재귀적으로 함수를 호출해야하는 경우, 임시 데이터를 스택에 넣고 재귀 함수를 빠져나와 백트레킹을 할 때는 스택에 넣어 주었던 임시 데이터를 빼줘야한다. 
  • 한 번 재귀 호출이 일어날 때 마다 계속 스택에 쌓아가므로 신중하게 사용해야한다.

 

출처 : 위키백과

public class mStack {
	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;
    }
}

 

Queue

• 선형 자료구조의 일종으로 선입선출(First In First Out :FIFO) 방식이다. 즉, 먼저 들어간 요소가 먼저 나온다.
• 데이터가 큐로 들어오는 동작(enqueue), 큐에서 나가는 동작은(dequeue)이다.
• 보통 큐는 연결 리스트(LinkedList)를 사용하여 구현한다.
• 큐는 BFS, 캐시를 구현할 때 주로 사용된다. (BFS 경우 처리해야하는 노드의 리스트를 저장하는 용도로 큐를 사용한다.)
• 참고로 Java Collection 에서 Queue 는 인터페이스이다. 이를 구현하고 있는 Priority queue등을 사용할 수 있다.
• 큐는 여러가지 종류가 존재하는데 원형 큐, 우선순위 큐, 데크(Deque) 등이 있다.
• 참고로 자바의 컬랙션 중 큐에 대한 시간 복잡도 정리는 다음을 참고하길 바란다.
  • (https://hee96-story.tistory.com/89)

 

출처 : 나무위키

public class mQueue {
	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 (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 NoSuchElementException();
            return first.data;
       	}
        
       	public boolean isEmpty() {	
        	return first == null;
       	}
	}
}

 

원형 큐

• 원형 큐는 선형 큐를 쓰다보면 배열의 앞부분이 비게 되는 한계점을 해결하기 위해 구조화한 자료구조이다.
• 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 (rear+1) % 배열 사이즈 가되며 배열의 첫 인덱스부터 다시 데이터 삽입이 가능하다.
• 만약 큐가 포화상태이면 (rear+1) % 배열 사이즈 ==front 이면 enqueue가 실행되지 않는다.

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=kciter&logNo=100199946363&proxyReferer=https:%2F%2Fwww.google.com%2F

 

우선순위 큐

• 우선순위 큐는 원소들에 우선순위를 매겨서 큐에 넣는다. 그래서 들어간 순서와 상관없이 뺄 때는 우선순위가 높은 원소부터 빠진다.
• 힙(Heap)을 구현할 때 주로 사용된다.

 

데크(Deque : Double Ended Queue)

• 데크는 양쪽에서 모두 삽입/인출이 가능한 큐이다.
• 스택과 큐의 장점을 가지고 만들어졌다.
• 입력이 한쪽에서만 가능하고 출력은 양쪽다 가능한 경우는 Scroll
• 출력이 한 쪽에서만 가능하고 입력이 양쪽에서 가능한 경우는 Shelf라고 한다.

 

출처 : 나무위키

추가로 공부하면 좋을 것

• Queue 를 사용하여 Heap 자료구조 구현하기
• Stack 두 개로 Queue 자료구조 구현하기

추가 개념

• 선형 자료구조 : 자료를 구성하는 데이터를 순차적으로 나열시킨 형태
• 비선형 자료구조 : 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태

참고

https://devowen.com/211

DS #3. 스택과 큐 (Stack and Queue)

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#stack-and-queue

JaeYeopHan/Interview_Question_for_Beginner