[자료구조] 순차적 자료구조

순차적 자료구조 (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)

 

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