TIL[70].stack&queue

jake.log·2020년 9월 9일
0

1. Stack

- 개념

Last in First Out (LIFO)
마지막으로 들어온 데이터가 가장 먼저 나간다.

스택은 우리가 어떠한 것을 차곡차곡 쌓았을 때 맨 위에 놓여진 것이 가장 첫번째로 사라지는 것을 말한다.
개발자의 입장에서 말하자면, 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조라고 할 수 있다.

스택은 배열 인덱스 접근이 제한되는 LIFO 구조다.

책상 위에 쌓여진 책, 부엌에 쌓여진 접시, 아이스크림이 콘 위에 쌓이는것, 인터넷 방문기록이 가장 최신 기록부터 쌓이는 것을 생각하면 쉽다.

- Stack의 동작

  • push : 스택 맨위 혹은 맨끝에 항목을 넣는다.
  • pop : 스택 맨 끝 항목을 반환하면서 제거한다.
  • top/peek : 스택 맨 끝 항목을 조회한다.
  • empty : 스택이 비어 있는지 확인한다.
  • size : 스택 크기를 확인한다.

- Stack 코드 구현

class Stack:
    def __init__(self):
        self.state = []

    def push(self, data):
		# 데이터를 스택에 push 하는 것을 구현 해 주세요
        self.state.append(data)
       
    def pop(self):
		# 데이터를 스택에서 pop 해서 그 값을 리턴하도록 구현 해 주세요
        return self.state.pop()
       
    def getPeak(self):
		# 스택의 최상위 값을 리턴하도록 구현 해 주세요
        return self.state[-1]

2. Queue

- 개념

First in First Out (FIFO)
처음으로 들어온 데이터가 가장 먼저 나간다.

큐는 우리가 마트에서 계산할 때 맨 앞에 줄을 선 사람이 계산을 하고 먼저 나가듯, 롤러코스터를 기다리는 사람들 중 가장 맨 앞 사람이 먼저 타듯..맨 앞에 있는 것이 가장 첫번째로 사라지는 것을 말한다.

개발자의 입장에서 말하자면, 먼저 들어온 데이터가 가장 먼저 나가는 선입 선출 구조라고할 수 있다.

책상 위에 쌓여진 책, 부엌에 쌓여진 접시, 아이스크림이 콘 위에 쌓이는것, 인터넷 방문기록이 가장 최신 기록부터 쌓이는 것을 생각하면 쉽다.

- Queue의 동작

  • enqueue: 큐 뒤쪽에 항목을 삽입한다.
  • dequeue: 큐 앞쪽에 항목을 반환하고, 제거한다.
  • peek/front: 큐 앞쪽의 항목을 조회한다.
  • empty: 큐가 비어 있는지 확인한다.
  • size: 큐의 크기를 확인한다.

- Queue 코드 구현

class Queue:
    def __init__(self):
		# 어떤 자료구조를 사용해 데이터를 담아야 할지 고민 해 주세요
        self.queue = []
       
    def enqueue(self, data):
		# 데이터를 큐에 enqueue 하는 것을 구현 해 주세요
        self.queue.append(data)
         
    def dequeue(self):
	    # 데이터를 큐에서 dequeue 해서 그 값을 리턴하도록 구현 해 주세요
         return self.queue.pop(0)
       
    def getFirst(self):
		# 큐의 가장 먼저 들어온 값을 리턴하도록 구현 해 주세요
        if self.queue:
            return self.queue[0]
profile
꾸준히!

0개의 댓글