스택, 큐 개념과 코드

스택

스택은 말 그래도 쌓아올린다는 것이다. 무엇을? 데이터를 순서대로 메모리에 올리고 꺼낸다는 것이다. 

 

특징 

- 같은 구조와 크기의 자료를 정해진 방향으로만 쌓고 꺼낼 수 있다. 

- 메모리에 삽입하는 연산을 Push라고 한다.

- 메모리에 삭제하는 연산을 Pop이라고 한다. 

- 마지막에 삽입된 자료가 가장 먼저 삭제된다. (후입선출)

- 비어있는 스택에서 원소 추출하려고 하면 Underflow, 메모리가 꽉 찾을 때 더 넣으려고 하면 Overflow라고 한다.

 

예) 방문 기록, 실행 취소, 후위 표기법 계산 

 

큐

큐의 개념은 도로로 생각하면 한 방향 일반통행이라고 생각하면 된다. 우리가 원한다고 유턴할 수 있는 것이 아니고 한 번 들어오면 반대쪽으로 나갈 수 밖에 없는 구조를 가진다. 즉 선입선출 스택의 구조이다.

 

특징 

- 큐의 가장 첫 원소를 Front/ 끝 원소를 Rear라고 한다.

- 큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성이다.

- 접근방법은 가장 첫 원소와 끝 원소로만 가능하다.

- 선입선출

 

예) 우선순위 작업 예약, 프로세스 관리, 너비우선 탐색, 캐시 

 

예시 문제 프로그래머스 스택/ 큐 

 

1번. 주식가격 

# stack_queue_1.py
import numpy as np
from collections import deque
prices = [1, 2, 3, 2, 3]


def solution(prices):
    stack_len = len(prices) - 1
    answer = [0] * len(prices)
    for i in range(len(prices) - 1):
        x = prices.pop(0)
        a = np.where(np.array(prices) < x)
        if not len(a[0]):
            answer[i] = stack_len
        else:
            answer[i] = a[0][0] + 1
        stack_len -= 1
    return answer


def solution_1(prices):
    answer = [0] * len(prices)
    for i in range(len(prices) - 1):
        x = prices.pop(0)
        for price in prices:
            if x > price:
                answer[i] += 1
                break
            else:
                answer[i] += 1
    # print(answer)
    return answer


def solution_3(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()

        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1

        answer.append(count)

    return answer


# print(solution(prices))
print(solution_1(prices))

 

2번. 기능개발

# stack_queue_2.py
progresses = [93, 30, 55]   # 진도가 적힌 정수 배열 (먼저 배포되어야하는 순서대로)
# progresses = [99, 1, 99, 1]
speeds = [1, 30, 5]     # 개발 속도가 적힌 정수
# speeds = [1, 1, 1, 1]


def solution_1(progresses, speeds):
    answer = []
    maximum = 0
    num = 0
    for progress, speed in zip(progresses, speeds):
        ent = (100 - progress) / speed
        if (100 - progress) % speed != 0:
            ent = ent + 1
        ent = int(ent)
        # print(ent)
        if num == 0:
            maximum = ent
            num = 1

        else:
            if maximum < ent:
                maximum = ent
                answer.append(num)
                num = 1
            else:
                num += 1
    answer.append(num)
    return answer


def solution_2(progresses, speeds):
    Q =[]
    for p, s in zip(progresses, speeds):
        if len(Q) == 0 or Q[-1][0] < -((p-100) // s):
            Q.append([-((p-100)//s), 1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]


# print(solution_1(progresses, speeds))
print(solution_2(progresses, speeds))

 

3번. 다리를 지나는 트럭

# stack_queue_3.py 다리를 지나는 트럭
from collections import deque
bridge_length = 100       # 100
weight = 100             # 100
truck_weights = [10,10,10,10,10,10,10,10,10,10]        # [10] [10,10,10,10,10,10,10,10,10,10]
# 8 101	110
movement = 1


def solution_1(b_l, w, t_ws):
    answer = 0
    total_len = len(t_ws)
    w_t = []        # 다리를 건너는 트럭
    w_t_w = 0       # 무게
    last_t = []      # 다리를 지난 트럭
    while 1:
        answer += 1

        if w_t:
            for i in range(len(w_t)):
                # print(w_t[i])
                w_t[i][1] -= 1
            # print(w_t)
            if w_t[0][1] == 0:
                w_t_w -= w_t[0][0]
                # print(w_t_w)
                last_t.append(w_t.pop(0))
        if len(last_t) == total_len:
            break
        if t_ws and t_ws[0] > w:
            break
        if t_ws and w_t_w + t_ws[0] <= w:
            temp = t_ws.pop(0)
            # print(temp)
            w_t.append([temp, b_l])
            w_t_w += temp

    return answer


def solution_2(b_l, wt, t_ws):
    time = deque([1])
    wsum = deque([t_ws[0]])
    sec = 0
    for v, i in enumerate(t_ws[1:]):
        if i <= weight - sum(wsum):
            time.append(1)
            wsum.append(i)
            if sum(time) - time[0] == t_ws:
                sec += time.popleft()
                wsum.popleft()
            continue
        if i <= weight - sum(wsum) + wsum[0]:
            sec += time.popleft()
            wsum.popleft()
            time.append(b_l - sum(time))
            wsum.append(i)
            continue
        while i > weight - sum(wsum):
            sec += time.popleft()
            wsum.popleft()
        time.append(b_l - sum(time))
        wsum.append(i)
    for i in time:
        sec += i
    return sec + b_l


# print(solution_1(bridge_length, weight, truck_weights))
print(solution_2(bridge_length, weight, truck_weights))

 

4번. 프린터

# stack_queue_4.py 프린터
priorities = [1, 1, 9, 1, 1, 1]   # [1, 1, 9, 1, 1, 1]	0
location = 0
# 1 5
# 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
# 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
# 3. 그렇지 않으면 J를 인쇄합니다.


def solution(priorities, location):
    queue = [(i, p) for i, p in enumerate(priorities)]
    answer = 0

    while 1:
        left_value = queue.pop(0)
        if any(left_value[1] < q_v[1] for q_v in queue):
            queue.append(left_value)
        else:
            answer += 1
            if left_value[0] == location:
                return answer


print(solution(priorities, location))