[자료구조] 순차적 자료구조
순차적 자료구조 (Sequential data structures)
순차적 자료구조에(Sequential data structures) 는 크게 총 3가지 있다.
1. 배열, 리스트
Index로 임의의 원소에 접근한다.
삽입 함수 append, insert 함수가 존재한다.
삭제 함수 pop( ), remove( ) 함수가 존재한다.
2. Stack, Queue, Deque
제한된 접근, 삽입 삭제만 허용한다.
Stack은 LIFO (last in first out)
Queue는 FIFO (first in first out)
Dequeue는 (stack+queue)
3. Linked list(연결 리스트)
자신의 값 + 다음값이 주소도 저장한다.
값들이 연속적이지 않은 memory 공간에 흩어져 있고 현재의 값에 대응값의 주소와 link 되어있어 다음 값을 알 수 있다.
인덱스로 접근이 불가능하다.
Stack 스택
순차적 자료구조에는 기본 연산으로 값의 저장, 삭제, 삽입, 탐색이 있다.
Stack은 LIFO 이므로 마지막으로 들어온 값이 가장 먼저 나가는 구조를 지닌다.
Stack을 python으로 구현해보면 다음과 같다.
Stack class를 정의해주면 빈 리스트를 생성해주고, 값을 push하게 되면 list에 val이 append되는 형태이다. 가장 나중에 들어온 값을 삭제해주는 pop( ) 함수를 사용하고, list 가장 위에있는 값을 return 해주는 top( ) 함수도 정의해준다.
class Stack():
def __init__(self):
self.items = []
def __len__(self):
return len(self.items)
def push(self,val):
self.items.append(val)
def pop(self):
try:
return self.items.pop()
except:
print('stack is empty')
def top(self):
try:
return self.items[-1]
except:
print('stack is empty')
Stack의 가장 기본적인 문제 하나를 풀어보자.
Q1) 괄호 짝 맞추기
입력값 : (())(
출력값 : False
입력값 : (2 + 5)*7 - ((3-1)/2+7)
출력값 : True
S = Stack()
parseq = '(2+5)*7-((3-1)/+7)'
for p in parseq:
if p == '(' :
S.push(p)
elif p == ')':
S.pop()
else:
continue
if len(S) > 0:
return False
else:
return True
값이 "(" 이면 Stack안으로 push 해주고, ")" 이면 pop()을 해준다.
( ) 짝이 맞으면 stack은 빈 stack이 되지만, 짝이 맞지 않는 경우 stack은 비어있지 않게 된다.
따라서 len(stack) 이 0보다 큰 값을 갖게되면 ( ) 짝이 맞지 않아 False를 return 해준다.
Queue 큐
FIFO ( first in first out ) 규칙의 순차적 자료구조이다.
| Stack | Queue | |
| insert | push | enqueue |
| delete | pop | dequeue |
Queue는 Stack과 달리 insert를 enqueue, delete 를 dequeue라고 칭한다.
FIFO 규칙을 가진 queue는 가장 먼저 들어간 값이 가장 먼저 나오는 규칙을 가지기 때문에 가장 먼저 들어간 값을 먼저 삭제하기 위해서는 front index에 대한 정보가 필요하다.
Queue를 python으로 구현해보면 다음과 같다.
class Queue():
def __init__(self):
self.items = [] # define empty list
self.front_idx = 0 # define front index
def enqueue(self,val): # value insert function
self.items.append(val)
def dequeue(self): # delte function
if self.front_idx == len(self.items):
print('Q is empty')
else:
x = self.items[front_idx]
self.front_idx +=1 # change front index
return x
Linked list 연결리스트
연결 리스트에는 한방향 연결리스트, 양방향 연결 리스트가 존재한다.
연결 리스트의 head node에는 head와 linked list의 size가 있고, node마다 key값과 다음 값의 주소 link 정보가 들어있다. 가장 마지막 node는 NULL과 link가 되어있다. 연결 리스트는 index 정보가 없어 n 번째 값을 알기 위해서 n번의 link를 타야하기 때문에 수행시간이 index에 따라 다르다.
우선 singleLinkedList (한방향 연결 리스트) 를 python으로 구현해보자. (주석 참고)
class Node():
def __init__(self, key = None, next = None):
self.key = key
self.next = next
def __str__(self):
return str(self.key)
class singlyLinkedList():
def __init__(self): # 연결리스트 정의
self.head = None
self.size = 0
def __len__(self): # 연결 리스트 길이
return self.size
def print_list(self): # 연결리스트 출력해주기
v = self.head
while(v):
print(v.key, "-> ", end ="")
v = v.next
print("None")
def pushFront(self, key): # 연결 리스트 맨 앞에 node 삽입
new_node = Node(key)
new_node.next = self.head # 기존 head를 new_node next 인자로 설정
self.head = new_node # new_node를 self.head로 정의
self.size +=1 # size 1 증가
def pushBack(self,key): # 연결 리스트 맨 끝에 node 삽입
new_node = Node(key)
if len(self) == 0: # 연결 리스트가 empty면 head 를 new_node로 정의
self.head = new_node
else:
tail = self.head
while tail.next != None: # tail까지 while문 돌리기
tail = tail.next
tail.next = new_node # tail의 next값으로 new_node 삽입
self.size +=1 # size 1 증가
def popFront(self): # 연결 리스트 맨 처음 node 삭제 / return 해당 node의 key 값
if len(self) ==0:
return None
else:
x = self.head
key = x.key
self.head = x.next # head값을 기존 head의 next 값으로 update 해준다.
self.size -= 1 # size 1 감소
del x
return key # 삭제한 해당 key return
def popBack(self): # 연결 리스트 맨 마지막 node 삭제 / return 해당 node의 key 값
if len(self) ==0:
return None
else:
prev = None
tail = self.head
while tail.next != None:
prev = tail # tail의 previous node
tail = tail.next
if len(self) ==1:
self.head = None
else:
prev.next = tail.next # tail의 prev값을 tail로 update
key = tail.key
del tail
self.size -=1
return key
def search(self,key): # key값이 저장된 노드를 리턴, 없다면 None
v = self.head
while v.key != None: # tail의 next값 None까지 while문 돌리기
if v.key == key: # 찾던 key값이 맞다면 v return
return v
else:
v = v.next
return None # key값이 연결 리스트에 없으면 None return
L = singlyLinkedList()
L.pushFront(1)
L.pushFront(9)
L.pushBack(4)
L.print_list()
L.popBack()
L.print_list()
print(L.search(9))
>>>
9 -> 1 -> 4 -> None
9 -> 1 -> None
9
reference : https://jjeongttakgoori.tistory.com/33?category=950412