데이터 구조 — 스택

프로그래밍에서 우리는 아주 많은 데이터로 작업해야 합니다. 따라서 효율적인 방식으로 데이터를 저장하고 구성해야 합니다. 이것은 데이터 구조가 유용할 때입니다. 데이터 구조를 사용하여 데이터를 저장, 구성, 처리 및 검색할 수 있습니다. 데이터 구조는 데이터 배열 방식에 따라 두 가지 범주로 더 나눌 수 있습니다.

이 기사에서는 선형 구조( Stacks ) 에 대해 이야기할 것입니다 . 비선형 구조에 비해 선형 구조의 개념은 비교적 이해하기 쉽습니다. 이러한 선형 구조의 몇 가지 예는 Stack, Queues, Deques 및 Lists입니다. 이러한 각 데이터 구조를 하나씩 살펴보겠습니다. 이러한 선형 구조는 2개의 끝이 있는 것으로 생각할 수 있습니다. (front & rear | left & right | top & bottom) 일부 선형 구조에서는 요소를 한쪽 끝에서만 삽입하거나 제거할 수 있지만 일부 구조에서는 양쪽 끝에서 모두 허용합니다.

1. 스택

• 따라서 기본적으로 스택은 항목의 삽입 및 제거가 동일한 끝에서 수행되는 정렬된 요소 모음입니다. 이 끝은 일반적으로 "상단"으로 알려져 있습니다. 또한 상단과 반대쪽 끝을 "하단"이라고 합니다.
• 또한 최신 항목은 위쪽에 있고 오래된 항목은 아래쪽에 있습니다. 따라서 스택에서 항목을 제거하는 순서는 항목을 스택에 삽입하는 순서의 역순입니다.
• 이제 스택의 동작을 잘 이해했으므로 스택 데이터 구조와 연결된 몇 가지 중요한 작업을 살펴보겠습니다.
• push (요소) — push 메서드는 항목을 스택의 맨 위에 삽입하는 데 사용됩니다.
• pop ()- pop 메서드는 스택에서 맨 위 항목을 제거하는 데 사용됩니다.
• peek () — Peek 메서드는 스택의 현재 최상위 항목을 보는 데 사용됩니다.
• size () — 스택에 있는 항목 수를 반환합니다.
• is_empty () — 이 메서드는 스택이 비어 있는지 여부를 확인하는 데 유용합니다.
• 여기서 목록의 끝은 스택의 맨 위로 간주됩니다. (시간 복잡도 — O(1)) 목록의 시작 부분이 스택의 맨 위에 있다고 생각할 수 있지만 항목을 푸시하거나 팝할 때 시간 복잡도가 O(n) 이 되기 때문에 그다지 효율적이지 않습니다 .
• 목록의 끝이 스택의 맨 위에 있다고 생각할 때


• 이제 스택을 구현하는 방법을 알았으므로 이제 스택 데이터 구조의 사용이 중요해지는 몇 가지 시나리오를 살펴보겠습니다.
• 숫자 체계 변환
• 먼저 스택을 사용하여 10진수를 2진수로 변환하는 방법을 살펴보겠습니다.

• 이제 위의 알고리즘을 확장하여 10진수를 2에서 16 사이의 숫자 시스템으로 변환해 보겠습니다.


거의 모든 프로그래밍 언어는 구문에 괄호를 사용합니다. 따라서 균형 잡힌 방식으로 괄호를 사용하지 않으면 구문 오류가 발생할 수 있습니다.

• 이 문제의 첫 번째 단계에서는 한 가지 유형의 괄호, 예를 들어 ()에 대해서만 고려할 것입니다. 우리가 확인해야 할 것은 괄호 집합이 균형을 이루고 있는지 여부입니다. 균형이 맞으면 true를 반환하고 그렇지 않으면 false를 반환해야 합니다.
• ( ) — 균형 잡힌 | ( ( ) ) — 균형 잡힌 | ( ( ( )( ) ) ) - 균형이 잡힌
• ( ( ) 균형이 맞지 않음 | ( ) ( ) ( — 균형이 맞지 않음 | ( ( ( ) ) ( ) — 균형이 맞지 않음

• ( [ ] ) — 균형 잡힌 | ( ( ) { } ) — 균형 잡힌 | ( ( [ { } [ ] ] ) ) - 균형이 잡힌
• ( ( ) 균형이 맞지 않음 | ( ) { } ]— 균형이 맞지 않음 | ( ( { } [ [ ) — 균형이 맞지 않음


3. 스택을 사용하여 문자열 반전



4. 중위 | 후위 및 접두사 표기법

컴퓨터 과학에서 우리는 많은 산술식을 다루어야 합니다. 표현식은 연산자(+, -, *, / 등)와 피연산자(A, B, c, d, 1, 2,… )와 괄호와 같은 기호로 구성됩니다.

• 중위 표기법 — 이 표기법에서 연산자는 피연산자 사이에 배치됩니다. (<피연산자> <연산자> <피연산자>)
• 표현식이 하나의 연산자(예: 2 + 3, 4 * 6)로만 구성된 경우 표현식을 바로 풀 수 있습니다. 그러나 표현식에 둘 이상의 연산자가 있는 경우 표현식의 모호성 때문에 직접 해결할 수 없습니다. 이 표현 1 + 4 * 5를 고려하십시오. 먼저 덧셈을 수행하면 [ ( 1 + 4 ) * 5 ] = 25로 답을 얻고 곱셈을 먼저 수행하면 [1 + (4 * 5)로 답을 얻습니다. )] = 21. 보시다시피 이 표기법에는 약간의 모호함이 있습니다. 따라서 이를 해결하기 위해 "연산자 우선 순위"라는 것을 사용합니다 . 연산자 우선 순위에 따라 곱셈은 더하기 전에 수행되어야 합니다. 따라서 정답은 25가 아니라 21이어야 합니다.
• 기본적으로 중위 표기법으로 작성된 표현식을 풀려면 일련의 규칙을 따라야 하고 괄호도 추가해야 합니다. 따라서 이 표기법은 해결하는 동안 더 많은 메모리를 사용할 수 있습니다. 따라서 이러한 문제를 극복하기 위해 과학자들은 접두사 및 접미사라는 두 가지 다른 표기법을 고안했습니다.
• 접두사 표기법에서 연산자는 피연산자 앞에 위치 하지만 (<연산자><연산자> <operand>) 후위 표기법에서는 연산자가 피연산자 뒤에 위치합니다. (<피연산자> <피연산자><연산자>)
• 중위 표기법에 비해 다른 두 표기법은 사람이 읽고 이해하기가 상당히 어렵습니다. 그러나 이 두 가지 표기법에는 괄호와 같은 추가 기호가 없고 모호성이 없기 때문에 이 두 가지 형식으로 작성된 표현은 컴퓨터에서 쉽게 읽을 수 있습니다.


• 후위 표현식 평가: 후위 표현식을 평가해야 할 때 연산자를 찾을 때까지 왼쪽부터 검색을 시작해야 합니다. 연산자를 찾으면 연산자 왼쪽에 있는 처음 2개의 피연산자에 관련 대수 연산을 수행해야 합니다.

• 먼저 입력에서 모든 공백을 제거해야 합니다. 따라서 분할 방법을 사용해야 합니다. 그런 다음 표정을 왼쪽에서 오른쪽으로 스캔해야 합니다. 숫자를 만나면 스택에 밀어 넣어야 합니다. 연산자를 만나면 스택에서 맨 위 항목 중 2개를 팝해야 합니다. 그런 다음 산술 연산을 수행하기 위해 도우미 함수를 호출해야 합니다. 그런 다음 결과를 스택에 푸시합니다. 스캐닝이 완료되면 평가된 접미사 표현식에 대한 답변인 스택에 남아 있는 것을 반환합니다.


• 이제 Python을 사용하여 중위 형식의 표현식을 후위 형식으로 변환하는 방법을 살펴보겠습니다.