python 자료구조 TIL (Stack, Queue)

 

오늘 실시간 강의는 스택과 큐, 그리고 정렬알고리즘이었따.

 

 

이 포스팅은 아래의 링크드리스트를 기반으로 스택과 큐를 구현하는 TIL!

 

 

↓↓ 이전글 링크에 있는 링크드리스트가 반드시 필요하다

2022.11.25 - [자료구조] - 알고리즘용 LinkedList

 

 

 

Stack 스택

 

LIFO를 검색하면 제일 눈에 띄는 사진! 동국대 개발자 커뮤니티님들 멋져요

 

스택은 LIFO (Last In First Out), 후입선출 방식의 리스트다.

 

가장 마지막에 넣은걸 제일 먼저 빼는 방식. 그냥 쌓고 꺼내고 쌓고 꺼내고.

쌓을떈 push(), 꺼낼땐 pop()

 

LIFO를 비유 할 때 편의점 진열대에 물건을 넣고 빼는 것에 비유하는 경우가 있는데..

선입선출 안하면 혼나거든요!!!!!!!!

 

기본적으로 라이브러리에 이미 만들어진 스택과 큐가 존재하긴 하지만,

코테를 대비해서든, 와타시의 논리력을 위해서든 직접 구현할 줄 알아야 하기 때문에 복습 차원에서 다시 만들어봤따!

 

stack의 가장 기본적인 3가지 메소드,

peek, push, pop.

 

링크드리스트를 기준으로 만들 것인데, 아래 그림처럼 이 리스트를 세로로 세웠다고 가정하여

head를 최상단에 두고, head만 오지게 지지고 볶으며 구현하자 (tail은 쓰지 않는다)

그림판으로 그렸따

 

1) peek()

 

peek()는 스택의 최상단 지점을 반환하는 메소드다.

그것은 가장 최근에 삽입된 데이터이기도 하고,

다음에 가장 먼저 꺼내질 데이터

 

def peek(self):

    if self.head is None:
        return None
    
    return self.head.data

정말 간단하다. head만 반환하면 됨

 

 

 

2) push()

 

push() 는 스택의 최상단 지점에 노드를 추가하는 메소드다.

 

def push(self, data):

    if self.head is None:
        self.head = Node(data)

        return

    newNode = Node(data)
    newNode.next = self.head
    self.head = newNode

    return

push() 또한 매우 쉽다.

 

새 노드를 만들고, 새 노드의 next에 기존의 head를 지정하고,

새 노드가 head가 되게 만들어버리면 끝!

 

 

 

3) pop()

 

pop() 은 스택의 최상단지점의 노드를 꺼내는 메소드!

peek() 처럼 반환을 하면서, 꺼내진 노드는 삭제를 시켜줘야 한다.

 

def pop(self):

    if self.head is None:
        return None

    popNode = self.head
    self.head = self.head.next

    return popNode.data

 

pop() 도 정말 쉽다..

 

 

stack은 링크드리스트에 대한 개념만 잘 잡혀있으면 정말 쉽게 구현할 수 있다.

 

 

 

 

 

 

Queue 큐

선입 선출 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

큐는 FIFO (First In First Out), 선입선출 방식의 리스트다.

 

선입선출은 모르는 사람이 없을정도로 잘 알려진 용어라고 생각한다.

들어온 순서대로 나가는 일반적인 대기열이다.

먼저 들어간게 먼저 나오는 방식. 위 그림에 너무 잘 설명되어 있다.

 

큐에 넣는 것은 Enqueue, 꺼내는 것은 Dequeue 라고 한다

 

 

링크드리스트를 이용해서, 아래 그림처럼

Enqueue()는 tail에 삽입,

Dequeue()는 head에서 꺼내는 방식으로 구현할 것이다.

그림판 도움!

 

처음엔 왜 떵구멍에다 넣고 머리통에서 끄내지? 싶다.

나도 심적으로 안정감이 들게 head에 삽입하는 식으로 구현해봤는데.. 번거로워진다!

왜 번거로워지는지는 Dequeue()를 구현해보면 알게 된다!

 

1) enqueue()

 

    def enqueue(self, data):

        if self.head is None:
            self.tail = Node(data)
            self.head = self.tail
            return

        elif self.head.next is None:
            self.tail.next = Node(data)
            self.tail = self.tail.next
            self.head.next = self.tail
            return

        self.tail.next = Node(data)
        self.tail = self.tail.next
        return

 

stack에 비해 관리해야 하는 tail 노드가 하나 더 추가되었기에 코드가 조금 길어졌지만,

 

enqueue()도 정말 간단하다! 

 

None이던 self.tail.next 에 새 노드를 추가하고,

self.tail이 self.tail.next을 가리키도록 바꿔주기만 하면 된다

 

 

2) Dequeue()

 

def dequeue(self):

    if self.head is None:
        return None

    elif self.head.next is None:
        dequeueNode = self.head
        self.head = None
        self.tail = None
        return dequeueNode.data

    dequeueNode = self.head
    self.head = self.head.next
    return dequeueNode.data

 

dequeue()의 코드도 정말 간단하다!

 

임시로 head를 저장할 변수 dequeueNode를 만들고,

self.head가 self.head.next를 가리키도록 해서 기존의 self.head의 연결을 끊어버린다.

 

그리고 dequeueNode 반환!

 

 

 

그런데 만약

tail에 넣고 head에서 꺼내는 방식이 아니라,

head에 넣고 tail에서 꺼내는 방식이었다면?

 

dequeueNode = self.tail
self.tail = self.tail.prev # next필드가 아니라 prev 필드가 필요함!
return dequeueNode.data

next만을 이용하는 단방향 리스트가 아니라,

모든 노드를 prev로 한번 더 연결시켜 양방향 리스트가 되도록 구현해야 한다!

 

그럼 enqueue() 할떄 prev로 연결시켜주는 작업이 추가되어서 번거롭다!

또는 tail 직전 노드에 도달할 때 까지 리스트를 돌리는 반복문을 구현해야한다!

정 단방향리스트로 하고 싶으면 next연결이 아니라 저어어언부 prev로 연결시켜야 한다! (이건 진짜 변태같다)

 

 

그렇다! tail에 삽입하는 큐의 방식은 진행방향을 고려한 합리적인 선택이었던것!!!!!

 

 

오늘의 TIL 끗!!!!!!!!!