Queue

큐

큐에 대한 간단한 설명

---

큐(Queue)는 FIFO방식의 선형 자료 구조이다.
FIFO(first in first out) 선입선출
큐의 맨 앞부분은 프론트 끝부분은 테일이라고 한다.
큐는 선입선출이라 테일에서 입력을 받고 프론트에서 출력한다.

큐의 정의

---

삽입과 삭제가 양 끝에서 일어나는 자료구조

자료 처리 방식

운영체제의 자료 스케줄링 등에 응용되는 것으로 가장 적합한 자료구조

큐의 장점

---

데이터가 입력된 순서대로 처리해야 할 필요가 있는 상황에 사용된다.

큐의 단점

---

크기가 제한적

큐의 앞부분이 비어도 데이터를 삽입할 수 없다.

(앞부분이 비어있어도 뒤로 입력해야 한다.)

전위 후위 중위 표기법

---

중위 표기법

1+2x9-2%7

중위 표기법은 우리가 일반적으로 쓰는 계산순서가 같다.

전위 표기법

1+2x9-2%7

전위 표기법은 연산자를 앞으로 빼는 표기법이다.

전위 표기법으로 바꾸는 방법

1. 우선순위를 괄호로 묶어준다.
   ((1+(2x9))-(2%7))
   
   
2. 가장 안쪽에 있는 괄호부터 앞으로 꺼내준다.
   ((1+x(29))-%(27))
   
   
3. 2의 과정을 반복
   -(+(1x(29))%(27))
   
   
4. 반복 과정이 끝나면 괄호를 없애준다.
   결과물 : -+1x29%27

후위 표기법

후위 표기법은 연산자를 뒤로 빼는것만 빼면 전위 표기법과 같다.

1+2x9-2%7

후위 표기법으로 바꾸는 방법

1. 우선순위를 괄호로 묶어준다.
   ((1+(2x9))-(2%7))
   
   
2. 가장 안쪽에 있는 괄호부터 뒤으로 꺼내준다.
   ((1+(29)x)-(27)%)
   
   
3. 2의 과정을 반복
   ((1(29)x)+(27)%)-
   
   
4. 반복 과정이 끝나면 괄호를 없애준다.
   결과물 : 129x+27%-

스택을 이용한 후위 표기법 출력

---

알고리즘

1. 문자열을 입력받아 하나씩 탐색한다.
2. 이과정중 피연산자가 나오면 바로 출력한다.
3. 연산자가 나오면 스택에 push한다.
4. )가 나오면 스택에서 연산자를 pop한다.

리스트큐의 객체 구조

---

__queue[]

큐원소들의 저장되는 리스트

enqueue()
// enqueue(50) 
// 큐의 맨 끝부분에 50추가

맨뒤에 원소를 삽입한다

dequeue() 

맨앞에 있는 원소를 알려주고 삭제한다

front()

맨앞에 있는 원소를 알려준다

dequeueAll() 

리스트로 큐 구현

---

class ListQueue :
    def __init__(self) :
        self.__queue = []

    def enqueue(self, x) :
        self.__queue.append(x)
    
    def dequeue(self) :
        return self.__queue.pop(0)

    def front(self) :
        if self.isEmpty():
            return None
        else:
            return self.__queue[0] 

    def isEmpty(self) -> bool :
        return (len(self.__queue) == 0)
    
    def dequeueAll(self) :
        self.__queue.clear()
    
    def printQueue(self) :
        print("Queue form front : ", end='')
        for i in range (len(self.__queue)) :
            print(self.__queue[i] ,", ", end="")
        print()


q = ListQueue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
q.printQueue()
print(q.dequeue())

실행결과

Queue form front : 1 , 2 , 3 , 4 , 5 , 
1