스택

데이터를 검색하는 find()

def find(value : Any) -> int:

if is_empty() :
	raise FixedStack.Empty
    
while self.stk[self.ptr] is not None :
	if self.stk[self.ptr] == value
    	return self.ptr
    else:
    	self.ptr -= 1
        if self.ptr == 0 :
        	return False
            

실제 코드는...
위에부터 선형 검색이 맞는데,
확실히 나는 시작 지점을 지정해주지 않았지만,
정답 코드에서는...

ptr은 가장 위의, 비어있는 칸을 가리키는 거니까
range를 self.ptr -1부터 -1까지, -1 단위로 나열한다.
range는 마지막 숫자는 포함안하니까 -1로 했다.

그렇기 때문에 따로 ptr를 감소시킬 필요는 없고,
(그리고 아마 감소시켜도 안 된다고 생각한다.)
(왜냐하면, 그렇게 하면 이 함수를 실행하고 나서는 ptr이 0이 되어버릴테니.)

(어디까지나 ptr은 실제로 이동시키는게 아니면 값으로 따로 써야한다는 사실을 주의하자.)
실패시 -1을 반환하는 건... 음 뭐 잘 모르겠다.

아무래도 이미 돌려주는 값의 자료형이 정해져있으니,
False를 대신에 반환하는 게 아닐까 싶다.

데이터 개수를 세는 count()

스택에 쌓여있는 데이터의 개수를 구하여 반환한다.
검색하는 데이터가 중복으로 몇개 있는지 반환하는 것이다.

def count(value:Any) -> int:
	count = 0
    
    if is_empty():
    	raise FixedStack.Empty
    
    for i in range(self.ptr -1, -1, -1):
    if self.stk[i] ==value:
    	count += 1
    return count    

맞앗당
따로 empty를 확인하지 않는 것만 빼면!

데이터가 포함되어있는지 판단하는 __contain()

스택 내에 그 데이터가 있는지 판단하고,
맞으면 True, 아니면 False를 반환한다.

find랑 똑같이 짜고 반환하는 것만 다르면 안 되나?

보니까 count()시키고 0과 비교한다

return self.count(value) > 0

흠...
진짜 쉽게 쓰네.

? 멤버십 판단 연산자(membership test operator)

x in s로 수행할 수 있....다...
보충수업 4-3이 알려준다고 한다

언더스코어가 앞뒤로 두개씩 붙은 함수는 특별한 의미가 있다고 한다. (다들 이거 벨로그에서 쓸땐 어떻게 붙이게 할까..코드화시키나.)

len의 경우는 이걸 정의하면,
obj.__len__() 대신 len(obj)라고 쓸 수 있게 된다고 한다.

contains의 경우,
함수 이름을 다 안 쓰고 x in obj 로 구현이 가능하다고 한다.

이 더블 언더스코어를, __를 던더(dunder)라고 하고,
그래서 이게 해당하는 함수를 던더 함수라고 하며,
len은 렌 던더, 또는 던더 렌이라고 한다고 한다.

deque()로 구현하기

여러 컨테이너를 collections 모듈로 제공한다.

주요 속성
maxlen
append(x) 오른쪽(맨 끝)에 추가
appendleft(x) 왼쪽(맨 앞)에 추가
clear()
copy() 얕은 복사
count(x)
extend(iterable)
extendleft(iterable) iterable에서 가져온 원소를 맨앞, 왼쪽에 추가.

index(x,[,start[,stop]]) 검색을 시작하는 인덱스, 검색을 종료할 인덱스를 start와 stop으로주고 x를 찾음.

insert(i,x) i번째에 x삽입
pop()
popleft()
remove(value)
reverse() 역순으로 정렬.
rotate(n=1) 모든 원소를 n값만큼 오른쪽으로 밀어낸다. n이 음수라면 왼쪽으로 밀어낸다.

? iterable

반복 가능한 객체.
리스트, 딕셔너리, 셋, 문자열, 바이트, 튜플, 레인지.
bytes, range..str..

? enumerate()

for i in enumerat(t):
print(i)

를 하면 앞에는 인덱스 번호, 뒤에는 컬렉션 원소를 튜플 형태로 반환해준다.

(0, 1)
(1, 2) ...

큐(Queue)란?

스택과 같이 데이터를 임시 저장하는 자료 구조.

큐 알아보기

선입선출 구조.

큐에 데이터를 추가하는 작업을 인큐(enqueue),
데이터를 꺼내는 작업을 디큐(dequeue),
데이터를 꺼내는 쪽을 front, 넣는 쪽을 rear라고 한다.

인큐하기

다음 데이터에 바로 저장함.
처리 복잡도 O(1)

디큐하기

2번째 이후 원소를 모두 앞쪽으로 옮겨줘야한다.
처리 복잡도 O(n)
효율성이 좋지 않다!

우선 순위 큐?(priority queue)

인큐할 때 데이터 우선순위를 부여하여 추가하고,
디큐할 때 우선순위가 가장 높은 데이터를 꺼낸다.

파이썬에서는 우선 순위를 부여하는 큐를 heapq 모듈에서 제공한다.

heapd에서 인큐는
heapq.heappush(heap, data)로 수행,
디큐는
heapq.heappop(heap)으로 수행한다.
이 프로그램은 6장에서 다룬다.

링 버퍼로 큐 구현하기

디큐할때 배열 안의 원소를 옮기지 않는 큐를 구현해보자.
이 때의 자료구조를 링 버퍼(ring buffer)라고 한다.

맨끝의 원소 뒤에, 맨 앞의 원소가 연결되는 자료구조다.

어떤 원소가 맨 끝원소인지 식별하는 변수가
front와 rear다.

• front
  맨 앞 원소의 인덱스
• rear
  맨끝 원소 바로 뒤의 인덱스
  (다음 인큐되는 데이터가 저장되는 위치)

...

흠.
내가 생각하기에 인큐를 프론트와 리어로 구현한다면
인큐는 그냥 리어에 값을 넣으면 되고
디큐는.. 프론트의 값을 지운다음에 프론트를 한칸 뒤로 가면 되는 거 아닌가?

근데 어떻게 써야할지는 잘 감이 안 잡힌다.

원리는 그게 맞다고 한다.

그렇게 해서, 원소를 옮길 필요 없이 프론트와 리어를 업데이트하는 것만으로 수행할 수 있기 때문에 처리 복잡도는 O(1)이라고 한다.

고정 길이 큐를 구현해본다고 한다!

FixedQueue 구현하기

예외 처리 시키는 Empty와 Full,
초기화하는 init,
데이터 개수를 알아내는 len()
비어있는지 판단하는 is_empty()
가득 차있는지 판단하는 is_full()

데이터를 넣는 enque()
데이터를 꺼내는deque()

앞의 건 속성을 class로 Exception을 만들어서 만들어주고,

init은..

self.front = 0
self.rear = 0
self.capacity = capacity

그리고 두개를 더 한다.
데이터의 개수인 no, 큐의 본체인 que.

self.no = 0
self.que = [None] * capacity

len()
그냥 no만 반환하면 되겠네...

is_empty랑 full도 no로 확인하고...

enque()

넣는건...

def enque(key: Any) -> bool:
	if self.no == capacity:
    	return False
        
    self.que[self.rear] = key
	self.rear +=1
	self.no +=1
    return True

하.. 하려다말았는데 is_full()로 raise FixedQueue.Full 처리하네

아!! 그리고 링 버퍼라서 들어가는 부분이 있다!
이거 궁금했는데 이렇게 하네.

만약 다 안 찼는데 끝에 다다랐다! 라면...
rear를 0으로 초기화해준다.
끝에 다다른걸 capacity로 판단해주고 있다.
그리고 딱히 성공 여부를 반환해주진 않네.
None으로 끝낸다.

deque()

deque는...

def deque(self) -> Any :
	if self.is_empty():
    	raise FixedQueue.Empty
        
    value = self.que[self.front]
    self.que[self.front] = None
    self.no -= 1
    if self.front == self.capacity :
    	self.front = 0
    else :
    	self.front += 1
    return value
    
    

딱 한부분이 다른데,
원래 있던 자리를 비워주는 부분이다.
나는 None으로 바꿔놨는데,
여기는...
프론트를 먼저 증가시켜주고(그냥 참조 부분만 바뀌면 되니까)
근데 그 값이 스택 크기와 같다면 0으로 바꿔준다.

capacity는 크기라 원래 크기랑 딱 같은데,
front는 인덱스라 0부터 시작하기때문에
마지막이라면 1을 더해줘야 일치하기 때문에 수정해줬다...

self.front += 1..

count()

그 해당하는 개수가 몇개나 있는지 반환...하는 거지?

for i in range(front,rear):
	if key == self.que[i] :
    	c += 1
    return c
    

아!
링버퍼라서, 꼭 프론트라고해서 앞에 있는 것도, 리어라고 해서 뒤에 있는 것도 아니구나.

그래서 아예 데이터 개수인 no로 range를 잡은 후에,
인덱스를...
뭐 no면 1부터 반환할테니까...

idx = ( i + self.front) % self.capacity

난 잘 모르겠군.

이제보니 빼먹은게 peek()와 find()가 있다.
한번 보겠다!

peek()

다음 디큐에서 꺼낼 데이터를 들여다본다.
front, rear, no의 값은 변하지 않고,
비어있을 때는 예외 클래스 처리를 해준다.

def peek(self) -> Any:
	if is_Empty():
    	return FixedQueue.Empty
	return self.que[self.front]

find()

value와 같은 데이터가 포함되어있는 위치를 알아낸다.
인덱스를 구하는 식은 (i + front) % capacity를 한다.

하...

아마 front값을 바꾸지 않고,
capacity로 나누면 나머지가 나와서 capacity 내에서 증가하기때문에 거기에 i를 더한 일종의 값으로 사용하는 것 같다.

그래서 count는 c를 거기서 더할뿐이고,
find는 그 값을 반환하는 것 뿐이다.

링 버퍼의 활용?

링 버퍼는 오래된 데이터를 버리는 용도로 활용할 수 있다.
예를 들어 원소 수가 n인 배열에서
데이터를 계속해서 입력할때,

가장 최근에 들어온 데이터 n개만 저장하고,
나머지 오래된 데이터는 버리는 경우다.

(무한히 입력하지만, 메모리가 늘어나진않고,
이전에 입력했던 값은 자연히 사라진다.)

cnt = 0 # 정수를 입력받은 개수
n = int(input()) # 링 버퍼의 크기.

a[cnt % n] = int(input())
cnt += 1

1개를 입력받았을 때, 3개의 queue일때.

a[1]에 들어가게된다.

2개를 입력받았을떄, 3개의 queue일떄.

a[2]에 들어가게 된다.

...
결론적으로는 아까 find의 index 지정 원리와 같음.