[자료구조] 스택과 큐

안수진·2023년 6월 1일

Algorithm

목록 보기

4/22

스택

스택은 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조

📖 스택 용어

top: 삽입과 삭제가 일어나는 위치
push: top 위치에 새로운 데이터를 삽입하는 연산
pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산

DFS(깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아야 한다.
후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.

큐

큐는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조
삽입과 삭제가 양방향으로 이루어진다.

📖 큐 용어

rear: 큐에서 가장 끝 데이터를 가리키는 영역
front: 큐에서 가장 앞의 데이터를 가리키는 영역
add: rear 부분에 새로운 데이터를 삽입하는 연산
poll: front 부분에 있는 데이터를 삭제하고 확인하는 연산
peek: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

BFS(너비 우선 탐색)에서 자주 사용

우선순위 큐

우선순위 큐(priority queue)는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
우선순위 큐는 일반적으로 힙(heap)을 이용해서 구현한다.

🔎 백준 1874번: 스택 수열

임의의 수열을 스택에 넣었다가 출력하는 방식으로 오름차순 수열을 출력할 수 있는지 확인하고, 출력할 수 있다면 push와 pop연산을 어떤 순서로 수행해야 하는지를 알아내는 프로그램을 작성해보자

- 문제 분석하기

현재 수열 값 >= 자연수
현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push한다. 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.
현재 수열 값 < 자연수
현재 수열 값보다 자연수가 크다면 pop으로 스택에 있는 값을 꺼낸다. 꺼낸 값이 현재 수열 값이거나 아닐 수 있다. 만약 아니라면 후입선출 원리에 따라 수열을 표현할 수 없으므로 NO를 출력한 후 문제를 종료하고, 현재 수열 값이라면 그대로 조건문을 빠져나온다.

슈도 코드

N(수열 개수) A[](수열 배열)
수열 배열 채우기

for(N만큼 반복){
	if(현재 수열 값 >= 오름차순 자연수){
    	while(값이 같아질 때까지){
        	push()
            (+) 저장
        }
        pop()
        (-) 저장
    }
    else(현재 수열 값 < 오름차순 자연수){
    	pop()
        if(스택 pop 결과값 > 수열의 수) NO 출력
        else (-) 저장
    }
}
if(-값을 출력한 적이 없으면) 저장한 값 출력

제출 코드

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A[] = new int[N];
		for(int i = 0; i< N; i++){
			A[i] = sc.nextInt();
		}

		Stack<Integer> stack = new Stack<>();
		int num = 1;
		boolean result = true;
		StringBuffer bf = new StringBuffer();
		for(int i = 0; i < A.length; i++){
			int su = A[i];
			if(su >= num){
				while(su >= num){
					stack.push(num++);
					bf.append("+\n");
				}
				stack.pop();
				bf.append("-\n");
			}
			else{
				int n = stack.pop();
				if(n > su){
					System.out.println("NO");
					result = false;
					break;
				}
				else{
					bf.append("-\n");
				}
			}
		}
		if(result) System.out.println(bf.toString());
	}
}

🔎 백준 2164번: 카드2

- 문제 분석

- 슈도 코드

N(카드의 개수) myQueue(카드 저장 자료구조)
for(카드의 개수만큼 반복){
	큐에 카드 저장하기
}
while(카드가 1장 남을 때까지){
	맨 위의 카드를 버림: poll()
    맨 위의 카드를 가장 아래의 카드 밑으로 이동: poll() -> add()
}
마지막으로 남은 카드 출력

- 제출 코드

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

public class Baekjoon2164_카드 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Queue<Integer> myQueue = new LinkedList<>();
		int N = sc.nextInt();
		for(int i = 1; i <= N; i++) {
			myQueue.add(i);
		}
	
		while(myQueue.size() > 1) {
			myQueue.poll();
			myQueue.add(myQueue.poll());
		}
		
		System.out.println(myQueue.poll());
	}
}

🔎 백준 11286번: 절댓값 힙

- 문제 분석

N의 최대 범위가 100,000으로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있다. 데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제를 쉽게 해결할 수 있다.
단, 이 문제는 절댓값 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야한다. 예제의 절댓값이 같을 때는 음수를 우선하여 출력해야 하는 사실을 기억하며 문제에 접근하자.

x = 0 일때
큐가 비어 있을 때는 0을 출력하고 비어있지 않을 때는 절댓값이 최소인 값을 출력한다. 단, 절댓값이 같다면 음수를 우선하여 출력한다.
X = 1 일때
add로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬한다.

- 슈도 코드

N(질의 요청 개수)
우선순위 큐 선언
- 절댓값 기준으로 정렬되도록 설저앟기
- 단, 절댓값이 같으면 음수 우선 정렬하기
for(N만큼 반복){
	요청이 0일 때: 큐가 비어 있으면 0, 비어 있지 않으면 큐의 front값 출력하기(poll())
    요청이 1일 때: 새로운 데이터를 우선순위 큐에 더하기(add())
}