[Data Structure] 스택(stack), 큐(Queue)

[Data Structure] 스택(stack), 큐(Queue) 

 

이전에는 stack과 queue에 대해 해당 자료구조의 기본적인 개념을 알고 문제풀이에 사용했다면 이번에는 해당 자료구조의 구현을 통해 해당 자료구조에 대해 좀 더 알아보았다. 파이썬에서는 리스트 자료구조를 통해 스택과 큐를 둘 다 쉽게 구현 가능했었지만 그것에 의존하지 않고 해당 자료구조를 알아보는 시간을 가질 수 있었다. 

 

큐와 스택을 구현하는 방법에는 배열과 연결리스트가 존재한다. 이때 구현에 관해 각자의 사용 장단점부터 살펴보았다.

• 배열 
  • 배열의 인덱스를 사용하여 편리하게 사용한다는 장점
    
    • 원하는 데이터가 어디있는지 위치를 파악할 수 있는것
  • 크기가 정해져있기에 고정배열 사용 시 주기적으로 크기를 살펴봐야한다
• 연결 리스트
  • 노드 / 연결리스트의 방식으로 구현
  • 스택의 크기에 제한이 없다 → 연결리스트의 장점
  • 원소 삽입 및 삭제에 강점을 보임

 

스택(stack)

 

문제풀이에 자주 사용이 되는 스택이다. 스택의 특징들을 한번 살펴보자

 

•  

• 후입선출(Last in First Out)의 구조
  • 가장 늦게 들어온 작업을 먼저 처리하는 상황에서는 유용하다.
    • 다만 해당 작업을 진행하던 중 아래에 있는 데이터를 가져오려면 위에 있는 데이터를 처리해야한다 
    • 프링글스 구조: 나중에 들어온 감자칩부터 입으로 들어온다
    • 빨래 바구니 
    • 인터넷 브라우저의 뒤로가기 메서드 
      • 페이지가 넘어가면서 기존의 페이지는 쌓여진 페이지 가장 위에 존재 

stack..

스택의 주요 메서드

 

• push : data를 입력받아서 스택 안에 데이터를 넣어주는 메서드
• pop : 가장 위에 존재하는 데이터를 뽑아내는 메서드
• peek : 가장 위에 존재하는 데이터를 보여주는 메서드

연결리스트로 구현이 된 스택

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


class Stack:
    def __init__(self):
        self.head = None

    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head

    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return "Stack is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    def peek(self):
        if self.is_empty():
            return "Stack is Empty"
        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None

 

stack = Stack()
print(stack.is_empty())
stack.push(5)
print(stack.peek())
stack.push(3)
stack.push(52)
print(stack.peek())
stack.push(51)
print(stack.pop())

파이썬에서 스택 사용

stack = []
stack.append(5)
stack.pop()

 

스택의 사용 알고리즘

• DFS ( 깊이 우선 탐색 )
  • 해당 알고리즘은 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

 

큐(Queue)

 

스택과 마찬가지로 문제풀이에 자주 사용이 되는 큐 자료구조이다. 큐의 특징들을 한번 살펴보자

 

• 선입선출(First in First Out)의 구조
  • 가장 먼저 들어온 데이터를 먼저 처리하므로 공정한 자료구조이다
  • 대기줄 
• 한쪽에서는 데이터의 삽입이 이루어지고 다른 한쪽은 데이터의 추출만 이루어짐

 

queue..

큐 메서드

 

• enqueue : 맨 뒤에 데이터 추가하기 메서드
• dequeue : 맨 앞의 데이터 뽑기 메서드
• peek : 맨 앞의 데이터 보기 메서드

 

연결리스트로 구현이 된 스택

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


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    # 맨 뒤에 데이터 추가하기
    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():  # 만약 비어있다면,

            self.head = new_node  # head 에 new_node를
            self.tail = new_node  # tail 에 new_node를 넣어준다.
            return

        self.tail.next = new_node
        self.tail = new_node

    # 맨앞 데이터 뽑기
    def dequeue(self):
        if self.is_empty():
            return "Queue is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    # 맨 앞의 데이터 보기
    def peek(self):
        if self.is_empty():
            return "Queue is Empty"
        return self.head.data

    # 큐가 empty 여부 확인
    def is_empty(self):
        return self.head is None

queue = Queue()
queue.is_empty()
queue.enqueue(3)
print(queue.peek())
queue.dequeue()
queue.enqueue(34)
print(queue.peek())
queue.enqueue(35)
print(queue.peek())

파이썬에서 큐 사용

queue = []
queue.append(5)
queue.popleft()

 

큐 사용 알고리즘

 

• BFS ( 너비 우선 탐색 )
  • 해당 알고리즘은 그래프에서 가까운 노드부터 탐색을 하는 알고리즘