스택, 큐

스택 (Stack)

특징

 - 데이터를 한 곳에서만 넣고 뺄 수 있다.

 - 선형구조

 - Last In First Out(LIFO). 후입선출

 - 대표적으로 되돌리기(ctrl + Z). 순서대로 기억하고 저장 해놔야함.

 - 데이터의 삽입/삭제가 잦은 자료구조

출처 : 컴퓨터인터넷IT용어사전

구현

Linked List

 - 링크드리스트를 이용하여 헤드 노드를 구성하여 None으로 두고 데이터를 넣고빼고 함.

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


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

 

push

 - push(data) : 맨 앞에 데이터 넣기

    def push(self, value):
        new_head = Node(value)      # 새로운 노드를 생성
        new_head.next = self.head   # 현재의 헤드를 새로운 노드의 뒤에 연결
        self.head = new_head        # 새로운 노드를 헤드로 설정
        
        
stack.push(3)

 - push를 하면 헤드로 새로운 데이터가 입력된다.

 

pop

 - pop() : 맨 앞의 데이터 뽑기

    def pop(self):
        if self.is_empty():         # 데이터가 비어있을 때
            return "Stack is Empty"
        delete_head = self.head     # 헤드의 데이터를 꺼내 담는다.
        self.head = self.head.next  # 헤드 다음의 노드를 새로운 헤드롤 설정
        return delete_head          # 꺼낸 헤드의 데이터를 반환

 

peek

 - peek() : 맨 앞의 데이터 보기

    def peek(self):
        if self.is_empty():         # 데이터가 비어있을 때
            return "Stack is empty"
        return self.head.data       # 헤드의 데이터를 출력

 

isEmpty

 - isEmpty() : 스택이 비었는지 안 비었는지 여부 반환

    def is_empty(self):
        return self.head is None   # 헤드가 None인지 아닌지 여부

---

큐 (Queue)

특징

 - 데이터를 한 곳으로 넣고 다른 한 곳에서 뺄 수 있다.

 - 선형구조

 - First In First Out(FIFO). 선입선출

 - tail에 데이터를 생성하고, head로 데이터를 뽑는다.

 - 순서대로 처리되어야 할 때 사용.

출처 : 컴퓨터인터넷IT용어사전

구현

Linked List

 - 링크드리스트로 구현. 헤드와 테일의 노드를 가지고 시작.

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


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

 - tail 노드가 있음.

 

enqueue

 - enqueue(data) : 맨 뒤에 데이터 추가

    def enqueue(self, value):
        new_node = Node(value)      # 새로운 노드를 생성
        if self.is_empty():         # 데이터가 비어있을 경우
            self.head = new_node    # 새로운 노드를 헤드이자
            self.tail = new_node    # 테일로 설정한다.
            return

        self.tail.next = new_node   # 테일의 다음에 새로운 노드를 붙인다.
        self.tail = new_node        # 새로운 노드를 새로운 테일로 설정

 

dequeue

 - dequeue() : 맨 앞의 데이터 뽑기

    def dequeue(self):
        if self.is_empty():         # 데이터가 비어있을 때
            return "Queue is Empty"
        delete_head = self.head     # 헤드의 데이터를 꺼내 담는다.
        self.head = self.head.next  # 헤드의 다음 노드를 새로운 헤드로 설정
        return delete_head.data     # 꺼낸 헤드의 데이터를 출력

 

peek

 - peek() : 맨 앞의 데이터 보기

    def peek(self):
        if self.is_empty():         # 데이터가 비어있을 때
            return "Queue is Empty"
        return self.head.data       # 헤드의 데이터를 출력

 

isEmpty

 - isEmpty() : 큐가 비었는지 안 비었는지 여부 반환

    def is_empty(self):
        return self.head is None    # 헤드가 None인지 아닌지 여부

---