Stack & Queue - (1)

Stack

stack 은 후입선출 (Last in First Out) LIFO 형식으로 이루어진 자료구조.

stack.append(data) 를 하면 가장 뒤쪽에 들어오고 stack.pop() 을 하면 가장 뒤쪽이 삭제된다.
top pointer로 stack에서 가장 새롭게 들어온 부분을 가르키게 된다.

값1, 값2, 값3, 값4
에서 값5를 넣으면
값1, 값2, 값3, 값4, 값5
이렇게 된다.----->top은 값5

연산
top: 삽입, 삭제가 일어날 위치
append(data): 데이터 삽입
pop(): 데이터 삭제
s[-1]: top에 데이터가 있는지 없는지 확인하는 연산

DFS, Back tracking 등에 쓰임.

Queue

queue 은 선입선출 (First in First Out) FIFO 형식으로 이루어진 자료구조.

queue.append(data) 를 하면 rear 쪽에 데이터가 들어오고
queue.popleft() 를 하면 front 쪽의 데이터가 삭제된다.

연산
rear: 큐의 가장 끝 데이터가 가리키는 영역
front: 큐의 가장 앞 데이터가 가리키는 영역
append(data): rear 쪽 데이터 삽입
popleft(): front쪽 데이터 삭제
q[0]: front에 데이터가 있는지 없는지 확인하는 연산

BFS 등에 주로 쓰임.

Priority Queue

우선 순위 큐는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조.
heap을 이용하여 구현하는게 일반적이다.

해당 내용은 추후 heap을 다룰 때 자세히 공부하도록 하겠다.

스택으로 수열 만들기(백준 1874번, 시간 제한: 2초)

문제
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

입력 예시
8
4
3
6
8
7
5
2
1

출력 예시

코드 예시 (python)

from collections import deque
import sys
input=sys.stdin.readline
n=input()
A=[0]*n
for i in range(n):
    A[i]=int(input())
stack=[]
num=1
ans=""
result=True
for i in range(n):
    if A[i]>=num:
        while A[i]>=num:
            stack.append(num)
            num+=1
            ans+="+\n"
        stack.pop()
        ans+="-\n"
    else:
        if stack.pop()>A[i]:
            print("NO")
            result=False
            break;
        else:
            ans+="-\n"
if result:
    print(ans)

stack을 사용해야 한다.
A[i]가 num보다 크다면 stack에 num을 하나씩 넣는다.
A[i]<num 이 되면 해당 stack에 pop 한다.
만약 pop 한 결과가 A[i]이 아니면 NO 를 출력하면 된다.

else:
        if stack.pop()==A[i]:
            ans+="-\n"
        else:
            print("NO")
            result=False
            break;

즉, 이렇게 수정해도 된다.

코드 예시(c)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
    int n;
    int top=-1;
    int index=0;
    int result_index=0;
    int A[100001];
    int stack[100001];
    char result[200002];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    int num=1;
    while(1){
        if(top==-1||stack[top]<A[index]){
            top++;
            stack[top]=num++;
            result[result_index]='+';
            result_index++;
        }
        else if(stack[top]==A[index]){
            top--;
            result[result_index]='-';
            result_index++;
            index++;
        }
        else {
            printf("NO\n");
            return 0;
        }
        if(index==n)break;
    }
    for(int i=0;i<result_index;i++)
        printf("%c\n",result[i]);
    return 0;
}