자료구조 - 스택

●스택의 이해

 

  스택의 가장 중요한 특성   -  "먼저 들어간 것이 나중에 나온다 ! "

 

 

LIFO (Last In First Out)

 

 

 

 

 위의 테이블은 D->C->B->A 순으로 들어온 것이고, 나갈때는 A->B->C->D 순으로 나가게 된다. 해당 값은 바닥부터 채워지고, 나갈때는 위에서 부터 나가게 된다. 이런 형태를 LIFO라고 하는데, "나중에 들어와서 처음으로 나간다" 라는 뜻이다. 

 

 

 

●스택 ADT의 정의

 

   우리가 스택으로 할 수 있는 일은 한정적이다. 

 

  1. PUSH   ->   스택에 값을 넣는다

  2. POP     ->   스택에서 값을 빼낸다

  3. PEEK    ->   이번에 꺼낼 값이 무엇인지 확인한다.

 

이것은 스택의 보편적인 ADT이다.

(ADT란 Abastract Data Type으로, 자료들과 그 자료들에 대한 연산들을 명기한 것 입니다. 다시 말해, 특정 자료형과 그 자료형을 바탕으로 하는 기능들(함수들)의 집합을 ADT라고 합니다.)

 

 

- 스택 자료구조의 ADT 

   

   void StackInit(Stack * pstack);      // 스택의 초기화를 진행한다.

   int SIsEmpty(Stack * pstack);       // 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

   void SPush(Stack * pstack, Data data);  //  스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

   Data SPop(Stack * pstack);         // 마지막에 저장된 요소를 삭제한다.

   Data SPeek(Stack * pstack);      // 마지막에 저장된 요소를 반환하되 삭제하지 않는다.

 

 

   ADT를 정의했다면, 이를 기반으로 스택의 구현을 위한 구조체를 정의하고 헤더파일을 디자인 해야한다. 

  여기서 구현 방법은 2가지가 있다.

 

 

 

    - 연결리스트

 

    - 배열

 

 

 

스택 개념을 활용하기 좋은 문제가 있다.

 

https://www.acmicpc.net/problem/10828

10828번: 스택

 

스택을 구현하는 문제는 이거 한 문제로 충분하다고 생각한다.

 

 

 

●계산기 프로그램 구현

   

    스택을 활용하여 계산기 프로그램을 구현할 수 있다. 

 

  ▶  ( 2 + 3 ) * 3 + 4 + 2 / 2

 

     위 문장이 있다고 한다면, 계산의 우선 순위를 따져봐야 할 것이다. 

 

   - 소괄호를 파악하여 그 부분을 먼저 연산한다.

   - 연산자의 우선순위를 근거로 연산의 순위를 결정한다.

 

해당 연산을 하기 전, 먼저 알아야 할 개념이 있다. 

 

     중위 표기법   /    전위 표기법    /  후위 표기법 

 

 중위 표기법  -  예) 5 + 2 / 7

 전위 표기법  -  예) + 5 / 2 7 

 후위 표기법  -  예) 5 2 7 / + 

 

 

우리가 일상 생활에서 사용하는 표기법은 '중위 표기법'이다.