Algorithm 공부 #04 - 자료구조(스택과 큐)

 

 

Algorithm 공부 #04 - 자료구조(스택과 큐)

 

 

 스택(Stack)

     ● 후입선출 구조로 삽입과 삭제가 한 쪽에서만 일어나는 자료구조

     ● 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에서 효과적

         https://pooreumjung.tistory.com/39

 

 큐(Queue)

     ● 선입선출 구조로 삽입과 삭제가 양방향에서 일어나는 자료구조

     ● 너비 우선 탐색(BFS) 종류의 코딩 테스트에서 효과적임

         https://pooreumjung.tistory.com/25

      ● 우선순위 큐(priority queue) : 값이 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

 

 

예제

    백준 1874번 스택 수열

    https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

※ 스택의 후입선출 구조를 이용하는 문제 ※

  ● 현재 수열 값 >= 자연수

      while(수열 값>=자연수){  

               stack.push(자연수);

               자연수++;

               result.push_back('+'); }

     

      stack.pop();

      result.push_back('-');

 

      → 만약 현재 수열 값이 4이고 자연수가 1이라면 1,2,3,4를 스택에 push해주고 마지막에 pop을 1회만 하여

           4를 꺼내고 조건문 종료

          

      

  ● 현재 수열 값 < 자연수

      stack.pop();

      if(pop한 값 >= 자연수){

          check = false;

          NO출력

          break;

               }

       else{

                result.push_back('-')   }

 

     

      → 만약 현재 수열 값이 3, 자연수가 5라면 스택에서 3을 꺼낸뒤 현재 수열 값과 스택에서 꺼낸 값이 같으므로

           연산을 계속해서 수행할 수 있음

 

 

#include<iostream>
#include<stack>
#include<vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n; // 배열의 크기
	cin >> n;

	vector<int>A(n, 0); // 입력 받을 배열
	vector<char>result; // 결과 출력 배열

	int num = 1;// push할 자연수
	stack<int>myArr; // 스택
	bool check = true; // NO의 판단법
	
	for (int i = 0; i < n; i++) {
		cin >> A[i]; // 배열 입력
	}

	for (int i = 0; i < A.size(); i++) {
		
		int su = A[i]; // 현재 배열의 값

		if (su >= num) { // 배열의 값이 num보다 크다면
			
			while (su >= num) {  
				myArr.push(num);
				num++;
				result.push_back('+');
			}
			
			myArr.pop();
			result.push_back('-');
		}
		
		else {
			
			int dx = myArr.top();
			myArr.pop();
			
			if (dx > su) {
				cout << "NO";
				check = false;
				break;
			}
			
			else {
				result.push_back('-');
			}
		}
	}

	if (check) {
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << '\n';
		}
	}
}

 

백준 17298번 오큰수

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

※ 스택을 이용해서 푸는 문제 ※

● 스택에 새로 들어오는 수가 top존재하는 수보다 크면 그 수는 오큰수가 된다

● 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다

● 스택이 채워져 있고 A[index] > A[top]라면 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장

● 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감

● 과정을 수열 길이만큼 반복한 다음 현재 다음 수열에 남아있는 인덱스에 -1을 저장

#include<iostream>
#include<stack>
#include<vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<int>A(N, 0); // 입력받을 배열
	vector<int>res(N, 0); // 결과를 출력할 배열
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	stack<int>myStack; // 스택 생성

	myStack.push(0); // 맨 처음 인덱스 0푸쉬

	for (int i = 1; i < N; i++) {
		while (!myStack.empty() && A[myStack.top()] < A[i]) { // 스택이 비지 않을 때까지 + A[top] < A[index]일 때까지
			res[myStack.top()] = A[i]; // 오큰수를 저장하고
			myStack.pop(); //인덱스를 빼버리기
		}
		myStack.push(i); // 다시 그다음 인덱스 push
	}

	while (!myStack.empty()) { // 스택이 비지 않을 때까지
		res[myStack.top()] = -1; // 수열 길이만큼 다 돌리고 나서 남아 있는 인덱스에 -1을 저장
		myStack.pop(); // pop pop
	}

	for (int i = 0; i < N; i++) {
		cout << res[i] << " ";
	}
}

 

 

백준 2164번 카드2

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

 

 

 

※ 큐를 이용해서 푸는 문제 ※

● queue의 사이즈가 1보다 클 때까지만 반복문 돌리기

● 반복문 안에서 queue.pop(); queue.push(queue.front()); queue.pop(); 반복해주기

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	queue<int>myQueue;
	for (int i = 1; i <= N; i++)
		myQueue.push(i);

	while (myQueue.size()>1) {
		
		myQueue.pop();
		int n = myQueue.front();
		myQueue.pop();
		myQueue.push(n);
	}

	cout << myQueue.front();
}

 

 

백준 11286번 절댓값 힙

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

※ 큐 중에서도 우선순위 큐를 이용해서 푸는 문제 ※ 

● 우선순위 큐를 생성하고 compare구조체를 만들어서 조건에 맞게 출력하도록 해야함

● x가 0인 경우

   if(큐가 비어있지 않다면)
   절댓값이 가장 작은 값을 => 같은 게 있다면 음수를 출력
   그리고 그 값을 제거

    if(큐가 비어있다면)

   0을 출력
● x가 0이 아닌 경우
    x를 삽입 => 우선순위 큐와 compare에 의해 자동으로 정렬

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct compare {
	bool operator()(int a1, int a2) {

		int first_abs = abs(a1);
		int second_abs = abs(a2);

		if (first_abs == second_abs) // 절댓값이 같다면 음수를 기준으로
			return a1 > a2;
		else // 그게 아니라면 그냥 절댓값을 기준으로
			return first_abs > second_abs;
	}
};

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	priority_queue<int, vector<int>, compare>myQueue;

	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;

		if (x == 0) {
			if (myQueue.empty()) {
				cout << '0' << '\n';
			}
			else {
				cout << myQueue.top() << '\n';
				myQueue.pop();
			}
		}

		else {
			myQueue.push(x);
		}

	}
}