선형 자료구조 - 스택, 큐
19099 단어 자료구조와 알고리즘CSCS
1. 스택(Stack)
- LIFO(Last In First Out)
- pop, push, peek, isEmpty 등의 연산이 있다.
1.1 스택의 함수
1.1.1 pop
- 스택 구조에서 가장 나중에 추가된 원소를 빼내서 반환
- 비어있는 스택에서
pop
연산을 할 경우stack underflow
가 발생
1.1.2 push
- 스택의 구조의 맨 뒤에 원소를 추가
1.1.3 peek
- 스택의 top의 가장 맨 위의 요소를 반환
1.1.4 size
- 스택의 현재 크기를 반환
1.1.5 isEmpty
- 스택이 비어있으면 True(1), 그렇지 않으면 False(0) 반환
1.3 구현
class stack:
def __init__(self):
self.items = []
def isEmpty(self):
if item:
return 0
else:
return 1
def push(self, item):
if item:
self.items.append(item)
def push(self):
if item:
self.items.pop(item)
def peek(self):
return self.items[-1]
def size(self):
if item:
return len(self.items)
myStack = stack()
myStack.isEmpty() # 1
myStack.push(1)
myStack.push(2)
myStack.push(3)
myStack.peek() # 3
myStack.size() # 3
print(myStack.pop()) # 3
print(myStack.pop()) # 2
print(myStack.pop()) # 1
2. 큐(Queue)
- FIFO(First In First Out)
- 삭제만 수행되는
front
과 삽입만 수행되는rear
를 통해 큐의 상태를 표현
2.3 큐의 함수
2.3.1 enQueue
rear
부분에 원소를 추가
1.1.2 dequeue
front
부분의 원소 제거 후 반환
1.1.3 isEmpty
- 큐가 비어있으면 True(1), 그렇지 않으면 False(0) 반환
1.1.4 size
- 큐의 현재 크기를 반환
1.3 선형 큐 구현
class queue:
def __init__(self):
self.items = []
#self.front = 0
#self.rear = 0
def isEmpty(self):
if item:
return 0
else:
return 1
def enqueue(self, item):
if item:
self.items.append(item)
def dequeue(self):
if item:
tmp = self.items.pop(0)
return tmp
def size(self):
if item:
return len(self.items)
myStack = queue()
myStack.isEmpty() # 1
myStack.enqueue(1)
myStack.enqueue(2)
myStack.enqueue(3)
myStack.size # 3
print(myStack.dequeue()) # 1
print(myStack.dequeue()) # 2
print(myStack.dequeue()) # 3
- 파이썬으로 구현하게 되면 리스트의 크기를 알아서 조절해주기 때문에
front == rear
인 상황은 항상 큐가 비어있는 상태이다 하지만 C언어를 이용해 구현할 경우 항상 비어있는 상태는 아니다.
1.4 원형 큐 구현
SIZE = 5 # 큐 사이즈 제한
class queue:
def __init__(self):
self.items = [None] * SIZE
self.front = 0
self.rear = 0
def isEmpty(self):
if self.front == self.rear:
return 1
else:
return 0
def isFull(self):
if self.front == (self.rear + 1) % SIZE:
return 1
else:
return 0
def enqueue(self, item):
if self.isFull() != 1:
self.rear = (self.rear + 1) % SIZE
self.item[self.rear] = item
def dequeue(self):
if self.isEmpty != 1:
tmp = item[self.front]
self.front = (self.front + 1) % SIZE
return tmp
def size(self):
if item:
return (self.rear - self.front + SIZE) % SIZE
myStack = queue()
myStack.isEmpty() # 1
myStack.enqueue(1)
myStack.enqueue(2)
myStack.enqueue(3)
myStack.size # 3
print(myStack.dequeue()) # 1
print(myStack.dequeue()) # 2
print(myStack.dequeue()) # 3
출처
Author And Source
이 문제에 관하여(선형 자료구조 - 스택, 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@main_string/선형-자료구조-스택저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)