[자료구조] 스택(Stack), 큐(Queue), 덱(Deque)

🌵스택(Stack) 구조란?

 

스택(Stack)은 ‘쌓다’라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.
즉, 데이터가 들어온 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 나오게되는 구조이다. 
LIFO (Last In First Out)

 

 

🌵특징 및 장단점

스택(Stack)은 정해진 방향으로만 쌓을 수 있으며,

새로 삽입된 자료는 stack.push를 사용해 스택의 top에 쌓일 수 있다. 

삭제 연산은 stack.pop을 통해 이루어지며, top위치의 자료가 삭제된다.

 

top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1)

 

 

장점

• top 을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.

 

단점

• top 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능하다. 탐색하기 위해선 모든 데이터를 꺼내면서 진행해야 한다.

 

 

 

🌵 파이썬에서의 스택(Stack) 사용

파이썬에서는 스택(Stack) 자료구조는 따로 제공하지 않는다.

대신 기본 클래스인 list를 통해 스택을 만들어 낼 수 있다.

 

Operation	구현	비고
push item	list.append(item)	O(1)
pop item	list.pop()	O(1)
top	top = list[-1]	가장 위에 있는 자료 반환
empty	if not list	스택이 비어있는지의 여부 반환

 

 

 

🌵 스택(Stack) 활용

• 재귀 알고리즘
• DFS 알고리즘
• 작업 실행 취소와 같은 역추적 작업이 필요할 때
• 괄호 검사, 후위 연산법, 문자열 역순 출력 등

 

 

---

 

🌵큐(Queue) 구조란?

 

큐(Queue)는 한쪽에서만 데이터의 삽입/삭제가 이루어졌던 스택과는 달리 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다. 
먼저 들어온 것이 먼저 나가는 ‘선입선출’, FIFO(First In First Out) 구조이다.
데이터가 삽입되는 곳을 rear, 데이터가 제거되는 곳을 front라 한다.

 

 

🌵선형 큐 (Linear Queue)

• 선형 배열을 사용하여 구현된 큐
• 삽입을 위해서는 계속해서 요소들을 이동시켜야 한다.
• front, rear은 증가만 하는 방식
• front 앞쪽에 공간이 있더라도 삽입할 수 없는 경우 발생 가능

 

 

🌵원형 큐 (Circular Queue)

 

• front : 맨 첫번 째 요소 바로 앞
• rear : 마지막 요소
• empty 상태 : front == rear
• full 상태 : front == (rear + 1) % MAX_QUEUE_SIZE
• 공백 상태와 포화 상태를 구분하기 위해 하나의 공간을 비워둔다.

 

 

 

🌵큐 (Queue)의 활용

• 데이터를 입력된 순서대로 처리해야 할 때
• BFS 알고리즘
• 프로세스 관리
• 대기 순서 관리

 

 

 

🌵 파이썬에서의 큐(Queue) 사용

1) 리스트(list)로 구현

Operation	사용법	비고
push item	list.append(item)	O(1)
pop item	list.pop(0)	가장 앞에 있는 원소 삭제

 

하지만 이렇게 list를 큐 자료 구조의 효과를 내기 위해서 사용하는 것은 성능 측면에서 추천되지 않습니다. 파이썬의 list는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료 구조이기 때문에 pop(0) 또는 insert(0, x)는 성능적으로 매우 불리한 연산이다.

 

 

2) collections 모듈의 deque로 구현

Operation	사용법	비고
append	deque.append(item)	맨 마지막에 요소 추가
appendleft	deque.appendleft(item)	맨 앞에 요소 추가
pop	deque.pop()	맨 뒤 요소 삭제
popleft	deque.popleft()	맨 앞 요소 삭제
clear	deque.clear()	모든 요소 삭제
insert	deque.insert(i, item)	i번째 인덱스에 요소 추가

 

 

3) Queue 모듈로 구현

Operation	사용법	비고
put	queue.put(item)	요소 추가
empty	queue.empty()	큐가 비어있는지의 여부 반환
full	queue.full()	큐가 차있는지의 여부 반환

 

import queue

q = queue.Queue()
q.put('a')

 

 

---

 

🌵덱(Deque) 구조란?

 

 

deque는 Double - Ended Queue의 줄임말이다.
한쪽에서만 삽입, 다른 한쪽에서만 삭제가 가능했던 큐와 달리 양쪽 front, rear에서 삽입/삭제가 모두 가능한 큐를 의미

1) 데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
2) 데이터의 크기가 가변적일 경우

 

 

🌵특징

•  데이터의 삽입 삭제가 빠르고 앞, 뒤에서 삽입 삭제가 모두 가능
• 가변적 크기
• index 를 통해 임의의 원소에 바로 접근이 가능하고 새로운 원소 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입
• 중간에서의 삽입 삭제가 어렵고, 스택, 큐에 비해 구현이 어렵다.

 

---

 

🌵 관련 문제 (스택)

 

🥈[백준 알고리즘 10828번 : 스택]

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

10828번: 스택

 

 

[SOLUTION]

n = int(input())
li = []

for i in range(n):
    order = input().split()
    if 'push' in order :
        li.append(order[1])
    elif order[0] == 'top':
        if len(li) != 0 :
            print(li[len(li)-1])
        else:
            print(-1)
    elif order[0] == 'size':
        print(len(li))
    elif order[0] == 'empty':
        if len(li) == 0:
            print(1)
        else:
            print(0)
    else :
        if len(li) == 0:
            print(-1)
        else:
            print(li.pop())

 

 

🥈[백준 알고리즘 10773번 : 제로]

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

10773번: 제로

[SOLUTION]

https://gyurisinzorba.tistory.com/81

[Python] 백준 알고리즘 10773번 : 제로

 

🥈[백준 알고리즘 1874번 : 스택 수열]

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

1874번: 스택 수열

[SOLUTION]

https://gyurisinzorba.tistory.com/67?category=1019803 

[Python] 백준 알고리즘 1874번 : 스택 수열

 

🥈[백준 알고리즘 4889번 : 안정적인 문자열]

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

4889번: 안정적인 문자열

[SOLUTION]

https://gyurisinzorba.tistory.com/68?category=1019803 

[Python] 백준 알고리즘 4889번 : 안정적인 문자열

 

---

 

🌵 관련 문제 (큐, 덱) 

🥈[백준 알고리즘 18258번 : 큐2]

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

18258번: 큐 2

[SOLUTION]

import sys
from collections import deque

N = int(sys.stdin.readline())
queue = deque()
for i in range(N):
    command = sys.stdin.readline().split()

    if command[0] == "push":
        queue.append(command[1])

    elif command[0] == "pop":
        if not queue:
            print(-1)
        else:
            print(queue.popleft())
    
    elif command[0] == "size":
        print(len(queue))

    elif(command[0] == "empty"):
        if not queue:
            print(1)
        else:
            print(0)
    
    elif(command[0] == "front"):
        if not queue:
            print(-1)
        else:
            print(queue[0])
    
    else:
        if not queue:
            print(-1)
        else:
            print(queue[-1])

 

🥈[백준 알고리즘 2164번 : 카드 2]

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

2164번: 카드2

[SOLUTION]

https://gyurisinzorba.tistory.com/82?category=1019803

 

 

🥈[백준 알고리즘 2164번 : 프린터 큐]

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

1966번: 프린터 큐

[SOLUTION]

https://gyurisinzorba.tistory.com/84

[Python] 백준 알고리즘 1966번 : 프린터 큐

 

🥈[백준 알고리즘 10866번 : 덱]

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

10866번: 덱

[SOLUTION]

https://gyurisinzorba.tistory.com/83

[Python] 백준 알고리즘 10866번 : 덱

 

🥈[백준 알고리즘 1021번 : 회전하는 큐]

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

1021번: 회전하는 큐

[SOLUTION]

 

 

 

~ 해당 포스팅은 업데이트 중 ~