[알고리즘] 스택(Stack), 큐(Queue)

 

TITLE

알고리즘이란?

알고리즘(라틴어, 독일어: Algorithmus, 영어: algorithm 알고리듬[*], IPA: [ǽlɡərìðm])은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다.(출처: 위키피디아)

위의 정의에서도 볼 수 있듯이, 알고리즘이란 어떤 계산을 실행하기 위한 단계적 절차를 의미하고, 모든 계산에는 계산이 되어야 할 원소(element)가 존재합니다. 매우 간단하고도 당연한 말입니다.

정의적으로 얘기하기는 어렵지만, 그림 한장을 통해 아주 쉽게 이해할 수 있습니다.

매우 당연한 얘기?

매우 당연한 얘기입니다. 어떤 맛집의 비법 양념 만드는 법을 알고리즘이라고 한다면, 설탕, 간장, 고춧가루 등이 원소가 될 것이고, 퍼즐을 통해 액자를 만드는 것을 알고리즘이라고 하면, 퍼즐 조각 하나 하나가 원소가 될 것입니다.

이렇듯 모든 문제에는 원소가 존재하는데, 이 원소들을 다루는 가장 기본적인 자료구조가 바로 큐와 스택입니다.

(자료구조란 자료(원소)들을 다루는 구조라고 생각하면 되겠습니다.)

---

큐와 스택은 둘 다 막대 형식의 자료구조라고 생각하면 쉽습니다. 물론 실제 형태는 사용자의 마음에 따라 바뀌겠지만, 쉽게 개념적으로는 막대 형식이 이해하기 편합니다. 둘 다 들어오는 입력들을 순서대로 저장하는 형태를 가지고 있습니다.

입력으로 들어온 원소(a, b, c) 를 차례대로 쌓아줍니다.

둘의 차이점은 명확합니다. 안의 원소를 꺼내주는 순서가 다르다는 것입니다. 쉽게 말해서, 입력을 쌓는 방식은 똑같은데, 출력이 나가는 방식이 반대인 것입니다.

큐(Queue): FIFO(First-In-First-Out) 형식의 자료구조.
스택(Stack): LIFO(Last-In-Last-Out) 형식의 자료구조. 

 

큐는 들어오는 순서대로 나가고(FIFO), 스택은 들어온 순서의 반대 순서대로 나가는 것(LIFO). 간단하게 그림으로 표현하면 다음과 같습니다.

큐의 출력 예시

큐는 FIFO니, a -> b -> c 순서대로 들어간 입력을 그대로 c -> b -> a 순서대로 출력해주게 됩니다. 좀 더 쉬운 예시를 들면,  줄을 서있는 사람들을 생각해보면 됩니다.  사람들이 은행업무를 보기 위해 줄을 서서 기다리고 있습니다. 당연히 먼저 기다린 사람이 먼저 업무를 봐야하지 않을까요? 이것이 바로 큐입니다.

 

 

스택의 출력 예시

스택은 LIFO니, a -> b -> c 순서대로 들어간 입력을 역순으로 a -> b -> c 순서대로 출력해주게 됩니다. 마찬가지로 간단한 예시를 들면, 창고에 물건을 쌓는다고 생각해보면, 창고에 물건을 쌓을 때는 절대 바깥쪽부터 쌓지 않습니다. 안쪽부터 빈 공간이 없도록 차곡차곡 쌓은 뒤에, 뺄 때는 바깥쪽부터 순서대로 빼는 것이 정답일 것입니다. 채울 때는 안쪽부터 차곡차곡, 뺄 때는 바깥쪽부터 순서대로. 이것을 스택이라고 합니다.

 

큐와 스택 모두 굉장히 간단한 자료구조지만, 모든 프로그래밍에 있어 기본이고 헷갈릴 수 있으니 외워두면 좋을 것 같습니다.

---

큐와 스택 모두 Java기준 기본적으로 라이브러리가 제공이 됩니다.

 

1. 큐

큐는 LinkedList를 이용하여 구현되어있기 때문에 Queue와 Linked List 모두 import 해주어야 사용 가능합니다. 

큐에 원소를 삽입하는 함수로는 offer()와 add()가 있고, peek()을 통해 다음에 빼낼 원소를 조회할 수 있으며, poll()과 remove()를 통해 원소를 빼낼 수 있습니다.

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

System.out.println("<<< Queue >>>");
Queue<Integer> queue = new LinkedList<>(); // 큐 객체 생성

queue.offer(10); // offer: 큐에 10 삽입
queue.offer(5); // offer: 큐에 5 삽입
System.out.println("Queue : " + queue);
// Queue : [10, 5]

queue.add(25); // add: 큐에 25 삽입
queue.add(99); // add: 큐에 99 삽입
System.out.println("Queue : " + queue);
// Queue : [10, 5, 25, 99]

int peek = queue.peek(); // peek: 다음에 빼낼(맨 앞) 원소 '조회'
System.out.println("peek : " + peek);
// peek : 10

System.out.println("Queue : " + queue);
// Queue : [10, 5, 25, 99]

int poll = queue.poll(); // poll: 맨 앞의 원소 '빼냄'
System.out.println("poll : "+poll);
// poll : 10

System.out.println("Queue : " + queue);
// Queue : [5, 25, 99]

int remove = queue.remove(); // remove: 맨 앞의 원소 '빼냄'
System.out.println("remove : "+remove);
// remove : 5

System.out.println("Queue : " + queue);
// Queue : [25, 99]

 

 

2. 스택

스택은 단순히 Stack만 import 해주어도 사용이 가능합니다. 

큐에 원소를 삽입하는 함수로는 push()가 있고, peek()을 통해 다음에 빼낼 원소를 조회할 수 있으며, pop()을 통해 원소를 빼낼 수 있습니다.

import java.util.Stack;

 System.out.println("<<< Stack >>>");

Stack<Integer> stack = new Stack<>(); // 스택 객체 생성

stack.push(1); // push: 스택에 1 삽입
stack.push(9); // push: 스택에 9 삽입
stack.push(13); // push: 스택에 13 삽입
System.out.println("Stack : " + stack);
// Stack : [1, 9, 13]

int peek = stack.peek(); // peek: 다음에 빼낼(맨 뒤) 원소 '조회'
System.out.println("peek : "+ peek);
// peek : 13

System.out.println("Stack : " + stack);
// Stack : [1, 9, 13]

int pop = stack.pop(); // pop: 맨 뒤의 원소 '빼냄'
System.out.println("pop : " + pop);
// pop : 13

System.out.println("Stack : " + stack);
// Stack : [1, 9]

pop = stack.pop(); // pop: 맨 뒤의 원소 '빼냄'
System.out.println("pop : " + pop);
// pop : 9

System.out.println("Stack : " + stack);
// Stack : [1]

 

 

 

<참고>

velog.io/@lshjh4848/Java-%EC%8A%A4%ED%83%9DStack-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC

coding-factory.tistory.com/602

www.tcpschool.com/java/java_collectionFramework_stackQueue