자료 구조 - Chpater 06

스택(Stack)

스택

스택(Stack) 또한 선형 자료구조의 일종이다.

스택은 나중에 들어간 것이 먼저 나오는 구조이다. 후입 선출 방식의 자료구조.

영어로 LIFO (Last - In First - Out) 구조의 자료구조이다.

 

스택의 ADT의 정의

• Data를 넣는다.
• Data를 꺼낸다.
• 다시 stack 구조를 참고하며 본다.

스택은 배열을 이용해서 구현이 가능하고, 또 연결 리스트를 이용해서도 구현이 가능하다.

 

예제 : 배열로 스택 구현 (stack)

인덱스 0의 배열 요소는 스택의 바닥이다.

마지막에 저장된 데이터의 위치를 기억해야 한다.

• Push : Top을 위한 한 칸 올리고, Top이 가리키는 위치에 데이터 저장
• Pop : Top이 가리키는 데이터를 반환하고, Top을 아래로 한 칸 내림

스택 구현

ArrayBaseStack.c

0.00MB

ArrayBaseStack.h

0.00MB

ex6-1 StackArray.c

0.00MB

예제 : 연결 리스트로 스택 구현 (stack)

스택도 연결 리스트이다. 다만 저장된 순서의 역순으로 조회가 가능한 연결 리스트이다.

기존 연결 리스트에서 새로운 노드를 꼬리가 아닌 머리에 추가하는 형태로 구현한 연결 리스트이다.

 

연결 리스트 스택 구현

ex6-2 StackLinkedList.c

0.00MB

ListBaseStack.c

0.00MB

 

ListBaseStack.h

0.00MB

예제 : 중위 표기법 연산 후위 표기법으로 변환

f(x) = ( 6 + 7) / 2 ...

식에 대해서 프로그램은 소괄호를 파악하고 먼저 연산을 실행하고 연산자의 우선순위 근거로 연산의 순위를 정한다.

 

수식의 표기법

• 중위 표기법(infix notation)  ->  5 + 2 / 7
• 전위 표기법(prefix notation)  ->  + 5 / 2 7
• 후위 표기법(postfix notation) -> 5 2 7 / +

전, 후위 표기법으로한 계산이 중위 표기법의 수식을 대상으로 한 계산기의 구현보다 좋다.

 

중위 표기법 -> 후위 표기법

• 중위 표기법의 수식을 후위 표기법의 수식으로 변환한다.
• 후위 표기법으로 바뀐 수식을 계산하여 그 결과를 얻는다.

후위 표기법으로 변환

ex6-3 InfixToPost.c

0.00MB

InfixToPostfix.c

0.00MB

InfixToPostfix.h

0.00MB

예제 : 후위 표기법 연산 결과 반환

후위 표기법 연산 결과

ex6-4 Calculator.c

0.00MB

PostCalculator.c

0.00MB

PostCalculator.h

0.00MB

예제 : 예제 파일 정리

중위 표기법으로 입력을 받아 후위 표기법으로 변환한뒤 연산하여 출력하는 프로그램

최종 파일

ex6-5 finish.c

0.00MB

InfixCalculator.c

0.00MB

InfixCalculator.h

0.00MB