Queue

공부한 내용을 스스로 보기 쉽게 정리한 글입니다.

Queue의 특징

1. 내가 버스정류장에 서있다고 생각해보면, 버스 전용차선으로 버스가 줄지어 들어온다. 아무리 뒷차가 손님을 다 태웠다고해서, 앞에 버스가 아직 손님을 태우고 있으면 뒷 버스는 출발 하지 못한다.
   
   이것이 바로 QUEUE
2. FIFO : First In First Out == 선입선출 or 후입후출
3. front와 rear 라는 index가 각각 구조의 맨 앞과 뒤를 가리키고 있다. Data는 rear로 들어가고, front 에서 나온다.

ADT

1. empty() 라는 메소드로 Queue 에 data가 있는지 없는지 확인하게 한다. empty 이면 True, not empty 이면, False 를 return 한다.
   
   Queue.empty() returns Boolean

2. enaueue(data) 메소드로 Queue의 rear 가 가리키고 있는 data 뒤에 data를 넣는다.
   
   Queue.enqueue (data) returns None

3. dequeue() 메소드로 Queue의 front가 가리키고 있는 data를 반환하면서 삭제 된다.
   
   Queue.dequeue() returns data

4. peek() 메소드로 Queue의 front가 가리키고 있는 data를 반환한다. peek은 어디까지나 확인하는 메소드 이므로, data가 삭제되지 않는다.
   
   Queue.peek() returns data

구현 1 : by python list

• Queue 구조를 Python에 내장 되어 있는 list를 container 로 구현한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Queue:
  def __init__(self):
    self.container=list()

  def empty(self):
    # ADT 를 따라서, 비어 있으면 return True 비어있지 않으면 return False
    if not self.container:
      return True
    return False

  def enqueue(self, data):
    # list 를 활용했으므로, list.append(data)를 활용할 수 있다.
    self.container.append(data)

  def dequeue(self):
    # pop 역시 list.pop()을 활용할 수 있다.
    return self.container.pop(0)

  def peek(self):
    # peek은 단지 front 에 어떤 데이터가 있는지 확인 하는 것 뿐이므로, 현재 리스트의 가장 앞 부분에 있는 data 를 확인하면 된다.
    return self.container[0]

구현 2 :

Stack

공부한 내용을 스스로 보기 쉽게 정리한 글입니다.

Stack 의 특징

1. 접시를 쌓듯이 데이터를 쌓아 올리는 모양의 데이터 구조
2. LIFO : Last In First Out == 후입선출 or 선입후출
3. top index 가 항상 Stack의 가장 윗부분을 가리키고 있어, 우리는 top 위치만 볼 수 있다.
4. 단점 : stack 의 top 이 외에 밑에 쌓여져있는 데이터의 Search 가 안된다.

ADT

1. empty() 라는 메소드로 Stack 에 data가 있는지 없는지 확인하게 한다. empty 이면 True, not empty 이면, False 를 return 한다.
   

Stack.empty() returns Boolean
2. Stack의 top 위치에 데이터를 쌓는다.

Stack.push(data) returns None

3. Stack의 top 위치에 있는 데이터를 삭제하면서 반환한다.
   

Stack.pop() returns data
4. Stack의 top 위치에 있는 데이터를 반환하지만, 삭제하지 않는다. 어떤 데이터가 있는지 just 확인.

Stack.peek() returns data

구현 1 : by python list

• Stack 구조를 Python에 내장 되어 있는 list를 container 로 삼아 구현하게 되면, 그 구현은 매우매우 쉽다.
• Python의 List 자료형의 대단함을 그만큼 느낀다.
• 이 때 List 의 index가 큰 쪽이 top 방향이다.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  class Stack: def __init__(self): self.container=list() def empty(self): # ADT 를 따라서, 비어 있으면 return True 비어있지 않으면 return False if not self.container: return True return False def push(self, data): # list 를 활용했으므로, list.append(data)를 활용할 수 있다. self.container.append(data) def pop(self): # pop 역시 list.pop()을 활용할 수 있다. return self.container.pop() def peek(self): # peek은 단지 top 에 어떤 데이터가 있는지 확인 하는 것 뿐이므로, 현재 리스트의 가장 마지막에 append 되어 있는 data를 확인하면 된다. return self.container[-1]

구현 2 :