[Python & Data Structure] Queue, Stack, Linked List

✏️ Queue (큐의 개념)

• 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILI(Last In Last Out)을 특징으로 하는 자료구조다.데이터가 입력된 순서대로 처리되어야할 떄 주로 사용이 된다.
• 정해진 한 곳(top)을 통해서 insert, delete가 이루어지는 stack과 달리 Queue는 한쪽 끝(rear)에서 insert, 다른 쪽 끝(front)에서 delete작업이 이루어진다. rear에서 이뤄지는 삽입연산을 enQueue, front에서 이뤄지는 삭제연산을 dequeue라고 한다.
• 활용처: 프로세스관리, BFS 구현, Cache 구현

 

✏️ Queue (큐의 사용과 구현)

Python은 queue라이브러리를 제공한다. 하지만 list를 이용해 대부분 구현이 가능하기에 가장 간단한 방법은 범용 자료구조인 list를 사용하는 것이다. append()와 pop(0)을 활용하면 Queue의 enqueue와 dequeue를 사용하는 효과를 낼 수 있다. 

1. queue Library 활용

import queue

(1) Queue()

 

Code:

# Queue() : 일반적으로 사용되는 큐 자료구조이다.
q = queue.Queue()
q.put(10)
q.put(20)
q.put(30)
print(q.qsize())
print(q.get())
print(q.get())
print(q.qsize())

Output:

3
10
20
1

 

put() : enqueue

get(): dequeue

qsize: queue의 요소개수를 가져온다

 

(2) PriorityQueue()

: 데이터의 우선순위를 지정해 정렬시키고, 우선순위에 따라 출력하는 자료구조이다. 

Code:

# PriorityQueue() : 우선순위 큐

q = queue.PriorityQueue() 
q.put((10, "중요한거"))
q.put((0, "엄청중요한거"))
q.put((15, "안중요한거"))
print(q.get()[1])
print(q.get()[1])
print(q.get()[1])

Output:

엄청중요한거
중요한거
안중요한거

우선순위가 지정되지 않는다면 오름차순으로 정렬이되고, 위처럼 (우선순위, 값) 형태의 튜플을 넣어준다면 우선순위에 맞추어 정렬이 된다.

 

2. List 로 Queue() 구현

 

Code:

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

  def put(self, x):
    self.q.append(x)

  def get(self):
    return self.q.pop(0)

  def qsize(self):
    return len(self.q)

q = Queue()
q.put(10)
q.put(20)
q.put(50)
print(q.qsize())
print(q.get())
print(q.get())
print(q.qsize())

Output:

3
10
20
1

 

✏️ Stack (스택의 개념)

• 데이터를 순서대로 쌓는 자료구조이다.
• LIFO (Last In First Out) 또는 FILO (First In Last Out) 이라고 부른다.
• 입력과 출력이 한방향으로 이루어져 접근이 제한적이다.

 

✏️ Stack (스택의 사용과 구현)

push() : 데이터를 스택에 쌓는다.

pop() : 데이터를 스택에서 꺼낸다.

 

1. List 로 구현

class Stack:
  def __init__(self):
    self.stack = list()
  
  def push(self, x):
    self.stack.append(x)
  
  def pop(self):
    return self.stack.pop()

stack = Stack()
stack.push(10)
stack.push(30)
stack.push(50)
print(stack.pop())
print(stack.pop())

 

 

✏️ Linked List (연결리스트의 개념)

• Array List와 달리 엘리먼트와 엘리먼트 간의 연결(link)를 이용해서 리스트를 구현한 것.
• python의 경우 List 기본 자료형에 linked list 기능이 함께 포함되어 있다. 
• array list에서는 엘리먼트라는 이름을 사용하지만 linked list와 같이 연결된 엘리먼트들은 Node 혹은 Vertex라고 부른다.

Node: 데이터의 저장단위로 데이터 값 + 포인터로 구성되어 있다.

Pointer: 각 노드 안에서, 다음이나 이전의 노드의 주소를 가지는 값을 의미한다.

 

✏️ Linked List (연결리스트의 구현)

 

1. Node 구현

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

현재 노드에서 다음 노드를 어떻게 참조시킬까? 아래와 같이 할 수 있을 것.

head = Node(10)
next_node = Node(20)
head.next = next_node

 

2. 단순 연결 리스트의 구현

• 첫번째 노드 삽입
• 중간 노드 삽입
• 마지막 노드 삽입
• 노드삭제

SLL class 생성

class SLL:
  def __init__(self, data):
    new_node = Node(data)
    self.head = new_node
    self.list_size = 1

* 길이를 계산하는 것보다 O(n), 길이를 가지고 있는편 O(1) 이 더 빠르다.

아래 메서드들은 모두 SLL 클래스 내부에서 구현된다.

 

첫번째 노드 삽입

def insertFirst(self, data):
    new_node = Node(data)
    temp_node = self.head
    self.head = new_node
    self.head.next = temp_node
    self.list_size += 1

헤더를 교체한다.

 

노드 선택

다른 메서드의 작업 간단화를 위한 메서드. 인덱스 번호로 노드를 선택한다.

def selectNode(self, num):
      if self.list_size < num:
        return
      node = self.head
      count = 0
      while count < num:
        node = node.next
        count += 1
      return node

 

마지막 노드 삽입

def insertLast(self, data):
      node = self.head
      while True:
        if node.next == None:
          break
        node = node.next
      new_node = Node(data)
      node.next = new_node
      self.list_size += 1

 

중간 노드 삽입

def insertMiddle(self, num, data):
      if self.head.next == None:
        insertLast(data)
        return
      node = self.selectNode(num)
      new_node = Node(data)
      temp_next = node.next
      node.next = new_node
      new_node.next = temp_next
      self.list_size += 1

 

헤드노드 삭제

def deleteHead(self):
      node = self.head
      self.head = node.next
      del node

 

노드 삭제

def deleteNode(self, num):
      if self.list_size < 1:
        return
      elif self.list_size < num:
        return
      
      if num == 0:
        self.deleteHead()
        return

      node = self.selectNode(num-1)
      node.next = node.next.next
      del_node = node.next
      del del_node