스택 이란 ?
- 스택은 데이터를 임시 저장할 때 사용하는 자료구조
- 후입선출 방식 FILO 이다 (가장 나중에 넣은 데이터를 가장 먼저 꺼냄)
- 스택에 데이터를 넣는 작업을 푸시, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다.
- 스택 배열 : stk (푸시한 데이터를 저장하는 스택 본체인 리스트형 배열), stk[0]은 스택의 바닥
- 스택 크기 : capacity (스택의 최대 크기) , equal len(stk)
- 스택 포인터 : ptr (스택에 쌓여있는 데이터의 개수)
* 예외처리 : 오류를 복구하여 프로그램이 중단되는 것을 피함
- 원래 처리하는 코드와 오류가 발생할 때 대처하는 코드를 분리
* raise : 일부러 오류 발생
-스택 클래스 정의
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
from typing import Any
class FixedStack:
class Empty(Exception):
pass
class Full(Exception):
pass
def __init__(self,capacity : int =256) -> None:
self.stk=[None]*capacity
self.capacity=capacity
self.ptr=0
def __len__(self) ->int:
return self.ptr
def is_empty(self) -> bool:
return self.ptr<=0
def is_full(self)->bool:
return self.ptr>=self.capacity
def push(self, value: Any)-> None:
if self.is_full():
raise FixedStack.Full
self.stk[self.ptr]=value
self.ptr+=1
def pop(self)->Any:
if self.is_empty():
raise FixedStack.Empty
self.ptr-=1
return self.stk[self.ptr]
def peek(self)->Any:
if self.is_empty():
raise FixedStack.Empty
return self.stk[self.ptr-1]
def clear(self)->None:
self.ptr=0
def find(self,value:Any) -> Any:
for i in range(self.ptr -1,-1,-1):
if self.stk[i]==value:
return i
return -1
def count(self,value:Any)->bool:
c=0
for i in range(self.ptr):
if self.stk[i]==value:
c+=1
return c
def __contains__(self,value:Any)-> bool:
return self.count(value)
def dump(self)-> None:
if self.is_empty():
print("스택이 비어있습니다.")
else:
print(self.stk[:self.ptr])
|
cs |
-
- 스택 클래스 실행
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
from enum import Enum
from fixed_stack import FixedStack
Menu=Enum('Menu',['푸시','팝','피크','검색','덤프','종료'])
def select_menu() -> Menu:
s = [f'({m.value}){m.name}' for m in Menu] # (1) 푸시 (2) 팝 ... 으로 표현하기 위해
while True:
print(*s,sep=' ',end='')
n=int(input(': '))
if 1<= n <= len(Menu): # 1부터 설정한 번호까지 입력을 하기 위해
return Menu(n) # 1 = Menu.푸시, 2 = Menu.팝 ...
s = FixedStack(64) # FixedStack에 64를 넣음 capcity=64
while True:
print(f'현재 데이터 개수: {len(s)} / {s.capacity}') # __len__ 함수를 통해 len(s) 는 ptr 값을 반환
menu=select_menu()
if menu == Menu.푸시:
x=int(input('데이터를 입력하세요 :'))
try:
s.push(x)
except FixedStack.Full:
print('스택이 가득 차 있습니다.')
elif menu== Menu.팝:
try:
x=s.pop()
print(f'팝한 데이터는 {x}입니다')
except FixedStack.Empty:
print('스택이 비어있습니다.')
elif menu== Menu.피크:
try:
x=s.peek()
print(f'피크한 데이터는 {x}입니다.')
except FixedStack.Empty:
print('스택이 비어있습니다.')
elif menu== Menu.검색:
x=int(input("검색할 값을 입력하세요."))
if x in s:
print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
else:
print("검색값을 찾을 수 없습니다.")
elif menu== Menu.덤프:
s.dump()
else:
break
|
cs |
-결과
- 결론 : 스택은 FILO로 가득 찼을 때와 비어 있을 때를 예외 처리를 해두고 푸시 할 때 스택 배열[ptr] 에 값을 넣어주면서 ptr 값을 증가 시켜준다. 이후 팝을 할 때 ptr 값이 가장 위에 있는 값, 마지막에 넣어 둔 값으로 스택 배열[ptr]값을 반환해 주면 된다.
* 새로 알게 된 점
1. 타입 모듈 (타입을 직접 지정할 수 있다.)
from typing import Any
2. 예외처리
class 예외처리이름(Exception):
pass
if 조건:
raise class.예외처리이름
3. 초기화 함수(반드시 해줘야 한다.)
__init__(self,변수1, 변수2.. ):
self.변수1=변수1
self.변수2=변수2
4. 데이터 개수 반환 ( len() 함수를 쓰게 함으로써 간단하게 표현하게 해준다.)
__len__() :
return 클래스의 데이터 변수
-> len(클래스)
5. 열거형 모듈 (자신만의 집합을 생성)
from enum import Enum
- enum은 기본적으로 name 과 value를 갖는다.
-> Menu = Enum('Menu ' , 'red, blue, gray') # 띄어쓰기로 구분
ex) 1. Menu(1) == Menu.red
ex) 2. Menu.red.value=1 , Menu.red.name= red
큐란 ?
1. 큐는 스택과 같이 데이터를 임시저장하는 자료구조이다.
2. 선입 선출 방식 FIFO 이다. (가장 먼저 넣은 데이터를 가장 먼저 꺼낸다.)
3. 큐에 데이터를 추가하는 작업을 인큐, 데이터를 꺼내는 작업을 디큐라고 하며
데이터를 꺼내는 쪽을 프런트, 데이터를 넣는 쪽을 리어라고한다.
(큐에서 프런트는 맨 앞의 원소를 리어는 맨 끝의 원소를 가리킨다.)
- 큐 구현하기
1. 배열 버퍼로 큐 구현하기
- 디큐를 할 때마다 원소를 하나씩 앞으로 이동한다.
2. 링 버퍼로 큐 구현하기
- 디큐를 할 때마다 원소를 옮기지 않는다.
- 맨 앞의 원소가 front 맨 뒤의 원소 rear를 이용하여 원소를 옮길 필요 없이 업데이트만으로 수행가능
- 큐 클래스 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
from typing import Any
class FixedQueue:
class Empty(Exception):
pass
class Full(Exception):
pass
def __init__(self,capacity: int) -> None: # 초기화 함수
self.no=0 # 데이터의 개수
self.front=0 # 맨 앞의 원소를 나타냄
self.rear=0 # 맨 뒤의 원소
self.capacity=capacity #최대 크기 초기화
self.que=[None]*capacity # 큐 배열 저장
def __len__(self) ->int: # 추가한 데이터 개수 반환
return self.no
def is_empty(self) -> bool:
return self.no<=0
def is_full(self)->bool:
return self.no>=self.capacity
def enque(self, x: Any)-> None:
if self.is_full(): # 초과하면 예외처리
raise FixedQueue.Full
self.que[self.no]=x
self.rear+=1
self.no+=1
if self.rear==self.capacity: # rear이 최대크기와 같으면 rear은 0이다. (링 형이므로)
self.rear=0 # (초과는 위에서 예외처리를 하므로 되지 않는다.)
def deque(self)->Any:
if self.is_empty():
raise FixedQueue.Empty
x= self.que[self.front]
self.front+=1
self.no-=1
if self.front==self.capacity:
self.front=0
return x
def peek(self)->Any:
if self.is_empty():
raise FixedQueue.Empty
return self.que[self.front]
def clear(self)->None:
self.no= self.front=self.rear= 0
def find(self,value:Any) -> Any:
for i in range(self.no):
idx= (i+self.front) % self.capacity # i+self.front 로 인덱스 번호를 알 수 있다. 하지만 capacity 를 초과화면
if self.que[idx]==value: # 번호를 구할 수 없으니 (i+self.front) % capacity를 하여 인덱스 번호를 구한다.
return idx
return -1
def count(self,value:Any)->bool:
c=0
for i in range(self.no):
idx= (i+self.front) % self.capacity
if self.que[idx]==value:
c+=1
return c
def __contains__(self,value:Any)-> bool:
return self.count(value)
def dump(self)-> None:
if self.is_empty():
print("스택이 비어있습니다.")
else:
for i in range(self.no):
print(self.que[(i+self.front)%self.capacity], end='')
print()
|
cs |
- 큐 클래스 실행
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
from enum import Enum
from fixed_queue import FixedQueue
Menu=Enum('Menu',['인큐','디큐','피크','검색','덤프','종료'])
def select_menu() -> Menu:
s = [f'({m.value}){m.name}' for m in Menu] # (1) 인큐 (2) 디큐...
while True:
print(*s,sep=' ',end='')
n=int(input(': '))
if 1<= n <= len(Menu):
return Menu(n) # 1 = Menu.인큐, 2 = Menu.디큐 ...
q = FixedQueue(64) # FixedQueue에 64를 넣음 capcity=64
while True:
print(f'현재 데이터 개수: {len(q)} / {q.capacity}') # __len__ 함수를 통해 len(q) 는 no 값을 반환
menu=select_menu()
if menu == Menu.인큐:
x=int(input('인큐할 데이터를 입력하세요 :'))
try:
q.enque(x)
except FixedQueue.Full:
print('큐가 가득 차 있습니다.')
elif menu== Menu.디큐:
try:
x=q.deque()
print(f'팝한 데이터는 {x}입니다')
except FixedQueue.Empty:
print('큐가 비어있습니다.')
elif menu== Menu.피크:
try:
x=q.peek()
print(f'피크한 데이터는 {x}입니다.')
except FixedQueue.Empty:
print('큐가 비어있습니다.')
elif menu== Menu.검색:
x=int(input("검색할 값을 입력하세요."))
if x in s:
print(f'{q.count(x)}개 포함되고, 맨 앞의 위치는 {q.find(x)}입니다.')
else:
print("검색값을 찾을 수 없습니다.")
elif menu== Menu.덤프:
q.dump()
else:
break
|
cs |
- 결과
- 결론 : 큐는 FIFO 방식으로 front , rear 값을 이용하여 디큐를 실행한다.
스택과 마찬가지로 예외처리를 선언하고 큐 배열[no]에 값을 넣어 인큐를 수행한다.
여기서 인큐를 함으로써 no값이 증가하고 rear 값이 1 증가하며 rear 값이 capacity 값과 같다면 0으로 돌아간다
(링 형이므로 capacity = 6 rear=6 이면 한바퀴를 돌았다고 생각)
디큐는 큐 배열[front] 값을 반환한다. 여기서 디큐를 함으로써 front 값이 반환됨으로 no 값이 감소하고
front 값은 1이 증가하게 된다. 인큐와 마찬가지로 front 값이 capacity와 같으면 0으로 돌아간다.
find함수와 count함수에서 중요한 부분은 바로 인덱스 번호를 찾는 것이다. 스택과 찾는 부분이 비슷하지만 링 형이라 는것을 명심해야 한다. 반복문을 돌려 (i+front ) % capacity 를 하여 해당하는 인덱스 번호를 찾아낸다.
front 변수는 초기 값이라 생각하면 되며 링 형이므로 capacity를 초과했을 때 인덱스 번호를 알기 위해 % capacity를 수행한다.
- 링 버퍼의 활용 ( FIFO 방식으로 데이터를 인큐 및 디큐)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
n=int(input())
a= [None]*n
cnt=0
while True:
a[cnt%n]=int(input(f'{(cnt%n)+1}번째 정수를 입력하세요 : ')) # 링 형은 반드시 순서 변수 % 전체크기를 해줘야 한다.
cnt+=1
retry=input(f'계속 할까요? (Y..YES / N.. NO):')
if retry in { 'N', 'n'}:
break
i=cnt-n # i는 시작 값이다. cnt가 n을 넘어서면 시작 값이 바뀌기 떄문에 i=cnt-n 이다.
if i<0 : i=0 #i가 음수면 cnt가 n보다 작다는 뜻으로 배열을 한바퀴 돌리지 않았다는 의미로 시작 값은 0 이다.
while i<cnt:
print(f'{i+1}번째= {a[i%n]}') # 인덱스번호= 시작 변수 % 전체크기
i+=1
|
cs |
* 링 형을 배열로 표현할 때의 인덱스 번호는 순서 변수 % 전체 크기 이다.
'Python > 자료구조 내용 정리' 카테고리의 다른 글
자료구조 6장 - 정렬 알고리즘 (0) | 2021.08.13 |
---|---|
자료구조 5장 - 재귀 알고리즘 (0) | 2021.08.09 |
자료구조 - 3장 검색 알고리즘 (0) | 2021.07.29 |
자료구조 - 2장 기본 자료구조와 배열 (0) | 2021.07.27 |
자료구조 - 1장 알고리즘 기초 (0) | 2021.07.27 |