[ 자료구조 ] 스택 큐 덱

 

 

1.  개념

 

스택, 큐, 덱은 데이터의 삽입과 삭제가 제한된 위치에서만 이루어지기 때문에

Restricted Data Structure(제한된 자료구조)라고 불린다

 

1 )  스택

 

 

스택은 선입후출( LIFO : Last In First Out ) 규칙을 갖고 있다.

스택 가장 위에 자리한( 가장 마지막에 저장한 ) 데이터의 위치를 top이라고 하며

스택 안에 데이터를 넣는 것을 push, 삭제하는 것을 pop 이라고 한다

push와 pop은 항상 top에서 이루어진다

 

top이 0보다 작아지는 순간 스택은 empty 상태라고 할 수 있고

top이 배열의 max size보다 커지는 순간 스택은 full 상태라고 할 수 있다

 

Python에서는 리스트를 이용해서 구현하면 된다

pop() : 데이터 삭제
append(data) : 데이터 삽입

 

 

 

  2 )  큐

 

 

큐는 선입선출( FIFO : First In First Out ) 규칙을 갖고 있다

큐에서 데이터를 삽입하는 곳을  rear 라 하고 삭제하는 곳을 front 라고 하며

데이터를 삽입, 삭제하는 것을 각각 enqueue, dequeue 라고 한다

 

front == rear 가 되는 순간 큐는 empty 상태라고 할 수 있고

rear == ( 배열의 마지막 index ) 가 되는 순간 큐는 full 상태라고 할 수 있다

 

파이썬에서는 queue 라이브러리를 사용한다

queue 라이브러리는 세 가지의 큐를 제공한다

-  Queue : 기본 큐 (앞서 서술한 큐)

get() : front에 있는 데이터 dequeue
put(data) : rear 에 데이터 enqueue

    

-  LifoQueue : LIFO의 규칙을 갖는 큐 (스택처럼 기능)

get() : rear 에 있는 데이터 dequeue
put(data) : rear 에 데이터 enqueue

 

 -  PriorityQueue : 우선순위 큐

우선순위 큐에 대해서는 뒤에서 자세히 서술하도록 하겠다       

 

원형 큐 ( Circular Queue )

 

원형 큐는 선형 큐의 문제점을 보완하기 위한 개념이다

 

선형 큐의 문제점은 dequeue를 할 때마다 front가 뒤로 움직이면서 배열에 빈 공간이 생기고

이 때문에 배열에 빈 공간이 있음에도 rear == 배열의 마지막 index 이기만 하면

큐를 full 상태로 인식하게 된다는 것이다

이를 방지하기 위해서는 dequeue를 할 때마다 데이터를 계속 한 칸씩 앞으로 옮겨줘야 하는데

이는 매우 비효율적인 방법이다

 

 

원형 큐는 배열의 시작과 끝을 이어서 배열의 마지막 인덱스 다음에 데이터를 삽입해야 할 때

배열의 첫 인덱스부터 다시 데이터를 삽입할 수 있도록 한다

 

원형 큐의 enqueue와 dequeue는 아래와 같이 이루어진다

enqueue할 때 rear = (rear + 1) % (배열의 크기)

dequeue할 때 front = (front + 1) % (배열의 크기)

 

원형 큐에서 empty와 full을 판단하는 방법은 아래와 같다

(rear + 1) % (배열의 크기) == front 가 되는 순간 원형 큐는 full 상태라 할 수 있고

front == rear 가 되는 순간 원형 큐는 empty 상태라고 할 수 있다

 

원형 큐를 구현할 때 주의해야 할 점은 front를 항상 비워놔야 한다는 것이다

그래야 full과 empty를 구분할 수 있다

 

하지만 위에서 말한 선형 큐의 문제점은 정적 배열을 사용할 때 나타나므로

동적 배열을 사용하는 Python에서는 원형 큐를 굳이 이용하지 않아도 된다

 

 

우선순위 큐 ( Priority Queue )

 

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

 

우선순위 큐를 구현할 때는 queue 라이브러리와 heapq 라이브러리 둘 중 하나를 선택하면 된다

-  queue 라이브러리를 이용한 우선순위 큐 구현

put((a, b)) : a - 우선순위를 나타내는 지표 / b - 데이터 값
* 보통 튜플 형식으로 enqueue한다

get() : 우선순위가 높은 데이터 dequeue

 

-  힙을 이용한 우선순위 큐 구현

힙의 작동 과정은 아래 그림과 같다

       

       

           

           힙을 이용한 데이터 삽입과 삭제의 과정은 아래와 같다

                           * 최소 힙

            

위의 과정을 아래의 함수를 통해 구현할 수 있다

heapq.heappush(큐 이름, 데이터 값) : 데이터 enqueue
heapq.heappop(큐 이름) : 우선 순위에 따라 데이터 dequeue

           

 

 

  3.  덱

 

 

 

덱은 front 와 rear 에서 데이터 삽입과 삭제가 모두 가능하다.

 

파이썬에서는 deque 라이브러리를 사용한다

파이썬 list의 시간 복잡도 : O(n)

파이썬 deque 라이브러리의 시간 복잡도 : O(1)

따라서 deque 라이브러리를 사용하는 것이 시간 복잡도 측면에서 훨씬 유리하다

append() : rear 에 데이터 삽입
appendleft() : front 에 데이터 삽입

pop() : rear 에 있는 데이터 삭제
popleft() : front 에 있는 데이터 삭제

 

    

   

 

2.  문제 풀이

 

# 1  스택으로 수열 만들기 - 백준 1874번

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

1874번: 스택 수열

 

 

import sys 
input = sys.stdin.readline 

N = int(input())
A = [0]*N 

for i in range(N):
    A[i] = int(input())
    
stack = []
num = 1
result = True 
answer=""

for i in range(N):
    # su : 만들어내야 하는 수 / num : stack의 top
    su = A[i]
    # su >= num 이면 su < num이 될 때까지 stack에 num 삽입, num 1 증가, + 삽입 
    if su >= num:
        while su >= num:
            stack.append(num)
            num += 1
            answer += "+\n"
        stack.pop()
        answer += "-\n"
    # su < num 이면 stack에서 pop, pop한 수가 su보다 크면 NO, su보다 작으면 - 삽입
    else:
        n = stack.pop()
        if n > su:
            print("NO")
            result = False 
            break 
        else:
            answer += "-\n"
            
if result:
    print(answer)

 

 

 

# 2  오큰수 구하기 - 백준 17298번

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

17298번: 오큰수

 

 

 

 

 

 

 

# 3  카드 게임 - 백준 2164번 

 

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

2164번: 카드2

 

 

 

from collections import deque 

n = int(input())
card = deque()

for i in range(n):
    card.appendleft(i+1)
    
while len(card) > 1:
    card.pop()
    card.appendleft(card.pop())


print(card[0])

 

큐 문제

deque 라이브러리로 풀었다!

 

 

 

# 4  절댓값 힙 구현하기 - 백준 11286번

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

11286번: 절댓값 힙