자료구조 - 스택, 후위표기법, 큐를 사용하여 덱을 구현하는 방법

 

자료구조 - 스택, 후위표기법, 큐를 사용하여 덱을 구현하는 방법

 

 

 

자료구조와 관련된 스택(Stack), 후입선출 

 

스택(Stack)은 후입선출(Last-In-First-Out, LIFO) 방식으로 동작하는 자료구조입니다. 새로운 요소는 스택의 상단에 삽입되며, 가장 최근에 삽입된 요소가 가장 먼저 제거됩니다. 이것은 스택의 작동 방식으로 "Last-In-First-Out" 이라고 불리는 이유입니다. 스택은 일반적으로 스택 상단(top)으로만 접근할 수 있습니다. 요소를 추가하는 작업은 스택의 상단에 새로운 요소를 삽입하는 작업이며, 요소를 제거하는 작업은 스택의 상단에서 요소를 꺼내는 작업입니다.

 

 

스택은 주로 함수 호출 스택(function call stack)이나 뒤로 가기 버튼 등에 사용됩니다. 함수 호출 스택에서는 함수가 호출될 때마다 스택에 새로운 프레임(frame)이 추가되고, 함수 호출이 완료되면 해당 프레임이 제거됩니다. 이것은 중첩 함수 호출과 함수 호출의 반환을 관리하는 데 유용합니다. 스택은 또한 반복 알고리즘에서 재귀적(recursive) 함수를 호출하는 데 사용됩니다. 재귀 함수는 자기 자신을 반복적으로 호출하여 문제를 해결합니다. 이때 스택을 사용하면, 함수 호출을 효율적으로 관리할 수 있습니다.

 

 

스택은 다른 자료구조와 함께 사용될 때도 매우 유용합니다. 예를 들어, 스택과 큐(Queue)를 함께 사용하여 덱(Deque)을 구현할 수 있습니다. 스택은 또한 수식을 계산하는 데도 사용됩니다. 후위 표기법(Postfix Notation)으로 작성된 수식은 스택을 사용하여 계산할 수 있습니다. 스택은 프로그래밍에서 매우 중요한 자료구조 중 하나입니다. 이것은 함수 호출 스택이나 재귀 함수 등의 구현에 널리 사용되기 때문입니다. 스택을 이해하면, 다른 자료구조에 대한 이해도 쉽게 높일 수 있습니다.

 

 

반응형

 

후위 표기법(Postfix Notation)으로 작성된 수식을 스택을 사용하여 계산하는 방식

 

후위 표기법은 연산자를 피연산자 뒤에 적는 방식으로 수식을 작성하는 표기법입니다. 예를 들어, 중위 표기법(Infix Notation)으로 작성된 "3 + 4"와 같은 수식을 후위 표기법으로 작성하면 "3 4 +"와 같습니다. 후위 표기법으로 작성된 수식을 계산하기 위해서는 스택을 사용할 수 있습니다. 계산 알고리즘은 다음과 같습니다.

 

1. 표기법에서 한 항목을 읽어들인다.
2. 항목이 피연산자인 경우, 스택에 추가한다.
3. 항목이 연산자인 경우, 스택에서 피연산자 두 개를 제거한 후, 해당 연산자로 계산한 결과를 스택에 추가한다.
4. 표기법을 모두 읽을 때까지 위 과정을 반복한다.
5. 스택에 남은 마지막 요소가 수식의 결과값이 된다.

 

예를 들어, "3 4 +"라는 후위 표기법으로 작성된 수식을 계산하려면, 스택에 3과 4를 차례대로 추가한 후, "+" 연산자를 만나면 스택에서 4와 3을 제거하여 3 + 4 = 7의 결과를 스택에 추가합니다. 이렇게 스택을 사용하여 계산할 수 있습니다. 후위 표기법은 계산기에서 수식을 입력하는 방식으로 자주 사용되며, 스택을 사용하여 계산하는 방법은 프로그래밍에서도 자주 사용됩니다. 이 방법은 중위 표기법으로 작성된 수식을 계산하는 것보다 좀 더 간단하고 직관적이며, 수식을 계산하기 위한 중간 과정이 없어서 계산 속도가 빠릅니다.

 

 

 

스택과 큐(Queue)를 함께 사용하여 덱(Deque)을 구현하는 방법

 

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조입니다. 스택과 큐를 함께 사용하여 덱을 구현할 수 있습니다. 덱을 구현하기 위해서는 두 개의 스택과 큐를 사용합니다. 한 쪽 끝에서의 삽입과 삭제는 스택을 사용하고, 다른 쪽 끝에서의 삽입과 삭제는 큐를 사용합니다. 덱의 구현 방법은 다음과 같습니다.

 

1. 두 개의 스택(stack1, stack2)과 큐(queue)를 생성합니다.
2. 덱의 왼쪽 끝에서의 삽입은 stack1을 사용하여 push 연산을 수행합니다.
3. 덱의 오른쪽 끝에서의 삽입은 큐(queue)를 사용하여 enqueue 연산을 수행합니다.
4. 덱의 왼쪽 끝에서의 삭제는 stack1에서 pop 연산을 수행합니다. 
   만약 stack1이 비어있으면, stack2에서 pop 연산을 수행하여 stack1으로 옮긴 후 pop을 수행합니다.
5. 덱의 오른쪽 끝에서의 삭제는 큐(queue)에서 dequeue 연산을 수행합니다.
   만약 stack2가 비어있으면, stack1에서 모든 요소를 pop하여 stack2으로 옮긴 후 dequeue를 수행합니다.
6. 덱의 왼쪽 끝에서의 조회는 stack1에서 top 연산을 수행합니다.
   만약 stack1이 비어있으면, stack2에서 모든 요소를 pop하여 stack1으로 옮긴 후 top을 수행합니다.
7. 덱의 오른쪽 끝에서의 조회는 큐(queue)에서 peek 연산을 수행합니다.
   만약 stack2가 비어있으면, stack1에서 모든 요소를 pop하여 stack2으로 옮긴 후 peek을 수행합니다.

 

이렇게 두 개의 스택과 큐를 조합하여 덱을 구현할 수 있습니다. 이 구현 방법은 스택과 큐의 특성을 활용하여 빠르고 간단하게 덱을 구현할 수 있으며, 스택과 큐를 모두 사용하기 때문에 다양한 연산을 지원할 수 있습니다.