[자료구조/알고리즘]선형 자료구조

김지현·2021년 7월 9일

자료구조&알고리즘

자료구조/알고리즘

목록 보기

4/5

선형 자료 구조(Linear)

선형 자료 구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것
배열, 리스트, 스택, 큐

⌨랜덤 접근 불가능

모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조

✔ Stack

📌 스택(Stack)의 특징

스택은 데이터에 접근,삭제 시 top으로 정한 곳을 통해서 접근, 삭제 해야한다.
Last-In First-Out(LIFO), 후입선출
즉, 먼저 들어간 자료가 나중에 나오는 자료구조
데이터 삽입하는 push, 데이터 삭제하는 pop,top에 위치한 데이터를 확인하는 peek, 스택이 비었는지 확인하는 isEmpty가 있다

아래 코드는 가장 기본적인 스택의 구현으로 C언어 기준이다.

#define STACK_SIZE 500
int arr[STACK_SIZE]; //스택의 최대 크기는 500
int top = 0; //스택의 현재 크기는 0

int push(int n)
{
    if (top>=STACK_SIZE) return -1;
    arr[top++] = n;
    return 0;
}
int pop()
{
    if (top<=0) return -1;
    return arr[--top];
}

파이썬 기준으로 살펴보자

class stack:
	def __init__(self):
		self.items = []
      #비어있는지 확인
	def isEmpty(self):
		return self.items == []
      #데이터 삽입
	def push(self, item):
		self.items.append(item)
      #top 원소 확인
	def peek(self):
		return self.items[-1]

	def size(self):
		return len(self.items)
        
      #데이터 삭제
	def pop(self):
		return self.items.pop()

📌 스택의 활용

LIFO를 활용하여 여러 분야에서 활용 가능
웹 브라우저 방문기록 : 가장 나중에 열린 페이지부터 다시 보여준다.
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
실행 취소 : 가장 나중에 실행된 것부터 실행을 취소한다.

✔ Queue

📌 큐(Queue)의 특징

First-In First-Out(FIFO), 선입선출
입출력이 양방향에서 이루어짐
즉, 먼저 들어간 자료가 먼저 나오는 자료구조
큐의 rear에서 이루어지는 데이터 삽입 연산 Enqueue/ front에서 이루어지는 데이터 삭제 연산 Dequeue
삭제 연산만 수행되는 곳을 Front, 삽입 연산만 이루어지는 곳을 Rear
큐의 가장 첫 원소를 front, 가장 끝 원소를 rear

class queue:
	def __init__(self):
		self.items = []

	def enqueue(self, item):
		self.items.insert(0, item)

	def dequeue(self):
		return self.items.pop()

	def isEmpty(self):
		return self.items == []

	def size(self):
		return len(self.items)