Stack? Queue? 드루와....

Stack? Queue?

너네 누구냐..?

프로그래머스에서 알고리즘 문제를 풀던 도중 stack, queue라는 개념을 알게 되었다.
이번에 알게 된 stack과 queue를 정리하고 공유하기 위해 블로깅한다 ㅎㅎ

Stack이란?

입력과 출력이 한 곳(방향)으로 제한된 것을 말한다.
여기서 LIFO라는 개념이 등장한다.

LIFO란?

last in first out으로 이름 그대로 가장 나중에 들어온 것이 가장 먼저 나가는 것으로 주로 함수의 콜스택, 문자열 역순 출력, 연산자 후위 표기법등에서 사용된다.

크게 5가지의 명령어가 존재한다. (파이썬은 리스트로 스택을 흉내낸다.)

• 데이터 넣음 : push()
  파이썬에는 push()가 존재하지 않아, append()를 사용한다. 마지막 원소를 추가한다.
  
• 데이터 최상위 값 뺌 : pop()
  파이썬에는 pop()이 존재한다. 마지막 원소를 삭제한다.
  
• 비어있는 지 확인 : isEmpty()
  조건문으로 len()함수를 통해 확인 가능
  
• 꽉차있는 지 확인 : isFull()
  조건문으로 len()함수를 통해 확인 가능
  
• sp : 데이터가 새로 추가되고, 빠질때 위치를 확인하기 위한 것

Queue이란?

입력과 출력을 한 쪽 끝으로(front, rear)으로 제한된 것을 말한다.
큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부른다. 큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가지고, 접근방법은 가장 첫 원소와 끝 원소로만 가능하다.
여기서 FIFO라는 개념이 등장한다.

FIFO란?

first in first out으로 이름 그대로 가장 먼저 들어온 것이 가장 먼저 나가는 개념으로, 버퍼 또는 많은 양의 데이터가 입력된 것을 처리하지 못하는 상황에 주로 사용된다.

LIFO와 마찬가지로 크게 4가지의 명령어가 존재한다. (마찬가지로 리스트로 큐를 흉내낸다.)

• 데이터 넣음 : enQueue()
  파이썬에서는 append()(마지막원소로 삽입) 또는 insert(0, x)(첫번째 원소로 삽입)를 사용한다.

• 데이터 뺌 : deQueue()
  파이썬에서는 pop(0)으로 첫번째 원소를 삭제한다.

• 비어있는 지 확인 : isEmpty()
  조건문으로 len()함수를 통해 확인 가능

• 꽉차있는 지 확인 : isFull()
  조건문으로 len()함수를 통해 확인 가능

• sp : 데이터가 새로 추가되고, 빠질때 위치를 확인하기 위한 것

collections의 모듈 중 deque 자료구조가 있으니, queue를 작성 할때 사용하면 좋을 듯 싶다.
( popleft() 등등 여러 메소드 제공)

푼 문제 깃허브 링크

프로그래머스-기능개발.py : https://github.com/Samdaso-o/python_pratice/blob/main/Programmers/%EC%8A%A4%ED%83%9D-%ED%81%90/%EA%B8%B0%EB%8A%A5%EA%B0%9C%EB%B0%9C.py

사진 출처 : 위키백과