스택
스택은 데이터를 임시 저장할때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출방식이다.
(나중에 들어간게 먼저 나온다는 의미이다.)
푸시(push) : 스택에 데이터를 넣는 작업
팝(pop) : 스택에 데이터를 꺼내는 작업
스택배열 : stk
푸시한 데이터를 저장하는 스택 본체인 list형 배열
스택크기 : capacity
스택의 최대 크기를 나타내는 int형 정수
len(stk)와 일치
스택 포인터 : ptr
스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택포인터 라고 한다.
가장 마지막에 푸시한 원소의 인덱스에 1을 더한 값
예외처리
예외 처리의 기본 구조
try: -------원래 처리하는과정
except: -------오류가 생성됐을때 처리하는 과정
else: -----------오류가 발생되지 않았을때 처리하는 과정
finally: -----------오류에 상관없이 무조건 진행되는 과정
collections.deque로 스택 구현하기
from collections import deque
deque ======> 덱(데크) 라고 읽는다.
append(x) 함수
deque의 맨 끝(오른쪽)에 x를 추가한다.
appendleft(x) 함수
deque의 맨 앞(왼쪽)에 x를 추가한다.
clear( )함수
deque의 모든 원소를 삭제하고 크기를 0으로 한다.
copy( ) 함수
deque의 얕은 복사를 한다.
count(x)함수
deque 안에 있는 x와 같은 원소의 개수를 계산한다.
index(x[,start[,stop]]) 함수
deque 안에 있는 (인덱스 start부터 인덱스 stop까지 양 끝을 포함한 범위) x 가운데 가장 앞쪽에 있는 원소의 위치를 반환한다. x가 없는 경우는 Value Error를 내보낸다.
pop( ) 함수
deque의 맨 끝(오른쪽)에 있는 원소를 1개 삭제하고 그 원소를 반환한다. 원소가 하나도 없는 경우에는 IndexError를 내보낸다.
popleft( ) 함수
deque의 맨 앞(왼쪽)에 있는 원소를 1개 삭제하고 그 원소를 반환한다. 원소가 하나도 없는 경우에는 IndexError를 내보낸다.
remove(value) 함수
value의 첫 번째 항목을 삭제합니다. 원소가 없는 경우에는 ValueError를 내보냅니다.
큐(queue)
큐(queue)는 스택과 같이 데이터를 임시 저장하는 자료구조이며 선입선출 구조이다.
(가장 먼저 넣은 데이터를 가장 먼저 꺼내다는 의미이다.)
인큐(enqueue) : 큐에 데이터를 추가하는 작업
디큐(dequeue) : 큐에 데이터를 꺼내는 작업
큐에서 프런트는 맨 앞의 원소를, 리어는 맨 끝의 원소를 가리킨다.
heapq.heappush(heap,data)
------heap에서 data를 인큐한다.
heapq.heappop(heap)
------heap에서 data를 디큐한다.
링 버퍼
- 디큐할때 배열 안의 원소를 옮기지 않는 큐를 구현하는 자료구조
front : 맨 앞 원소의 인덱스
rear : 맨 끝 원소 바로 뒤의 인덱스(다음 인큐되는 데이터가 저장되는 위치)
(큐에서 프런트와 리어와 다른것이다.)
링 버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear의 값을 업데이트 하는 것만으로 인큐와 디큐를 수행할 수 있다.
덱(deque)
덱(deque : double-ended queue)은 맨 앞과 맨 끝 양쪽에서 데이터를 모두 삽입 삭제할 수 있는 자료구조이다.
큐와 스택을 합친 형태라고 생각하면된다.