🐷전동준(Jeon DongJun)

Go with the flow

[알고리즘 기초]스택과 큐

[해당 포스트는 유튜버 나동빈님의 영상을 참고했습니다.]

가장 기본이 되는 자료구조: 스택과 큐

1. 스택

(1) 스택 자료구조란

  1. 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조

  2. 입구와 출구가 동일한 형태로 스택을 시각화

    image-20220103105925528

  3. DFS 등 다양한 알고리즘에서 사용한다.

  4. 비슷한 예 : 프링글스 통이라고 생각하면된다.

(2) 스택 동작 예시

  • 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

  • 오른쪽에서 순서대로 삽입하되, 삭제하면 가장 마지막에 들어온 값이 나가는 선입후출

  • 그래서 삭제행위의 바로 이전의 삽입된 값 7과 4가 삭제되는 것이다.

    image-20220103105954432

(3) 구현(Python)

  • 파이썬은 별도로 다른 라이브러리를 이용할 필요없이 기본적으로 제공되는 객체인 리스트로 스택 자료구조를 표현 가능하다.
  • .append() 메소드는 리스트의 마지막 부분에 원소를 추가, pop은 리스트의 가장 마지막 원소를 제거(선입후출)
stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력

[1, 3, 2, 5]
[5, 2, 3, 1]

2. 큐

(1) 큐 자료구조란

  1. 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조

  2. 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화

    image-20220103110015679

  3. 비슷한 예 : 은행창구에서 번호표를 뽑고 대기하는 사람들을 생각해보자.

  4. 영어권에서는 보통 큐를 차례대로라는 의미로 사용한다고 함

(2) 큐 동작 예시

  • 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

  • 오른쪽에서 왼쪽 방향으로 삽입. 가장 먼저 들어온 값이 먼저 삭제되는 선입선출

  • 그래서 가장 먼저 들어온 5, 2가 삭제된다.

    image-20220103110047775

(3) 구현(Python)

  • 리스트 자료형을 이용해 큐를 구현할 수 있지만, 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있다.
    • 리스트 자료형을 활용해 특정 인덱스 값을 호출하기 위해 .pop() 메소드를 사용할 경우, 원소를 꺼낸 후 원소의 위치를 조정하는 과정에서 시간을 많이 소비하게 된다.
  • 그래서 deque 라이브러리를 사용하는게 훨씬 효율적
  • .append() 메소드는 리스트의 마지막 부분에 원소를 추가, popleft() 메소드는 리스트의 가장 첫 원소를 제거(선입선출)
from collections import deque

# 큐 (Queue) 구현을 위해 deque 라이브러리를 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 정렬
print(queue) # 나중에 들어온 순서대로 출력

deque([3, 7, 1, 4])
deque([4, 1, 7, 3])

2022

[web]jQuery 복습 3

2 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

16 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

6 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

6 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

6 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

9 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

2 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑