자료구조(3) - Stack

자료구조(3) - Stack

Stack

Stack

< 개념 >

Stack : List의 자료구조와 비슷하며 데이터를 정렬할 때 사용하기보단 FILO (First In, Last Out)를 활용한 문제가 있을 때 사용된다. 구조는 위의 그림처럼 아래가 막혀 있는 바구니를 생각하면된다.

위의 그림처럼 색깔 순으로 Stack에 넣는다면

처음부터 넣은 남색부터 데이터가 쌓이고 마지막으로 보라색이 넣어진다.

나올때는 반대로 마지막에 넣었던 보라색부터 나오고 맨처음 들어간 남색이 마지막에 나오므로 First In Last Out이 된다.

<특징>

FILO ( First In Last Out )

넣은 순서를 기억해야 하는 알고리즘 문제 풀 때 유용 Ex) 되돌리기기능, 짝맞추기 기능 등등

<구현>

#Stack 기본메소드

Stack 메소드 설명 Return Push (value) Value 값을 Node에 담아 Stack에 추가함 True / Fasle pop () Staack의 맨 위의 값을 꺼냄 value peek () Stack의 맨 위의 데이터를 확인함 value is_empty() Stack이 비웠는지 확인함 True / False

<구현 과정1 - Linked List 이용>

Push(value) : LinkedList 의 head에 새로운 노드 추가 한다

1. New Node 생성

2. 새로운 노드의 next를 현재 head로 지정

3. head를 새로운 노드로 재 지정

Pop() : LinkedList의 head를 출력한다.

1. head노드를 따로 저장

2. head를 저장한 노드의 next로 지정

3. 저장한 노드의 next를 제거

4. 저장한 노드 Return

* Stack이 비였을 경우 는 Head가 없기 때문에 예외처리를 해야함 (is_empty()함수 이용)

Peek() : LinkedList의 head 대이터를 조회한다

*Stack이 비였을 경우 는 Head가 없기 때문에 예외처리를 해야함 (is_empty()함수 이용)

is_empty() : LinkedList의 head데이터의 유무를 판단

#python Code - Stack by Linked List

class Node: # LinkedList를 이용한 Stack def __init__(self, data): self.data = data # data : data를 담을 부분 self.next = None # next : 다음 노드를 가리킴 class Stack: def __init__(self): # Stack 정의 self.head = None # head : 처음 head 지정 def push(self, value): # push() : Stack에 데이터 넣기 new_node = Node(value) new_node.next = self.head self.head = new_node return print('성공!') def pop(self): # pop() : Stack에서 데이터 꺼내기 if self.is_empty(): return "Stack is Empty" curr = self.head self.head = self.head.next curr.next = None return curr def peek(self): # peek() : Staack의 가장 윗 부분 데이터 엿보기 if self.is_empty(): return 'Stack is Empty' return self.head.data # isEmpty 기능 구현 # isEmpty() : Stack이 비였는지 확인 def is_empty(self): return self.head is None

<구현 과정2 - List 이용>

Stack를 간단히 구현을 하려면 python의 내장 함수인 List를 이용해도 좋다.

각 기능을 보여주려고 class를 정의하였지만 사실은 그냥 다음과 같이 대체하여 사용하면된다.

#list = '리스트를 정의한 변수

push() -> append()

pop() -> pop()

peek() -> list[0]

is_empty -> len(list) == 0

#python Code - Stack by List

class Stack: # list를 이용한 Stack def __init__(self): self.items = [] def push(self, value): self.items.append(value) return True def pop(self): return self.items.pop() def peek(self): return self.items[0] def is_empty(self): return len(self.items) == 0

Stack을 이용한 문제

추후 연결에정!

from http://zhqmfkv.tistory.com/33 by ccl(A) rewrite - 2021-12-17 17:00:53