스택 , 큐, 우선순위 큐 주제

스택

한쪽 끝에서만 데이터를 넣고 꺼내는 자료구조

LIFO(Last In First Out), 후입선출

#include<stdio.h>
#define MAX_STACK_SIZE 1000
 
int stack[MAX_STACK_SIZE];
int top=-1;
 
int IsEmpty(){
    if(top<0)
        return true;
    else
        return false;
    }
int IsFull(){
    if(top>=MAX_STACK_SIZE-1)
        return true;
    else
        return false;
}
 
void push(int value){
    if(IsFull()==true)
        printf("스택이 가득 찼습니다.");
    else
        stack[++top]=value; 
}
 
int pop(){
    if(IsEmpty()==true)
        printf("스택이 비었습니다.");
    else 
        return stack[top--];
}
 
int main(){
    
    push(3);
    push(5);
    push(12);
    printf("%d ",pop());
    printf("%d ",pop());
    printf("%d ",pop());
 
    return 0;
}

top의 위치를 저장해두고, top을 증가시키면서 그 자리에 push,

pop은 반대로 top의 위치 리턴하고, top - 해줌

큐

한쪽에서 데이터 넣고 반대쪽에서 꺼냄

FIFO(First In First Out), 선입선출

1697번: 숨바꼭질

#include <stdio.h>
#include <queue>
int arr[100000];
using namespace std;

typedef struct Node{
	int pos;
	int time;
}Node;

Node pp(int a,int b){
	Node q;
	q.pos=a;
	q.time=b;
	return q;
}
int main(){
	int ans;
	int start,end;
	scanf("%d %d",&start,&end);
	queue<Node> q;
	q.push(pp(start,0));
	int ttmp=0;
	while(1){
		arr[q.front().pos]=1;
		if(q.front().pos==end){
			ans=q.front().time;
			break;
		}
		int p = q.front().pos;
		int t=q.front().time;
		if(arr[p-1]==0){
			q.push(pp(p-1,t+1));
		}
		if(arr[p+1]==0){
			q.push(pp(p+1,t+1));	
		}

		if(p*2<=100000&&arr[p*2]==0){
			q.push(pp(p*2,t+1));
		}
	
			
		q.pop();
	}
	printf("%d",ans);
}