데이터 구조는 데이터 값, 이들 간의 관계 및 데이터에 적용 할 수있는 함수 또는 작업의 모음입니다. 이제 많은 데이터 구조를 사용할 수 있습니다. 하지만 오늘은 스택 데이터 구조에 초점을 맞출 것입니다. 다음 주제에 대해 논의 할 것입니다.
왜 데이터 구조인가?
이에 답하려면 큰 수준에서 생각해야합니다. Google지도가 몇 초 만에 최적의 경로를 표시하는 방법과 마이크로 초 단위로 검색 결과를 반환하는 방법을 생각해보십시오. 100 개의 웹 사이트 만 다루는 것이 아니라 10 억 개 이상의 사이트를 다루며 결과를 너무 빨리 보여줍니다.
사용 된 알고리즘이 중요한 역할을하지만 사용 된 데이터 구조 또는 컨테이너가 해당 알고리즘의 기반입니다. 모든 애플리케이션에서 데이터를 사용에 가장 적합한 방식 또는 구조로 구성하고 저장하는 것은 데이터의 효율적인 액세스 및 처리를위한 핵심입니다.
데이터 구조의 유형
데이터 작업을 효율적으로 수행하는 데 사용할 수있는 몇 가지 표준 데이터 구조가 있습니다. 응용 프로그램에 맞게 사용자 정의하거나 완전히 새로운 것을 구축 할 수도 있습니다.
스택 데이터 구조 란?
실제 사례를 고려하십시오.
- 화물 운송
- 쟁반에 접시
- 동전 스택
- 서랍 스택
- 철도 야드에서 열차 분로
이러한 모든 예는 후입 선출법 전략. 쟁반 위의 접시를 고려하십시오. 접시를 선택하려면 상단에서 접시를 선택해야하는 반면 접시가 쟁반에 보관 된 경우 역순이어야합니다. 다음 예제 위의 후입 선출 (LIFO) 원리는 스택 .
보완 작업과 별도로 스택에서 가능한 주요 작업은 다음과 같습니다.
- 스택 맨 위에 요소를 밀거나 삽입
- 스택 상단에서 요소 팝 또는 제거
스택 데이터 구조 생성
class Stack : def __init __ (self, max_size) : self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size 스택에서 예상되는 최대 요소 수입니다.
- 스택의 요소는 파이썬 목록에 저장됩니다.
- Top은 빈 스택을 표시하기 위해 처음에 -1을 취하는 스택의 최상위 인덱스를 나타냅니다.
스택의 초기 상태는 그림에서 볼 수 있습니다. 여기서 max_size = 5
스택에 요소 푸시
이제 스택에 요소를 입력하거나 푸시하려면 다음 사항을 기억해야합니다.
- 상단은 요소가 삽입 될 인덱스를 가리 킵니다.
- 스택이 가득 차면 즉 max_size = top 일 때 요소가 삽입되지 않습니다.
그래서 알고리즘은 무엇입니까 ??
# 스택의 최대 크기를 반환합니다. def get_max_size (self) : return self .__ max_size # 스택이 가득 찼는 지 여부에 관계없이 bool 값을 반환하고, 가득 차면 True이고 그렇지 않으면 False를 반환합니다. def is_full (self) : return self.get_max_size ()-1 == self .__ top # 스택 맨 위에 요소를 푸시합니다 .def push (self, data) : if (self.is_full ()) : print ( 'stack is already full') else : self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # def __str __ (self)를 디버깅하는 동안 DS 객체의 요소를 인쇄하려면 아래 __str __ ()을 사용할 수 있습니다. msg = [] index = self .__ top while (index> = 0) : msg.append ((str) (self .__ elements [index])) index- = 1 msg = ''.join (msg) msg = 'Stack data (Top to Bottom) :'+ msg return msg
이제 다음을 실행할 때 :
stack1 = 스택 (4)
# 필수 요소를 모두 누르십시오.
stack1.push ( 'A')
stack1.push ( 'B')
stack1.push ( 'C')
stack1.push ( 'E')
print (stack1.is_full ())
인쇄 (스택 1)
산출:
스택이 이미 가득 찼습니다
진실
스택 데이터 (위에서 아래로) : D C B A
자바 명령 줄 인수 예
스택에서 팝 요소
이제 스택에 요소를 삽입 했으므로 요소를 팝하려고하므로 다음을 처리해야합니다.
- 스택이 비어 있지 않습니다. 즉, top! = -1
- 데이터를 삭제할 때 맨 위는 스택의 이전 맨 위를 가리켜 야합니다.
그래서 알고리즘은 무엇입니까 ??
# 스택이 비어 있는지 여부에 관계없이 bool 값을 반환하고, 비어 있으면 True, 그렇지 않으면 False를 반환합니다. def is_empty (self) : return self .__ top ==-1 # 팝된 값 반환 def pop (self) : if (self.is_empty ()) : print ( 'Nothing to pop, already empty') else : a = self .__ elements [self .__ top] self .__ top = self .__ top-1 return a #display 모든 스택 요소를 위에서 아래로 def display (self) : for i in range (self .__ top, -1, -1) : print (self .__ elements [i], end = '') print ()
이제 이전에 생성 된 스택을 고려하여 요소를 팝해보십시오.
print (stack1.pop ())
print (stack1.pop ())
인쇄 (스택 1)
print (stack1.pop ())
print (stack1.pop ())
print (stack1.pop ())
산출:
디
씨
스택 데이터 (위에서 아래로) : B A
비
에
터질 게 없어, 이미 비어있어
스택 데이터 구조의 응용
- 예 1 :
스택은 산술 표현식 평가를위한 대괄호 일치 알고리즘을 구현하고 메서드 호출을 구현하는 데 사용됩니다.
답은 5입니다.
- 예 2 :
Windows의 클립 보드 두 스택을 사용하여 실행 취소-다시 실행 (ctrl + z, ctrl + y) 작업을 구현합니다. MS-Word, Notepad 등과 같은 Windows 워드 편집기에서 작업했을 것입니다. 다음은 MS-Word로 작성된 텍스트입니다. Ctrl-Z 및 Ctrl-Y를 클릭하면 텍스트가 어떻게 변경되었는지 관찰하십시오.
다음은 실행 취소-다시 실행 작업을 시뮬레이션하는 코드입니다. 코드를 살펴보고이 구현에서 스택이 어떻게 사용되는지 관찰하십시오.
# 클래스 스택 클래스 생성 Stack : def __init __ (self, max_size) : self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self) : if (self .__ top == self .__ max_size-1) : true 반환 False def is_empty (self) : if (self .__ top ==-1) : True 반환 False def push (self, data) : if (self.is_full ()) : print ( '스택이 꽉 찼습니다 !!') else : self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self) : if (self.is_empty ()) : print ( '스택이 비어 있습니다! ! ') else : data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self) : if (self.is_empty ()) : print ('The stack is empty ') else : index = self .__ top while (index> = 0) : print (self .__ elements [index]) index- = 1 def get_max_size (self) : return self .__ max_size # 아래 __str __ ()을 사용하여 디버깅 중 DS 객체 def __str __ (self) : msg = [] index = self .__ top while (index> = 0) : msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ='Stack data (Top to Bottom) : '+ msg return ms g # 제거 또는 백 스페이스 작업을 구현하는 함수 def remove () : 전역 클립 보드, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ( 'Remove :', clipboard) # 실행 취소 작업을 구현하는 기능 def undo () : globalclipboard, undo_stack, redo_stack if (undo_stack.is_empty ()) : print ( '실행 취소 할 데이터가 없습니다') else : data = undo_stack.pop () data) redo_stack.push (data) print ( 'Undo :', clipboard) # 다시 실행 작업을 구현하는 함수 def redo () : global 클립 보드, undo_stack, redo_stack if (redo_stack.is_empty ()) : print ( '데이터가 없습니다. 다시 실행하려면 ') else : data = redo_stack.pop () if (클립 보드에 데이터가 없습니다) : print ('다시 실행할 데이터가 없습니다 ') redo_stack.push (data) else : 클립 보드 .remove (데이터) undo_stack.push ( data) print ( '다시 실행 :', 클립 보드) 클립 보드 = [ 'A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = 스택 (len (clipboard)) remove () undo () redo ()산출:
제거 : [‘A’,‘B’,‘C’,‘D’,‘E’]
실행 취소 : [‘A’,‘B’,‘C’,‘D’,‘E’,‘F’]
다시 실행 : [‘A’,‘B’,‘C’,‘D’,‘E’]
이것으로 Python의 스택 데이터 구조 기사를 마칩니다. 성공적으로 코드를 이해하고 실행했다면 더 이상 Stacks Data Structure의 초보자가 아닙니다.
질문이 있으십니까? 이 기사의 댓글 섹션에 언급 해 주시면 가능한 한 빨리 연락 드리겠습니다.
다양한 응용 프로그램과 함께 Python에 대한 심층적 인 지식을 얻으려면 라이브에 등록 할 수 있습니다. 연중 무휴 지원 및 평생 액세스.