[자료구조] 큐(Queue)와 스택(Stack) 알아보기

이번 게시글에서는 큐와 스택에 대해서 알아보도록 하겠습니다.

---

01. 큐(Queue)

---

큐(Queue)는 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In, First Out) 구조로 저장하는 형식을 말합니다. 또 다르게 큐는 줄을 서는 행위와 유사하다고 할 수 있습니다.

번호 순서대로 들어오고, 번호 순서대로 나가는 Queue의 방식

 

FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식

 

1) Queue의 기능

• Enqueue : 큐에 데이터를 넣는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능

 

2) Queue의 메서드

메서드	설명
boolean add(Object o)	지정된 객체를 Queue에 추가 - 성공하면 true 반환 - 저장공간이 부족하면 IllegalStateException 발생
Object remove()	Queue에서 객체를 꺼내 반환 - 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어옴 - peek 와 달리 Queue가 비었을때 NoSuchElementException 발생
boolean offer(Object o)	Queue에 객체를 저장 - 성공하면 true, 실패하면 false 반환
Object poll()	Queue에서 객체를 꺼내서 반환 - 비어있으면  null 반환
Object peek()	삭제없이 요소를 읽어온다. - Queue가 비어있으면 null 반환

 

3) Queue 사용 예제

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue_int = new LinkedList<Integer>();
Queue<String> queue_str = new LinkedList<String>();

// 데이터 추가는 add(value) 또는 offer(value) 사용
queue_int.add(1);
queue_int.offer(2);

queue_int.poll(); // 큐의 첫 번째 값 반환, 해당 값은 큐에서 삭제
queue_int.remove(); // poll과 동일

 

4) Queue의 Enqueue와 Dequeue 직접 구현하기

ArrayList를 활용해서 Queue를 직접 구현한 코드입니다.

import java.util.ArrayList;

public class Queue<T> {
	
    private ArrayList<T> queue = new ArrayList<T>();
    
    /**
    * enqueue
    */
    public void enqueue(T item) {
    	queue.add(item);
    }
    
    /**
    * dequeue
    */
    public T dequeue() {
    	if (queue.isEmpty()) {
        	return null;
        } else {
        	return queue.remove(0);
        }
    }
    
    // queue 내부의 데이터 체크
    public StringBuilder look() {
    	StringBuilder sb = new StringBuilder();
        
        if (queue.isEmpty()) {
        	sb.append(0);
        } else {
        	for (int i=0; i<queue.size(); i++) {
            	Integer t = (Integer) queue.get(i);
                sb.append(t + ", ");
            }
        }
        
        return sb;
    }
    
    public boolean isEmpty() {
    	return queue.isEmpty();
    }
    
}

---

// 실행
public static void main(String[] args) {
	Queue<Integer> myQueue = new Queue<>();
    
    myQueue.enqueue(1);
    myQueue.enqueue(2);
    myQueue.enqueue(3);
    
    System.out.println(myQueue.look()); // 1,2,3
    
    System.out.println(myQueue.dequeue()); // 1
    System.out.println(myQueue.look()); // 2,3
}

 

---

---

02. 스택(Stack)

---

스택(Stack)의 사전적인 의미는 '쌓다' , '더미'입니다. 마치 여러 권의 책들이 수평으로 쌓인 형상과 유사합니다. 스택 또한 큐와 함께 자주 사용되는 기본적인 자료구조입니다. 하지만 큐와는 다른 특징을 갖고 있는데요.

스택은 '마지막에 추가된 데이터가 가장 먼저 나오는' 특징을 갖습니다. 큐에서는 FIFO 방식이었다면, 스택은 LIFO(Last-In, First-Out) 방식으로 동작합니다. 따라서 도식화를 하면 아래와 같습니다.

번호 순서대로 들어왔지만, 마지막 번호의 데이터부터 나가는 Stack의 방식

 

1) Stack의 메서드

메서드	설명
Object push(Object item)	Stack에 객체(item) 저장
Object pop()	Stack의 맨 위에서 저장된 객체를 꺼냄 - 비었을 때는 EmptyStackException 발생
Object peek()	Stack의 맨 위에 저장된 객체를 반환 - pop()과 달리 Stack에서 객체를 꺼내지 않음 - 비었을 때는 EmptyStackException 발생
boolean empty	Stack이 비어있는지 확인
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환, 못찾으면 -1 반환 * 배열과 달리 위치가 1부터 시작

 

2) Stack의 활용

• 재귀 알고리즘을 반복문을 통해서 구현할 수 있게 해 줌
• 실행 취소(undo)
• Backtracking
• 웹 브라우저 뒤로 가기
• 문자열의 역순 출력

 

3) Stack의 push와 pop 직접 구현하기

ArrayList를 활용해서 Stack을 직접 구현한 코드입니다.

import java.util.ArrayList;

public class Stack<T> {
	
    private ArrayList<T> stack = new ArrayList<T>();
    
    /**
    * push
    */
    public void push(T item) {
    	stack.add(item);
    }
    
    /**
    * pop
    */
    public T pop() {
    
    	if (stack.isEmpty()) {
        	return null;
        } else {
        	return stack.remove( stack.size() -1 );
        }
    }
}

 

---

// 실행
public static void main(String[] args) {

	Stack<Integer> myStack = new Stack<>();
    
    myStack.push(1);
    myStack.push(2);
    System.out.println(myStack.pop()); // 2
    
    myStack.push(3);
    System.out.println(myStack.pop()); // 3
    
    System.out.println(myStack.pop()); // 1
}