스택(stack) / 큐(queue)

스택

• 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조.
• Last in First out(LIFO) 구조

출처 : 나무위키

 

단순한 스택 형식 만들기는 append, list 형식으로 만들 수 있음

 

이 스택 형식을 잘 써먹는 함수로는 다음과 같은 함수가 있다.

• push(data) : 맨 앞에 데이터 넣기
• pop() : 맨 앞의 데이터 뽑기
• peek() : 맨 앞의 데이터 보기
• empty() : 스택이 비어있는지의 여부를 반환하는 연산
• top() : 스택의 가장 위에 있는 자료를 반환하는 연산

그럼 스택을 왜 쓸까? 스택과 위 함수와의 연관은 뭘까?

알고리즘 경험이 많진 않지만, 리스트 등의 데이터 형태에 들어온 것을

위 함수를 통해 꺼내어서 점검하는 형식으로 많이 이용한다.

 

콜스택

그리고 컴퓨터 프로그램에서 현재 실행중인 함수를 저장하는 역할을 한다.
실행 중인 함수는 호출되어 그 실행이 아직 완료되지는 않았지만, 완료후에는 호출된 지점으로 제어를 넘겨야 한다

 

예를 들어 빨래통에 빨랫감을 넣는데,

흰 옷 사이에 까만 옷을 넣으면 망하기 때문에 이게 흰 옷이 맞는지 확인해주는 절차라고 확인하면 된다.

 

---

큐

• 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조.
• First In First Out(FIFO)

출처 : 나무위키

 

큐 형식을 잘 써먹는 함수로는 다음과 같이 있다.

• enqueue(data) : 맨 뒤에 데이터 추가하기
• dequeue() : 맨 앞의 데이터 뽑기
• peek() : 맨 앞의 데이터 보기
• pop : 큐에서 자료를 빼는 연산
• push : 큐에 값을 넣는 연산
• empty() : 큐가 비었는지 안 비었는지 여부 반환해주기
• front : 큐의 가장 앞에 있는 자료를 반환하는 연산
• back : 큐의 가장 뒤에 있는 자료를 반환하는 연산
• put( ) : 큐에 데이터를 넣을 때 사용하는 메서드
• get( ) : 큐에서 데이터를 꺼내는 메서드
• 추가로 파이썬에서는 queue라는 내장 모듈을 제공한다.

큐의 포인터

• head : 큐의 첫 번째 원소를 가리키는 포인터
• rear : 큐의 마지막 원소를 가리키는 포인터

큐에 삽입/삭제

• push : rear 위치에 자료를 추가하고 rear를 1 증가시킴
• pop : head 위치의 자료를 제거하고 head를 1 증가시킴

 

추가로 deque 클래스가 파이썬에는 존재하는데,

double - ended queue라는 뜻으로 from collections import deque을 통해 가져올 수 있다.

deque는 데이터를 양방향으로 삽입/제거 등을 할 수 있기 때문에 효율면에서 좋다.

 

그럼 큐를 왜 쓸까? 큐와 위 함수와의 연관은 뭘까?

순서대로 처리되어야 하는 일에 필요하기 때문이다.

주문이 들어왔을 때 먼저 들어온 순서대로 처리해야 할 때, 혹은 먼저 해야 하는 일들을 저장하고 싶을 때 큐를 사용한다.

 

스택과는 점검 과정이 다소 다르다고 볼 수 있다.

 

스택은 박스 안에서 점검이 완료되면 스택 안에 그대로 두는 경우가 많지만,

큐는 박스 안에서 점검이 완료되면 배출하는 경우가 많다.

 

매표소(큐 박스)에서 표를 결제한 다음 관광지로 들어가는 것(배출)으로 생각하면 이해가 빠르다.

---

스택과 큐는 모두 '선형구조'이다.