[뇌를 자극하는 알고리즘] 2 . 스택

스택(Stack): 뭔가를 아래에서 부터 위로 쌓아 얹어 올리도록 하는 자료구조.

중간에 데이터를 삽입하거나 삭제하는 것을 허용하지 않음. 데이터의 입출력은 오로지 스택의 꼭대기에서만 이루어짐.

가장 마지막에 들어간 데이터가 제일 먼저 나오고 LIFO(Last In - First Out)

가장 먼저 들어간 데이터는 가장 나중에 나옴 FILO(First In - -Last Out).

 

 

2.2 스택의 주요 기능: 삽입과 제거

삽입:  스택 위에 새로운 노드를 쌓는 작업

제거: 스택에서 최상위 노드를 걷어내는 작업

 

2.3 배열로 구현하는 스택

배열 기반 스택

: 동적으로 스택의 용랭을 조절하기가 어렵다 but 구현이 간단하다

각 노드를 동적으로 생성하고 제거하는 대신 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성함.

최상위 노드위치를 나타내는 변수를 이용해 삽입과 제거 연산을 수행.

 

스택과 스택의 노드 표현하기

스택의 노드는 데이터만 담는 구조체로 표현됨.

노드가 존재하는 위치는 배열의 인덱스로 알 수 있기 때문에 링크드 리스트처럼 앞이나 뒷 노드에 대한 포인터는 필요 없음.

 

[스택 구조체]

  -용량 (스택이 얼마만큼의 노드를 가질 수 있는지)

  -최상위 노드의 위치 (삽입/제거 시에 최상위 노드에 접근할 수 있게 해줌)

  -노드 배열 (스택에 쌓이는 노드를 보관하는데 사용)

 

스택의 기본 연산 구현하기

c언어

-스택 생성과 소멸

   AS_CreateStack(): 생성

   AS_DestroyStack(): 소멸

-삽입(Push)연산

   AS_Push()

-제거(Pop)연산

   AS_Pop()

  

 

2.4  링크드 리스트로 구현하는 스택

링크드 리스트 기반 스택:

스택의 용량에 제한없음.  

 

스택과 스택의 노드 표현하기

링크드 리스트는 인덱스로 노드에 접근할 수 없음.

so 링크들 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드(스택은 쌓아 올리는 구조)에 대한 포인터 필요.

링크드 리스트 스택은 배열 기반 스택과는 달리 스택용량이나 최상위 노드의 인덱스가 없음.

대신 헤드와 테일(Top 포인터)에 대한 포인터가 필요함.

 

스택의 기본 연산 구하기

c언어

-스택의 생성과 소멸 

  LLS_CreateStack(): 생성

  LLS_DestroyStack(): 소멸

-삽입(Push)연산

   LLS_Push()

-제거(Pop)연산

   LLS_Pop()

 

2.5  스택의 응용:  사칙 연산 계산기 

수식의 중위 표기법과 후위 표기법

중위 표기법(Infix Notation): 우리가 일상적으로 사용하는 수식 표기법  ex) 23 / 7 + 12

후위 표기법(Postfix Notation): 연산자를 피연산자 뒤에 위치시키는 수식 표기법  ex) 23 7 /  12 +

후위 표기식 계산 알고리즘

1. 식의 왼쪽부터 요소를 읽어내면서 피연산자는 스택에 담기

2. 연산자가 나타난 경우에 스택에서 피연산자 두 개를 꺼내 연산하고 그 결과를 다시 스택에 삽입

 

* 토큰(Token): 최소 단위의 기호 또는 단어 * 

 

 

중위 -> 후위 표기법 변환 알고리즘

 

 

.