자료구조 #3 Stack(스택)

자료구조는 컴퓨터내의 데이터들을 효율적으로 저장하고 사용하는 방법들이다.

Stack ADT(Abstract Data Type)

여기서 ADT란 자료구조의 실제 구현 방법을 설명하지 않고 간단히 자료 구조가 어떤 features와 operations을 가지고 있는지 나타내는 타입이다.

• 실생활에서 쉽게 스택하면 떠올릴 수 있는 것들이 책쌓기, 접시쌓기이다. 제일 위에 있는 책이나 접시만 접근 가능하고 제일 윗부분에서만 책을 새로 넣거나 뺄 수 있다.
• Last-In-First-Out (LIFO)
• 스택은 Top 이라고 부르는 한쪽 끝에서만 데이터를 삽입, 삭제할 수 있는 제한된 리스트

Operations

(1) Push(x)
- 데이터를 Top에 삽입
(2) Pop(x)
- Top에 있는 데이터를 뽑기 (삭제)
(3) Top(x)
- Top 에 있는 값 확인
(4) IsEmpty(x)
- list가 Empty 인지 확인

=> Stack 은 element의 삽입, 삭제가 시간 복잡도 Constant Time or O(1) 으로 가능하다.

Applications

• Function Calls/ Recursion
• Undo in an editor
• Balanced Parenthese { ( ) }

Implementaion of Stacks

스택은 Array, Linked list 로 구현할 수 있다. 파이썬에서는 array가 없고 list가 내장 객체로 있기 때문에 List, Linked list로 구현가능하다.

(1) List

class Stack:
	def __init__(self):
    	self.container == list()
    
    def push(self, data):
    	self.container.append(data) # append는 list에 데이터 추가하는 메소드 
        
    def pop(self, data):
    	self.container.pop() # python list가 pop 기능 제공
    
    def is_empty(self): # list가 비었는지 확인 
    	if not self:
        	return True
        else:
        	return False
            
    def peek(self): # Top 데이터 확인
    	return self.container[-1] # 리스트의 마지막 요소의 인덱스는 -1
        
if __name__ == "__main__":
    	s = Stack()
        s.push(1)
        s.push(2)
        s.push(3) 
        
        while s:
        data = s.pop()
        print(data, end=' ') # 3 2 1 
        
    

(2) Linked list

파이썬에서 Linked list는 Node 클래스를 생성하여 구현할 수 있다. (Linked list 는 노드들이 연결된 구조인데 노드에는 데이터와 다음 노드의 주소값이 저장된다, 제일 마지막 노드의 주소값 자리에는 None이 저장된다. )

linked list의 경우 Node를 삽입 할때, 첫 엘리먼트에 Node를 삽입할 때는 시간 복잡도가 O(1) 이지만, 제일 마지막 노드에 새 Node를 삽입하기 위해서는 첫번째 엘리먼트부터 그다음 엘리먼트.... n-1번째 엘리먼트까지 이동한 후 새로 Node를 추가해야하기 때문에 O(N)이 소요된다. 그러므로 Linked list는 제일 앞 노드(TOP)에서 데이터가 추가되고 삭제된다.

class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None
        
class Stack: 
	def __init__(self):
    	self.head = None 
        
    def is_empty(self):
    	if not self.head:
        	return True
        return False
        
    def push(self, data):
    	new_node = Node(data)
        
        new_node.next = self.head
        self.head = new_node

push 함수

먼저 새 노드의 next를 현재 head로 대입 후 같은 값을 가리키게 하고, self.head = new_node 로 지정하여 새로운 Node로 head 값 변경

    def pop(self):
    	if self.is_empty():
        	return None
            
        ret_data = self.head.data
        self.head = self.head.next
        return ret_data 

head가 가리키고 있는 값의 data를 ret_data 에 저장 후, head 를 head가 가리키고 있는 노드의 next 를 대입하여 head를 변경

head는 Node 인가 ? 아니면 첫번째 element의 주소값을 저장해놓은 곳인가 ?
self.head.next : Node가 아닌데 .next를 사용할 수 있나 ? 아니면 head가 첫 엘리먼트를 가리키고 있기 때문에 첫엘리먼트의 next까지 접근이 가능한 건가 ??

    def peek(self,data):
    	if self.is_empty():
        	return None
            
        return self.head.data
        
    if __name__ == '__main__':
    	s = Stack()
        
        print(s.is_empty())
        
        s.push(1)
        s.push(2)
        s.push(3)
        
        print("peek of data : {}".format(s.peek)))
        
        while not s.is_empty():
        	print(s.pop()) # 3 2 1