[자료구조] - 스택(Stack)과 큐(Queue) + 관련 문제

스택(Stack)이란?

- 데이터를 집어넣을 수 있는 선형(Linear) 자료형

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

- 데이터 집어넣는 push, 데이터 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등 가능

스택 동작 방식

# 파이썬에서는 list [] 로 이미 구현되어있음

# append()를 활용해 리스트 맨 뒤에 넣음
a_list = [1,2,3]
a_list.append(1)
=> [1,2,3,1]

# pop()를 활용해 맨 뒤의 요소 꺼내고 삭제
a_list = [1,2,3]
a_list.pop()
=> [1,2]

print(a_list.pop())

# 출력: 2
# a_list : [1]

 

# 관련 문제 : 프로그래머스 -> 코딩테스트 연습 -> 스택/큐 -> 올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=python3

프로그래머스

def solution(s):
    answer = True
    
    res = []
    
    for i in s:
        if i == '(':
            res.append(i)
            
        if i == ')':
            try:
                res.pop()
            except IndexError:
                return False
    
    return len(res) == 0

 

큐(Queue)란?

- 데이터를 집어넣을 수 있는 선형(Linear) 자료형 (스택과 동일)

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

- 데이터 집어넣는 enqueue, 데이터 추출하는 dequeue 작업 가능

큐 동작 방식

 

# 1.list로 구현하기

queue = list()

queue.append(0)
queue.append(1)
queue.append(2)

del queue[0]	// 요소 0 제거
queue.pop(0)	// 요소 1 제거

print(queue)	// 2 출력

# 2.queue 라이브러리 사용 [Queue(), LifoQueue(), PriorityQueue()]

# 2.1 Queue() 사용

import queue
queue = queue.Queue()

queue.put(0)
queue.put(1)
queue.put(2)

queue.get() 	//get() 함수를 수행할 경우, 가장 먼저 추가된 요소 '0' 제거
queue.qsize()	//남은 항목 2개로 2출력

# 2.2 LifoQueue() 사용

import queue
queue = queue.LifoQueue()

queue.put(0)
queue.put(1)
queue.put(2)

queue.get()	//Lifo는 후입선출 구조이기 때문에 '2' 제거
queue.qsize()	//남은 항목 2개로 2출력


# 2.3 PriorityQueue() 사용

import queue
queue = queue.PriorityQueue()

queue.put((5, 0))
queue.put((10, 1))
queue.put((7, 2))

queue.get()	//우선순위 10이 가장 높음으로 1 제거
queue.qsize()	//남은 항목 2개로 2출력

 

# 관련 문제 : 프로그래머스 -> 코딩테스트 연습 -> 스택/큐 -> 주식가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=python3

프로그래머스

from collections import deque

def solution(prices):
    
    queue = deque(prices)
    answer = []
    
    while queue:
        price = queue.popleft()
        sec = 0
        
        for q in queue:
            sec += 1
            if price > q:
                break;
                
        answer.append(sec)
        
    return answer

 

출처

- https://helloworldjavascript.net/pages/282-data-structures.html#%ED%81%90-queue (내용)

- https://gorokke.tistory.com/129 (스택 코드 참고)

- https://velog.io/@gnwjd309/python-queue (큐 코드 참고)

- https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90 (사진)