Data structure(자료구조)란? - Stack & Queue(스택과 큐)

Data structure(DS)는 컴퓨터에서 데이터를 특정한 구조로 정리하여 데이터를 효율적으로 사용하기 위한 방법을 의미합니다.

자료구조의 종류는 다양한데, 지금까지 배워본 array나 collection framework에서 다룬 collection, map 등도 다 자료구조에 해당합니다! 생각해보면 각 자료구조들의 특징과 사용 방법이 조금씩 달랐습니다. 다량의 데이터를 한데 모아둔 것에 그치지 않고 데이터를 어떤 식으로 저장하고 이용할지 차이를 두었기 때문입니다. 이미 좋은 자료 구조들이 만들어져 있으니, 상황에 적절한 자료구조를 선택해서 사용할 수 있도록 하면 되겠습니다. ☺️

 

출처: shorturl.at/ilGZ8

 

이미 다룬 적이 있는 Array, LinkedList, Set은 제외하고 Stack, Queue, Tree, Graph를 알아보겠습니다.

Stack (class)

stack은 물건들이 쌓여있는 더미를 뜻하는 단어입니다. 

출처: 구글 shorturl.at/klnwL

그림처럼 책이 쌓여있을때 맨 아래 빨간 책을 읽고 싶다면 어떻게 해야 하나요? 무턱대고 가장 아래 책부터 뺄 수도있지만, 보통은 위의 책들을 다 빼낸 다음에야 맨 아래의 책을 뺄 수 있겠죠. 노란책을 빼고 싶을 때도 마찬가지로 위의 하늘색 책을 빼낸 다음에야 노란색 책을 빼낼 수 있습니다. 이렇게 물건이 stack으로 쌓여있다면 가장 위에서 부터 차례로 물건을 빼내며 원하는 물건에 접근할 수 있게됩니다. 

만약에 새로운 물건이 stack에 쌓일 때는 어떻게 되나요? 가장 위에 새로운 물건이 쌓이게 됩니다. 

 

데이터 구조에서의 stack도 이와 같습니다. Stack에 추가된 데이터는 나중에 들어온 순서대로 먼저 빼낼 수 있고 제일 먼저 들어와 있던 데이터는 가장 나중에 뺄 수 있습니다. 이것이 stack 구조의 가장 큰 특징이고 LIFO(Last In First Out) 이라고 부릅니다. 데이터를 하나씩만 처리할 수 있다는 것도 하나의 특징입니다. 

 

그렇다면 한 번 어떻게 사용하는 지 알아보겠습니다.

Stack은 class 이기 때문에, 사용하려면 먼저 instance를 생성해주면 됩니다. 

 

Stack<String> stack = new Stack<>();

이렇게 하면 Stack을 사용할 준비가 완료되었습니다.

Stack class에는 5개의 메서드가 정의되어 있는데, 어떻게 쓰이는지 예시로 살펴보겠습니다.

1) push()

먼저 위에서 생성한 stack은 현재 비어있는 상태일테니 요소를 추가해보겠습니다.

요소를 스택에 추가할 때는 .push() 메서드를 사용하면 됩니다. 

 

stack.push("1st");
stack.push("2nd");
stack.push("3rd");
stack.push("4th");
stack.push("5th");
 
System.out.println(stack);
//Prints [1st, 2nd, 3rd, 4th, 5th]

 

1st~5th까지 다섯개의 요소를 push해보았습니다. 데이터를 추가한 후 stack의 상태를 확인해 보니 차례로 잘 들어가(쌓여) 있습니다. 

 

2) pop()

이번에는 .pop()을 사용해서 나중에 들어온(쌓인) 순서대로 데이터를 제거하고 return 받도록 해보겠습니다. 

 

 
stack.pop();
stack.pop();
 
System.out.println(stack);
//Prints [1st, 2nd, 3rd]
 

 

두번 pop()을 시행하니 뒤에서부터(stack형태로 생각해보면 가장 위에 쌓여있는 데이터라고 생각하면 됩니다!) 차례로 5th와 4th가 지워진것을 확인할 수 있습니다. 첫 pop()시행 시에 5th가 지워지고 난 후 4th가 마지막 요소가 되었을 것이고, 한 번 더 pop()이 시행되니 그때 4th가 지워지게 됩니다. 

pop()은 따로 파라미터를 넣어줄 필요가 없는데, 애초에 가장 뒤의 데이터를 제거하고 return하기 때문입니다. 

 

pop()은 데이터를 지울 뿐만 아니라 지우는 데이터를 반환한다고 하였습니다. 그렇기 때문에 pop되는 데이터가 필요하다면, 변수에 할당해서 사용할 수도 있겠습니다. 

 

 
//pop된 데이터를 변수에 저장하여 사용
String poppedItem = stack.pop();
 
System.out.println(poppedItem); //Prints 3rd
 
System.out.println(stack); //Prints [1st, 2nd]
 

 

3) peek()

peek()을 사용하면 데이터를 지우지 않고도 마지막에 있는 데이터를 return할 수 있습니다. pop()과 마찬가지로 파라미터를 따로 넣어주지 않습니다. 

 

 
String peekItem = stack.peek();
 
System.out.println(peekItem); //Prints 2nd
 
System.out.println(stack); 
//Prints [1st, 2nd]
//마지막 데이터인 2nd가 삭제되지 않았음!
 
 
 

 

4) search(Object o)

 

search()를 사용하면 찾고자 하는 데이터가 몇번째에 위치했하고 있는지 알 수 있습니다. 이 메소드는 int type으로 위치를 반환합니다. 

여기서 유의할 점은 위치는 0이 아니라 1부터 시작한다는 것과 맨마지막의 데이터부터 순서를 센다는 점입니다!

예시에서 현재 남아있는 stack안의 요소들인 1st와 2nd를 search()를 사용해 몇번째에 있는지 확인해보겠습니다. 방금 얘기한대로라면 2nd를 search()했을 때는 숫자 1이 나오고 1st를 했을 때는 숫자 2가 나오겠죠? 

 

 
System.out.println(stack.search("2nd")); //Prints 1
System.out.println(stack.search("1st")); //Prints 2
 

IDE에서 확인해보면 예상한 대로 값이 반환되고 있음을 확인할 수 있습니다. 

 

Queue (interface)

Queue는 "대기줄" 을 뜻하는 단어입니다. 

 

출처: shorturl.at/jySZ0

마트에서 물건을 사기위해 계산대에 줄을 서있는 경우를 생각해보면 이해하기 쉽습니다. 

먼저 줄을 선 사람이 먼저 계산을 하게되고, 그 다음 사람이 다음 순서로 계산을 하게되고 마지막에 온 사람은 마지막에 계산을 하게됩니다.

이것이 Queue의 가장 큰 특징이며 FIFO(First In First Out) 라고 합니다. Stack과 마찬가지로 데이터를 하나씩만 처리할 수 있습니다. 

 

Queue는 인터페이스이기 때문에 queue를 implements 하고 있는 클래스를 사용해야 queue의 특성을 이용할 수가 있습니다.

대표적으로 LinkedList가 있습니다. 

 

Queue 인터페이스에 정의된 여섯가지 메서드이고, 한번 LinkedList를 이용해서 사용법을 살펴보겠습니다.  

 

1) offer()

offer()를 사용하면 데이터를 추가할 수 있습니다. add() 메서드로도 추가가 가능한데, add()의 경우는 boolean을 반환하고(배열이 가득 차면 더 이상 추가가 불가능 하므로 false를 반환합니다. 추가가 되면 true 반환.) offer()는 추가된 데이터를 반환합니다.

 

 
Queue<String> queue = new LinkedList<>();
 
queue.offer("1st");
queue.offer("2nd");
queue.offer("3rd");
queue.offer("4th");
queue.offer("5th");
 
System.out.println(queue);
//Prints [1st, 2nd, 3rd, 4th, 5th]
 

 

순서대로 잘 데이터가 추가된 것을 확인할 수 있습니다.

 

2) poll()

poll()을 사용하면 가장 앞에 있는 데이터를 삭제할 수 있습니다. 항상 맨 앞의 데이터를 삭제하므로 따로 파라미터가 필요없습니다. poll()은 삭제되는 데이터를 return 합니다.

 

 
queue.poll();
 
System.out.println(queue);
//Prints [2nd, 3rd, 4th, 5th]
 

 

가장 앞에 있는 데이터를 맨 뒤로 옮기고 싶다면 offer와 poll을 같이 이용하면 되겠죠?

 

 
queue.offer(queue.poll());
 
System.out.println(queue);
//Prints [2nd, 3rd, 4th, 5th, 1st]
 

 

3) peek()

 

Stack에서와 마찬가지로 peek() 은 열람용입니다. 데이터를 지우지 않고도 가장 앞에 있는 데이터를 return할 수 있습니다. pop()과 마찬가지로 파라미터를 따로 넣어주지 않습니다. 

 

 
System.out.println(queue.peek());
//Prints 2nd
 

 

여기까지 Stack과 Queue의 개념과 기본적인 사용법에 대해 알아봤습니다.

관련된 코테를 몇 가지 풀어보니 stack 과 queue의 개념이 사용되지만 반드시 Stack class를 이용한다거나 queue interface를 이용하는 것은 아니더라구요. 어떤식으로 자료들이 움직일 수 있는지 파악하고 적절한 데이터 구조를 사용하면 되는 것 같습니다. ☺️

다음번에는 트리와 그래프에 대해서도 한 번 다루어 보겠습니다. ☺️