[자료구조] 4. 스택(Stack)이란? / 연산, 구현방법
[python] python의 self와 init의 이해
스택이란?
자료구조.
쌓아놓은 더미를 뜻하며, 아래부터 위까지 층층이 쌓인 구조.
후입 선출(LIFO: Last-In First-Out)
가장 최근에 들어온 데이터가 가장 먼저 나감.
상자에 물건을 쌓아놓으면 가장 위에 것부터 가져가는 이치.
큐(Queue)는 들어온 데이터가 먼저 나가는 선형 구조.
! 스택 vs 리스트 vs 큐
리스트 : 어느 곳에서나 읽기, 삽입, 삭제 가능.
스택 : 리스트의 한쪽에서만 삽입, 삭제.
큐 : 삽입을 한쪽에, 삭제는 반대쪽에서.
스택의 구조와 사용
undo 등 되돌리기 시 가장 최근 작업을 취소하는 등에 사용.
상단(stack top) : 스택에서 입출력이 이루어지는 부분
하단(stack bottom): 반대쪽 바닥 부분
요소(element): 스택에 저장되는 것
공백 스택(empty stack): 공백 상태의 스택
포화 스택(full stack): 포화 상태의 스택
시스템 스택 함수 호출
시스템 스택이란, 운영 체제가 사용하는 스택을 가리킴.
함수를 실행하면 자신이 호출한 함수로 되돌아가는데,
이 때 스택으로 복귀할 주소를 기억해둠.
! 활성 레코드(activation record)
시스템 스택에 함수가 호출 될때마다 활성 레코드가 만들어짐.
이 곳에 복귀주소가 저장됨.
(그러니까, 함수 자체를 시스템 스택란에 쌓아서 넣어놓았다가 비워놓는 식으로 메모리를 쓰는데, 이러한 순간 순간 함수들이 호출될 때 생겼다 사라지는 걸 활성 레코드라고 함.)
(a에서 b로 간 다음 b에서 a로 돌아가려면 a로 돌아가는 길을 그때그때 기억해두는 거라고 생각하면 됨.)
복귀주소(return address), 프로그램 카운터(PC), 매개변수, 함수 안에서 선언된 지역 변수가 생성됨.
스택 추상 자료형
스택(Stack)은 후입선출(LIFO)의 접근방법을 유지하는 0개 이상의 요소를 지닌 선형 리스트의 일종.
1) 스택 ADT
-
init()
스택 초기화 -
create()
스택 생성 -
is_empty()
스택이 비어있는지 검사 -
is_full(s)
스택이 가득 찼는지 검사 -
push(e)
스택의 맨위에 요소 e 추가 -
pop()
스택 맨 위 요소를 가져오면서 삭제. -
peek()
스택 맨위 요소를 삭제하지 않고 반환
! ADT : 데이터 타입의 연산을 명시하되 구현을 명시하지 않음.
스택 연산
-
top()
스택 맨 위에 있는 데이터 값 반환 -
isempty()
스택에 원소가 있으면 True -
isfull()
스택에 원소가 없으면 False
정적/동적 구현
- 정적 구현 : 1차원 배열
stack[0] ... [top] 순으로 저장.
공백 상태 : top = -1
? 파이썬에서는 스택 어떻게 정의하지?
- 동적 구현 : 연결리스트 사용.
크기가 제한되지 않으나, 구현이 복잡하고, 삽입, 삭제가 오래 걸림.
...
연결 리스트
노드마다 값과 다음 노드 주소를 저장함.
연결 리스트에서는 head가 첫째 노드 주소를 가리킴.
class Node:
def __init__(self, data):
self.data = data #data는 값을 가리키는 변수(속성, attribute)
self.next = None #next는 다음 노드를 가리키는 변수
아.
클래스.dd 자체는 클래스 내에 dd라는 함수를 정의하는 과정임.
self.data = data 라고 하면 .data를 붙이면 할당된 데이터 값을 불러오겠다는 말임.
일단 함수 정의시 def와 class가 있다.
- 클래스 구성 요소.
글로벌 변수를 없애고, 모든 변수를 어떠한 스코프에 소속.
몇번이고 재사용 가능.
함수 실행 중 자신을 다시 호출하는 처리 가능.
def some_function(something):
print(something)class SomeClass:
def __init__(self,something):
self.something = something
def some_function(self):
print(self.something)실제 클래스를 사용하기 위해서는 인스턴스 생성 필요.
그러니까 바로 함수 명을 적으면 쓸 수 있는게 아니라,
어떤 변수에 할당 되고 나서야 그것의 부가 요소 호출하는 느낌.
a = SomeClass("some_value")
class SomeClass:
def __init__(self,something):
self.something = something
def some_function(self):
print(self.something)
a = SomeClass("some_value")
a.some_function()
#함수에서 print 내장함수를 사용하고 있으므로 some_value가 리턴된다.
클래스 내 다른 함수를 기재할 수 있고, 그걸 method라고 한다.
class some_class:
def __init__(self,something):
self.something = something
def some_function1(self):#메소드1
print(self.something)
def some_function2(self):#메소드2
return self.something
_init__ 의 이해
constructor의 일종. 초기화를 위한 함수.
인스턴스화 실시할때 처음 호출 됨.
데이터 초기 시점의 함수.
첫번째 인수는 반드시 self.
이것으로 인스턴스 변수를 메소드 내에서 작성, 참고가 가능해진다.
class MyStatus:
def __init__(self,age,name,height,weight):
self.age = age
self.name = name
self.height = height
self.weight = weight
def print_name(self):
print(self.name)
def print_age(self):
print(self.age)
def print_height(self):
print(self.height)
def print_weight(self):
print(self.weight)
a = MyStatus(34,"yamada",170,78)다시 돌아가서,
연결 리스트 만들기
class Node:
def __init__(self,data):
self.data = data
self.next = None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)...
음.
1은 그대로 넣었으니 data만 있어요.
head.next로 1의 빈자리에 2 노드를 넣어놨어요.
2에게도 있을 next에 3을 넣어놨어요...
모두 출력하는 법
: head 자체는 멈춰놓고,
추적하면서 하나씩 출력하면 되므로,
head의 값을 변수로 저장해놓고,
None이 올때까지 출력.
node = head
while node: #node is not None과 같은 코드
print(node.data, end = " ")
node = node.next
연결 리스트 끝에 새 노드 추가하기.
맨 끝에 none이 나오면 거기에 새 노드를 할당한다.
while문을 끝내기 위해 node 한칸 더 가준다.
node = head
while node:
if node.next is None:
node.next = Node(4)
break
node = node.next처음에 새 노드 추가하기
- 새 노드 만듦.
- 새 노드의 next에 head로 썼던 값 달아줆.
- 만든 노드에 head 할당.
node = Node(0)
node.next = head
head = node
길다.....
.....
스택 함수 쓰는 걸로 넘어가겠다
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, data):
if self.top is None:
self.top = Node(data)
else:
node = Node(data)
node.next = self.top
self.top = node
def pop(self):
if self.top is None:
return None
node = self.top
self.top = self.top.next
return node.data
def peek(self):
if self.top is None:
return None
return self.top.data
def is_empty(self):
return self.top is None
if __name__ == "__main__":
s = Stack()
for i in range(3):
s.push(chr(ord("A") + i))
print(f"Push data = {s.peek()}")
print()
while not s.is_empty():
print(f"Pop data = {s.pop()}")
print()
print(f"Peek data = {s.peek()}")
(근데 이거....)
(스택 쓰려고할때마다 클래스 넣어줘야하는 거겠지? 후..)
