누구나 자료구조와 알고리즘 - (8) 스택과 큐

 

 

 

 

 

스택(stack)

1.1. 정의

스택이 데이터를 저장하는 방법은 배열과 같으며 단순히 원소들의 리스트이다.

스택 연산을 묘사하는 데 쓰이는 유용한 두문자어가 LIFO(Last In, First Out)이다.

 

스택은 다음과 같은 세 가지 제약이 있다.

• 데이터는 스택의 끝에만 삽입할 수 있다.
• 데이터는 스택의 끝에서만 삭제할 수 있다.
• 스택의 마지막 원소만 읽을 수 있다.

접시 더미나 수직으로 놓인 배열로 묘사하여 생각해보자.

 

 

1.2. 용어

• 푸시(push): 스택에 값을 추가하는 것
• 팝(pop): 스택의 위에서 원소를 제거하는 것

예를 들어, 대괄호와 중괄호가 잘 닫혔는지 확인하는 linter를 구현한다고 쳐보자.

"var a = { y: [1, 2, 3] }"라는 문장을 처리할 때 각 여는 괄호를 만날 때 마다 stack에 push하고 닫는 괄호를 만날 때 마다 stack을 pop하며 pop한 괄호의 종류가 일치하는지 확인하여 일치하지 않을 때 오류를 뱉어내면 된다.

 

 

 

 

큐(queue)

1.1. 정의

큐 또한 임시데이터를 처리하기 위해 디자인된 데이터 구조다.

큐 연산을 묘사하는 데 쓰이는 유용한 두문자어가 LIFO(First In, Last Out)이다.

 

큐는 다음과 같은 세 가지 제약이 있다.

• 데이터는 큐의 끝에만 삽입할 수 있다.
• 데이터는 큐의 앞에서만 삭제할 수 있다.
• 큐의 앞에 있는 원소만 읽을 수 있다.

 

1.2. 용어

• 인큐(enqueue): 큐에 값을 추가하는 것
• 디큐(dequeue): 큐에서 값을 삭제하는 것

 

 

 

 

제약을 갖는 데이터 구조의 중요성

스택과 큐는 실용적인 알고리즘을 간결하게 처리할 수 있는 프로그래머의 도구이다.

스택이 하는 일은 배열도 할 수 있으나 배열과 달리 제약을 갖는 데이터 구조가 주는 이점이 있다.

 

1. 제약을 갖는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있다.

린팅 알고리즘은 스택의 위에서 항목을 제거하는 경우에만 동작한다. 스택 위 항목을 제외하고는 삭제할 수 없다.

 

2. 스택 같은 데이터 구조는 문제를 해결하는 새로운 사고 모델을 제공한다.

수택은 후입 선출 프로세스에 대한 전반적인 아이디어를 제공한다. LIFO 사고방식에 입각해 린터 같은 종류의 문제를 풀 수 있다.

 

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.