(자료구조-1)Deque와 Queue_python- 백준10845

짜바(가짜 자바)로 자료구조 알고리즘을 배운 나한테 파이썬 자료구조는 그럭저럭 할만 한듯 하다.

 

큐 정리좀 하려고 한다.

파이썬에 미리 구현되어 있는 클래스가 있긴한데 나는 만들어서 쓰는거 선호.

https://docs.python.org/ko/3/library/collections.html#collections.deque

collections — Container datatypes

만들어서 하면 시간복잡도는 있는거 쓰는 큐랑 똑같은데 공간복잡도는 처리가 안되더라...(이것도 되는 코드 추천받음)

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

10845번: 큐

여기서 원하는 메소드를 기준으로 제작되었음

 

일단 코드부터 공개하자면

class Queue:
  def __init__(self):
    self.q = []
    self.cnt = 0

  def push_x(self, k):
    self.q.append(k)

  def pop(self):
    length = len(self.q) - self.cnt
    if length == 0:
      return -1
   else:
      p_num = self.q[self.cnt]
      self.cnt += 1
      return p_num

  def size(self):
    length = len(self.q)-self.cnt
    return length

  def empty(self):
    length = len(self.q) - self.cnt
    if length == 0:
      return 1
    else:
      return 0

  def front(self):
    length = len(self.q) - self.cnt
    if length != 0:
      return self.q[self.cnt]
    else:
      return -1

  def back(self):
    length = len(self.q) - self.cnt
    if length != 0:
      return self.q[-1]
    else:
      return -1

장점은 아무래도 내가 짰으니까 나는 사용하기 한참 편하다는 것

단점은 코드가 얼마나 좋은지 나도 잘 모른다는 것...

 

이제 코드는 대충 이정도 소개하고  큐에 대해 알아보자

 

Queue

일반적으로 FIFO(First in First Out) 선입선출 많이 얘기한다.

중요한 건 맞다. 먼저 들어간 원소가 먼저 나온다는게 이 자료구조의 포인트고 솔찍히 이거 아니면 얘기할 것도 별로 없다.

 

그래도 몇가지 생각해 볼게 몇개 있는데 특히 파이썬 list에서는 1번으로 들어온 원소를 삭제시키려면 시간이 오래걸리기 때문에 이를 보완해준다는 점에서 의의를 갖는다.

[0]에 있는 원소를 아무리 잘 삭제시킨다고 해도 O(n)을 피할 수 없기 때문에 어떻게든 큐를 사용할 이유는 충분하다.

나는 이걸 O(1)로 유지시키려고 cnt 만들어서 원소 삭제될 때마다 한칸씩 옮겨주는걸 아이디어라고 냈는데

다 이렇게 하더라 ㅋㅋㅋ

 

딱히 뭘 글 쓸것도 별로 없고 연산에 따른 시간복잡도 얘기만 마저 하고 끗

자료구조/연산(시간 복잡도)	append(push)	pop(remove)
Python-list	O(n)	O(1)
Python-deque	O(1)	O(1)
Queue	O(1)	O(1)

 

 

2023.8.15 광복절 끝나기 1분전이다.

순국선열들에게 감사의 마음을 남긴다.