Python에서 스택 데이터 유형 만들기
Python에서 스택 데이터 유형 만들기
소개
스택은 데이터 구조 및 분석에 들어가기 전에 항상 공부해야 하는 기본 데이터 구조 중 하나입니다. ADT(Abstract Data Type)where operations are predefined의 예입니다. Queue, List 등과 같은 다른 유형의 ADT도 있습니다.
운영
모든 데이터 유형에 대해 가장 일반적인 작업에는 데이터 삽입, 데이터 제거 및 데이터 검색이 포함됩니다. 단순 스택의 경우 3가지 유형의 작업이 있습니다.
푸시 : 스택 맨 위에 데이터를 삽입합니다.
Pop : 스택의 맨 위에서 데이터를 제거합니다.
Top : 최상위 요소 데이터를 검색합니다.
스택은 LIFO(Last In First Out) 방식으로 작동합니다. 즉, 언제든지 포인터는 스택의 맨 위에 있고 포인터가 가리키는 데이터로만 작업할 수 있습니다. 스택이 배열을 사용하려는 경우 크기는 고정되지만 목록을 사용하려는 경우 크기는 가변적입니다.
푸시 작업
[4 5 6 8 5 2] 데이터와 함께 크기가 6인 스택용 배열을 사용한다고 가정해 보겠습니다. 처음에는 스택이 비어 있고 포인터가 스택 데이터의 맨 아래를 가리킬 것입니다. 이제 첫 번째 단계에서 데이터를 푸시하기 위해 0번째 위치에서 4를 푸시합니다. 그런 다음 포인터가 한 단계 위로 이동합니다. 다음 단계에서 다음 데이터가 첫 번째 위치에 삽입됩니다. 그리고 마침내 스택이 가득 찰 것입니다.
파이썬으로 작성해 봅시다.
class Stack:
def __init__ (self, size):
self.size = size
self.storage = ["~"]*size
self.pointer = 0
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer}.\n")
def push(self, x):
self.storage[self.pointer] = x
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer+1}.\n")
self.pointer+=1
data = [4, 5, 6, 8, 5, 2]
stack = Stack(size=6)
for x in data:
stack.push(x)
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.
New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.
New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.
New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.
New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.
New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.
New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
이제 스택에 데이터를 삽입했지만 스택 크기보다 더 많은 데이터를 삽입하면 어떻게 될까요? 이 경우 오버플로가 발생하고 위의 예에서 목록을 저장소로 사용했으며 무언가를 삽입하려고 하면 오류가 표시됩니다.
stack.push(0)
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
<ipython-input-23-c549502547a3> in <module>
----> 1 stack.push(0)
<ipython-input-21-dfbe390820f6> in push(self, x)
8
9 def push(self, x):
---> 10 self.storage[self.pointer] = x
11 print(f"New Stack: {self.storage}")
12 print(f"Pointer at {self.pointer+1}.\n")
IndexError: list assignment index out of range
이는 예상되는 것이지만 우리의 경우에는 오류가 조금 다르게 보이도록 해야 합니다.
class Stack:
def __init__ (self, size):
self.size = size
self.storage = ["~"]*size
self.pointer = 0
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer}.\n")
def push(self, x):
try:
self.storage[self.pointer] = x
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer+1}.\n")
self.pointer+=1
except IndexError as e:
print(f"Overflow Occured at pointer: {self.pointer}")
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)
for x in data:
stack.push(x)
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.
New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.
New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.
New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.
New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.
New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.
New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
Overflow Occured at pointer: 6
팝 작업
이제 스택이 완전히 채워졌으므로 스택에서 값을 제거하겠습니다. pop 연산은 포인터의 위치에 있는 데이터로 다시 작동합니다.
class Stack:
def __init__ (self, size):
self.size = size
self.storage = ["~"]*size
self.pointer = 0
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer}.\n")
def push(self, x):
try:
self.storage[self.pointer] = x
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer+1}.\n")
self.pointer+=1
except IndexError as e:
print(f"Overflow Occured at pointer: {self.pointer} \n")
def pop(self):
self.storage = self.storage[:-1]
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer-1}.\n")
self.pointer-=1
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)
for x in data:
stack.push(x)
stack.pop()
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.
New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.
New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.
New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.
New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.
New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.
New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
Overflow Occured at pointer: 6
New Stack: [4, 5, 6, 8, 5]
Pointer at 5.
이제 팝 작업을 수행했으므로 스택이 비어 있고 데이터를 제거하려고 하면 어떻게 됩니까? 그 경우가 스택 언더플로입니다. 그것도 쓰자.
for i in range(len(data)):
stack.pop()
New Stack: [4, 5, 6, 8]
Pointer at 4.
New Stack: [4, 5, 6]
Pointer at 3.
New Stack: [4, 5]
Pointer at 2.
New Stack: [4]
Pointer at 1.
New Stack: []
Pointer at 0.
New Stack: []
Pointer at -1.
New Stack: []
Pointer at -2.
위의 코드에서 포인터가 -ve가 될 때 오류가 표시되지 않습니다. 포인터가 이미 0이고 제거하려고 하면 오류라고 가정합니다.
class Stack:
def __init__ (self, size):
self.size = size
self.storage = ["~"]*size
self.pointer = 0
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer}.\n")
def push(self, x):
try:
self.storage[self.pointer] = x
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer+1}.\n")
self.pointer+=1
except IndexError as e:
print(f"Overflow Occured at pointer: {self.pointer} \n")
def pop(self):
if self.pointer<1:
print("Stack Underflow occured.")
else:
self.storage = self.storage[:-1]
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer-1}.\n")
self.pointer-=1
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)
for x in data:
stack.push(x)
stack.pop()
for i in range(len(data)):
stack.pop()
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.
New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.
New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.
New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.
New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.
New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.
New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
Overflow Occured at pointer: 6
New Stack: [4, 5, 6, 8, 5]
Pointer at 5.
New Stack: [4, 5, 6, 8]
Pointer at 4.
New Stack: [4, 5, 6]
Pointer at 3.
New Stack: [4, 5]
Pointer at 2.
New Stack: [4]
Pointer at 1.
New Stack: []
Pointer at 0.
Stack Underflow occured.
Stack Underflow occured.
이제 더 읽기 쉽게 만들기 위해 조금 더 조정합니다.
class Stack:
def __init__ (self, size):
self.size = size
self.storage = ["~"]*size
self.pointer = 0
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer}.\n")
def push(self, x):
print("=" * 20+" Push Operation "+"=" * 20)
try:
self.storage[self.pointer] = x
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer+1}.")
self.pointer+=1
except IndexError as e:
print(f"Overflow Occured at pointer: {self.pointer}")
print("="*55 + "\n")
def pop(self):
print("=" * 20+" Pop Operation "+"=" * 20)
if self.pointer<1:
print("Stack Underflow occured.")
else:
self.storage = self.storage[:-1]
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer-1}.")
self.pointer-=1
print("="*55 + "\n")
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)
for x in data:
stack.push(x)
stack.pop()
for i in range(len(data)):
stack.pop()
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.
==================== Push Operation ====================
New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
=======================================================
==================== Push Operation ====================
Overflow Occured at pointer: 6
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5, 6, 8, 5]
Pointer at 5.
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5, 6, 8]
Pointer at 4.
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5, 6]
Pointer at 3.
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5]
Pointer at 2.
=======================================================
==================== Pop Operation ====================
New Stack: [4]
Pointer at 1.
=======================================================
==================== Pop Operation ====================
New Stack: []
Pointer at 0.
=======================================================
==================== Pop Operation ====================
Stack Underflow occured.
=======================================================
==================== Pop Operation ====================
Stack Underflow occured.
=======================================================
탑 오퍼레이션
이것은 간단한 작업입니다. 현재 포인터가 가리키는 위치 아래에 있는 값을 제공합니다.
class Stack:
def __init__ (self, size):
self.size = size
self.storage = ["~"]*size
self.pointer = 0
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer}.\n")
def push(self, x):
print("=" * 20+" Push Operation "+"=" * 20)
try:
self.storage[self.pointer] = x
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer+1}.")
self.pointer+=1
except IndexError as e:
print(f"Overflow Occured at pointer: {self.pointer}")
print("="*55 + "\n")
def pop(self):
print("=" * 20+" Pop Operation "+"=" * 20)
if self.pointer<1:
print("Stack Underflow occured.")
else:
self.storage = self.storage[:-1]
print(f"New Stack: {self.storage}")
print(f"Pointer at {self.pointer-1}.")
self.pointer-=1
print("="*55 + "\n")
def top(self):
print("=" * 20+" Top Operation "+"=" * 20)
try:
print(f"Pointer at {self.pointer}.")
print(f"Return: {self.storage[self.pointer-1]}")
except:
print("Nothing on the top. Stack is empty.")
print("="*55 + "\n")
data = [4, 5, 6, 8, 5, 2, 0]
stack = Stack(size=6)
for x in data:
stack.push(x)
stack.top()
stack.pop()
for i in range(len(data)):
stack.pop()
stack.top()
New Stack: ['~', '~', '~', '~', '~', '~']
Pointer at 0.
==================== Push Operation ====================
New Stack: [4, '~', '~', '~', '~', '~']
Pointer at 1.
=======================================================
==================== Top Operation ====================
Pointer at 1.
Return: 4
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, '~', '~', '~', '~']
Pointer at 2.
=======================================================
==================== Top Operation ====================
Pointer at 2.
Return: 5
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, '~', '~', '~']
Pointer at 3.
=======================================================
==================== Top Operation ====================
Pointer at 3.
Return: 6
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, 8, '~', '~']
Pointer at 4.
=======================================================
==================== Top Operation ====================
Pointer at 4.
Return: 8
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, '~']
Pointer at 5.
=======================================================
==================== Top Operation ====================
Pointer at 5.
Return: 5
=======================================================
==================== Push Operation ====================
New Stack: [4, 5, 6, 8, 5, 2]
Pointer at 6.
=======================================================
==================== Top Operation ====================
Pointer at 6.
Return: 2
=======================================================
==================== Push Operation ====================
Overflow Occured at pointer: 6
=======================================================
==================== Top Operation ====================
Pointer at 6.
Return: 2
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5, 6, 8, 5]
Pointer at 5.
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5, 6, 8]
Pointer at 4.
=======================================================
==================== Top Operation ====================
Pointer at 4.
Return: 8
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5, 6]
Pointer at 3.
=======================================================
==================== Top Operation ====================
Pointer at 3.
Return: 6
=======================================================
==================== Pop Operation ====================
New Stack: [4, 5]
Pointer at 2.
=======================================================
==================== Top Operation ====================
Pointer at 2.
Return: 5
=======================================================
==================== Pop Operation ====================
New Stack: [4]
Pointer at 1.
=======================================================
==================== Top Operation ====================
Pointer at 1.
Return: 4
=======================================================
==================== Pop Operation ====================
New Stack: []
Pointer at 0.
=======================================================
==================== Top Operation ====================
Pointer at 0.
Nothing on the top. Stack is empty.
=======================================================
==================== Pop Operation ====================
Stack Underflow occured.
=======================================================
==================== Top Operation ====================
Pointer at 0.
Nothing on the top. Stack is empty.
=======================================================
==================== Pop Operation ====================
Stack Underflow occured.
=======================================================
==================== Top Operation ====================
Pointer at 0.
Nothing on the top. Stack is empty.
=======================================================
결론
이 블로그를 끝까지 읽어주셔서 감사합니다. 다음 블로그에서는 Queue에 대한 유사한 접근 방식을 공유할 것이며 시도하는 것도 재미있을 것입니다.
Reference
이 문제에 관하여(Python에서 스택 데이터 유형 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/iamdurga/making-a-stack-data-type-in-python-2lci텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
