[2023] 스택/큐

 

 

 

 

 

1. 스택(Stack)

LIFO(Last in first out) 후입선출

---

 

메소드

-[삭제 연산] pop : 맨 위의 원소 제거

-[삽입 연산] push : 맨 위에 원소 하나 추가

 

특징

-삽입과 제거가 맨 위(Top)에서만 일어남[삽입/삭제의 시간 복잡도 Θ(1)]

 

장점

-배열처럼 원소를 삭제하거나 이동했을 때 나머지 원소들이 움직일 필요가 없다.

-데이터를 추가/삭제하는 시간이 짧다.

-맨 위의 원소만 접근 가능

 

사용 사례

-재귀 알고리즘 : 데이터를 스택에 쌓아두고 재귀가 끝나고 빠져나올 때 순서대로 데이터를 꺼낸다.

-후위 표기법 계산

 

 

---

 

 

 

 

 

2. 큐(Queue)

FIFO(First in first out) 선입선출

---

 

메소드

-[삭제 연산] dnQueue(디큐): 맨 앞의 원소 제거

-[삽입 연산] enQueue(인큐): 맨 뒤에 원소 하나 추가

 

특징

-삽입 : 맨 뒤(Rear) / 삭제 : 맨 앞(Front)

-맨 앞과 맨 뒤의 원소만 접근 가능

 

장점

-데이터 접근, 삽입, 삭제가 빠르다.

 

사용 사례

-너비 우선 탐색(BFS) 알고리즘

-캐시 구현

---

문제

스택

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

9012번: 괄호

stack = list() # 빈 리스트로 스택
VPS = ""

for i in range(int(input())):
    stack = list() # 초기화
    VPS = "YES" # 올바른 괄호 문자열인가? 

    for l in input():
        
        if len(stack) == 0: # isEmpty
            if l == ")":
                VPS = "NO"
                break
            else:
                stack.append(l)
        else:
            if l == ")": # 만약 닫는 괄호라면 
                stack.pop(-1) # 마지막 여는 괄호 삭제
            else:
                stack.append(l) # 여는 괄호라면 추가

    if len(stack) != 0:
        VPS = "NO" # 남아있는 괄호가 있으면 잘못된 문자열

    print(VPS)

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

10773번: 제로

 

stack = list()
for i in range(int(input())):
    number = int(input())
    if number == 0:
        if len(stack) > 0:
            stack.pop(-1)
    else:
        stack.append(number)


stackSum = 0
for i in stack:
    stackSum += i

print(stackSum)

뭔가 타임아웃 될 것 같았는데 의외로? 안 됐다?

 

 

 

 

큐

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

10845번: 큐

import sys
input = sys.stdin.readline
print = sys.stdout.write

que = list()


for i in range(int(input())):
    ins = input().rstrip()

    if ins.startswith("push"):
        ins1, ins2 = ins.split()

        que.append(ins2)
        
    elif ins == "pop":
        if len(que) == 0:
            print("%d\n" % -1)
        else:
            print("%s\n" % que.pop(0))

    elif ins == "size":
        print("%s\n" % len(que))
        

    elif ins == "empty":
        if len(que) == 0:
            print("%d\n" % 1)
        else:
            print("%d\n" % 0)

    elif ins == "front":
        if len(que) == 0:
            print("%d\n" % -1)
        else:
            print("%s\n" % que[0])
        

    elif ins == "back":
        if len(que) == 0:
            print("%d\n" % -1)
        else:
            print("%s\n" % que[-1])

뭔가 한 번은 그냥 풀어보고 그 다음에 제대로 풀어야지~ 했는데 어째 이걸로도 풀려질 것 같아서(큐를 구현하려고 했었다 사실) 빠른 입출력을 적용해보았다... 그러니 이게되네 

 

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

2164번: 카드2

from collections import deque
que = deque(list(range(1, int(input())+1)))
while(1):
    if len(que) == 1:
        break
    else:
        que.popleft()
        que.append(que.popleft())



print(que[0])

collections 모듈을 사용해봤다.

 

---

참고자료

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

 

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

 

https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95

 

https://yoongrammer.tistory.com/45

 

https://cocoon1787.tistory.com/691