스택
- 가장 먼저 넣은 것을 가장 나중에 뽑을 수 있는 구조
- LIFO, Last In First Out (후입선출)
- 한 쪽 끝이 막힌 형태
- 기본 구조
- 스택에 데이터 삽입하는 작동: push
- 스택에 데이터 추출하는 작동: pop
- 스택에 들어있는 가장 위의 데이터: top (위치)
스택 empty, full
- 스택이 비어있는지 확인
-
top값이 -1 이면 스택은 비어있는 상태
def isStackEmpty(): # 스택이 비었는지 확인하는 함수 global SIZE, stack, top if (top == -1) : # 초기화 시 -1로 지정해두기 때문 return True else: return False
-
- 스택이 꽉 차있는지 확인
-
top 값이 ‘스택크기 -1’과 같다면 스택은 꽉 찬 상태
def isStackFull(): # 스택이 꽉 찼는지 확인하는 함수 global SIZE, stack, top if (top >= SIZE-1): # top 값 == 스택크기 - 1: 스택이 꽉 찼음 return True else: return False
-
데이터 삽입
추출
- 데이터 삽입: push
def push(data): # 스택에 데이터를 삽입하는 함수 global SIZE, stack, top if (isStackFull()): # True 값 반환 시, 오버플로우 발생하지 않게 하도록 print("스택이 꽉 찼습니다.") return top += 1 # 가장 위를 칭하는 값에 +1 해줌 stack[top] = data # 데이터 삽입 - 데이터 추출: pop
def pop(): # 스택에서 데이터를 추출하는 함수 global SIZE, stack, top if (isStackEmpty()): print("스택이 비었습니다.") return None data = stack[top] # 가장 위(최근)에 들어온 데이터를 data에 복사 stack[top] = None # stack[top] 지정 데이터 삭제 top -= 1 # top의 위치 변경 return data # pop 출력, 미리 data에 복사했던 것 출력
데이터 확인
- top 위치의 데이터 확인만 하고 스택에 그대로 두는 것
- peek()
def peek(): # 스택에서 top 위치의 데이터를 확인하는 함수 global SIZE, stack, top if (isStackEmpty()): print("스택이 비었습니다.") # 비어있는 경우, top == -1, stack[-1] 이어봤자 None... return None else: return stack[top] # return만 stack[top]으로 간단하게 구현
- 최종 코드
## 스택 작동을 위한 통합 코드 ## 함수 선언 부분 ## def isStackFull(): # 스택이 꽉 찼는지 확인하는 함수 global SIZE, stack, top if (top >= SIZE-1): # top 값 == 스택크기 - 1: 스택이 꽉 찼음 return True else: return False def isStackEmpty(): # 스택이 비었는지 확인하는 함수 global SIZE, stack, top if (top == -1) : # 초기화 시 -1로 지정해두기 때문 return True else: return False def push(data): # 스택에 데이터를 삽입하는 함수 global SIZE, stack, top if (isStackFull()): # True 값 반환 시, 오버플로우 발생하지 않게 하도록을 위함! print("스택이 꽉 찼습니다.") return top += 1 # 가장 위를 칭하는 값에 +1 해줌 stack[top] = data # 데이터 삽입 def pop(): # 스택에서 데이터를 추출하는 함수 global SIZE, stack, top if (isStackEmpty()): print("스택이 비었습니다.") return None data = stack[top] # 가장 위(최근)에 들어온 데이터를 data에 복사 stack[top] = None # stack[top] 지정 데이터 삭제 top -= 1 # top의 위치 변경 return data # pop 출력, 미리 data에 복사했던 것 출력 def peek(): # 스택에서 top 위치의 데이터를 확인하는 함수 global SIZE, stack, top if (isStackEmpty()): print("스택이 비었습니다.") # 비어있는 경우, top == -1, stack[-1] 이어봤자 None... return None else: return stack[top] # return만 stack[top]으로 간단하게 구현 ## 전역 변수 선언 부분 ## SIZE = int(input("스택 크기를 입력하세요 ==> ")) stack = [None for _ in range(SIZE)] top = -1 ## 메인 코드 부분 ## if __name__ == "__main__": select = input("삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> ") while (select != 'X' and select != 'x'): # X 누르기 전까지! X는 종료 if select == 'I' or select == 'i': # 삽입 data = input("입력할 데이터 ==> ") push(data) print("스택 상태: ", stack) elif select == 'E' or select == 'e': data = pop() print("추출된 데이터 ==>", data) # 추출 print("스택 상태: ", stack) elif select == 'V' or select == 'v': # data = peek() print("확인된 데이터 ==>", data) print("스택 상태: ", stack) else: print("입력이 잘못됨") select = input("삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> ") print("프로그램 종료!")
---
스택 응용
- 웹 서핑에서 이전 페이지 돌아가기
- 괄호 매칭 검사
- 닫는 괄호를 만났을 때 스택은 비어있지 않아야 한다.
- 닫는 괄호를 만났을 때 추출한 괄호는 여는 괄호여야 한다.
- 2를 만족해도, 두 괄호의 종류는 같아야 한다.
- 모든 수식의 처리가 끝나면 스택은 비어 있어야 한다.
큐
순차 큐
-
입구와 출구가 따로 있는 원통 형태
-
먼저 들어간 것이 먼저 나오는 구조
- FIFO, First In First Out, 선입선출
-
스택과 큐의 차이
-
큐의 구조와 용어
- 큐에 데이터를 삽입하는 작동: enQueue(인큐)
- 데이터를 추출하는 작동: deQueue(데큐)
- 저장된 데이터 중 첫 번째 데이터: front(머리)
- 첫 시작 = -1
- 저장된 데이터 중 마지막 데이터: rear(꼬리)
- 첫 시작 = -1
순차 큐
삽입, 추출, 확인
-
큐가 꽉 찼는지 확인하는 함수: isQueueFull
def isQueueFull() : # 큐가 꽉 찼는지 확인하는 함수 global SIZE, queue, front, rear if (rear != SIZE-1) : return False # 애초에 다 차지 않음 elif (rear == SIZE -1) and (front == -1) : # 모든 칸에 전부 차 있는 경우 return True else : # rear == SIZE -1 and front != -1 / 즉, 앞 칸이 비어있고 끝까지 차있는 경우 for i in range(front+1, SIZE) : # 데이터를 왼쪽으로 한 칸씩 옮긴다! queue[i-1] = queue[i] queue[i] = None front -= 1 rear -= 1 # rear을 옮기게 되면 어찌 되었건 full이 아닌 상태 return False -
큐가 비었는지 확인하는 함수: isQueueEmpty
def isQueueEmpty() : # 큐가 비었는지 확인하는 함수 global SIZE, queue, front, rear if (front == rear) : # 둘 다 업데이트 안 됨 return True else : return False -
데이터 삽입: enQueue
def enQueue(data) : # 큐에 데이터를 삽입하는 함수 global SIZE, queue, front, rear if (isQueueFull()): # 오버 플로우 방지! print("큐가 꽉 찼습니다.") return rear += 1 # rear 먼저 추가! queue[rear] = data # 이후 queue의 rear 인덱스에 data 넣기 -
데이터 추출: deQueue
def deQueue() : # 큐에서 데이터를 추출하는 함수 global SIZE, queue, front, rear if (isQueueEmpty()): # 언더 플로우 방지! print("큐가 비었습니다.") return None front += 1 # front +1 업데이트 data = queue[front] # front에 해당하는 데이터를 미리 data에 복사 queue[front] = None # front에 해당하던 데이터 삭제 return data # 복사해둔 거 출력 -
추출될 데이터 확인: peek
def peek() : # 큐에서 front+1 위치의 데이터를 확인하는 함수 global SIZE, queue, front, rear if (isQueueEmpty()) : print("큐가 비었습니다.") return None return queue[front+1] # 추출될 데이터 확인 = front+1
큐의 응용 - 원형 큐
-
큐의 처음과 끝이 연결된 구조
- 순차 큐에서는 1단계에서 오버헤드 발생
- 데이터가 찬 순차 큐에서, 오로지 새로운 삽입을 위해 rear을 옮겨야하는 일이 발생
→ 전체 데이터를 왼쪽으로 옮기는 일련의 과정
- 데이터가 찬 순차 큐에서, 오로지 새로운 삽입을 위해 rear을 옮겨야하는 일이 발생
- 원형 큐는 순차 큐를 구부려 끝을 이음
- 오버헤드 발생 X
- 순차 큐에서는 1단계에서 오버헤드 발생
-
원형 큐다 보니, 숫자가 늘어나는 구조가 아니라 순환하는 구조
-
따라서, % 로 계산!
-
- 최종 코드
## 함수 선언 부분 ## def isQueueFull() : global SIZE, queue, front, rear if ( (rear + 1) % SIZE == front) : return True else : return False def isQueueEmpty() : global SIZE, queue, front, rear if (front == rear) : return True else : return False def enQueue(data) : global SIZE, queue, front, rear if (isQueueFull()) : print("큐가 꽉 찼습니다.") return rear = (rear + 1) % SIZE queue[rear] = data def deQueue() : global SIZE, queue, front, rear if (isQueueEmpty()) : print("큐가 비었습니다.") return None front = (front + 1) % SIZE data = queue[front] queue[front] = None return data def peek() : global SIZE, queue, front, rear if (isQueueEmpty()) : print("큐가 비었습니다.") return None return queue[(front + 1) % SIZE] ## 전역 변수 선언 부분 ## SIZE = int(input("큐의 크기를 입력하세요 ==> ")) queue = [ None for _ in range(SIZE) ] front = rear = 0
나는 데단한 데싸인 ☠️