■ stack의 응용 : 계산기 프로그램$$ 1 + (2+3) / 4 $$스택을 사용하여 계산기를 구현해 보자. 계산기는 아래의 두 가지를 고려해서 연산을 진행할 수 있어야 한다.소괄호를 파악하여 그 부분을 먼저 계산한다.연산자의 우선순위를 근거로 연산의 순위를 결정한다.물론 스택만 사용해서 구현할 수 있는것은 아니고 별도의 알고리즘이 존재하며 이를 활용해야 계산기 프로그램을 만들 수 있다.▶ 전위(prefix), 중위(infix), 후위(postfix) 표기법먼저 수식을 이루는 피연산자가 한자리 숫자로만 이뤄진다고 가정해 보자. 전위, 중위, 후위 표기법은 수학식에서 연산자(operator)를 피연산자(operand) 들 사이 어디에 두느냐에 따른 표기 방식의 차이를 말한다.중위 표기법 (Infix N..

■ 스택(Stack)스택(Stack) 자료구조는 실 생활에서도 자주 볼 수 있는 상황으로 예를 들 수 있다. 쌓인 상자나 프링글스 통 안의 감자칩처럼, 가장 아래에 있는 물건을 꺼내기 위해선 그 위에 있는 물건을 먼저 꺼내야 한다. 따라서 스택은 “가장 나중에 들어간 것이 가장 먼저 나온다.(LIFO : Last-In, First Out)” 라는 후입선출 방식의 자료구조이다. ▶ 스택의 추상 자료형앞서 살펴본 리스트 자료구조의 추상자료형은 필요에 따라 정의 내용이 차이가 있었다. 하지만 스택의 추상 자료형은 상대적으로 정형화된 편이다. 한쪽이 막혀 있는 프링글스 통을 가지고 할 수 있는 일을 정리해 보면 아래와 같다.프링글스 통에 감자칩을 넣는다 : push프링글스 통에서 감자칩을 꺼낸다 : pop제일 ..

■ 양방향 연결 리스트양방향 연결 리스트는 하나의 노드가 자신의 왼쪽(이전)과 오른쪽(다음) 노드를 동시에 가리키는 구조이다.양방향 리스트이면서, 원형 연결 리스트를 동시에 지니는 리스트도 존재한다.그림만 보면 양방향 리스트의 구현은 어려워 보이지만, 양쪽 방향으로 이동할 수 있기 때문에 단방향에서 어렵게 구현했던 것이 쉽게 구현되기도 한다. 양방향 리스트 역시 끝을 가리키는 Tail노드를 사용하지 않고 데이터를 맨 앞에 추가하는 방식으로 구현해 보겠다. ■ 추상 자료형 정의#pragma oncetypedef int LData;struct Node{ LData data; Node* prev = nullptr; Node* next = nullptr;};struct DoublyLinkedList{ Node*..

■ 연결 리스트(Linked List)배열은 메모리에 연속적으로 저장되며 크기가 고정되는 “정적 메모리 구조”이기 때문에, 한번 생성된 후에는 길이를 직접 변경할 수 없다.정확히 말하면 길이를 늘일 수 없는 것이 아닌, 더 큰 배열을 새로 생성한 뒤 기존 데이터를 모두 복사해야 하므로 비효율적이다.그래서 필요할 때마다 데이터를 저장할 수 있는 “노드(연결이 가능한 객체)”를 동적 할당하여 이들을 연결한 것이 바로 연결 리스트이다.즉, 처음 데이터는 그 다음그다음 데이터가 저장된 위치를 가리키고, 다음 데이터는 그다음 데이터의 위치를 가리킨다.연결하는 방식에 따라서 연결 리스트도 여려 종류가 존재한다. 하나씩 천천히 살펴보도록 하자. ■ 단일 연결 리스트(Singly Linked List)단일 연결 리스트..

■ 추상 자료형(Abstract Data Type)리스트(List) 자료구조에 대해 설명하기 전에 먼저 추상 자료형이 뭔지 알아보자.추상 자료형(Adstract Data Type : ADT)은 “자료형이 어떻게 구현되어 있는지는 숨기고 무엇을 할 수 있는지만 정의한 자료형”이다.예를 들어 지갑을 생각해 보면, 우리는 단지 지갑에 지폐나 카드를 넣고 꺼내는 “기능”만 알고 있다.하지만 실제로 지갑을 열고, 돈을 넣고, 다시 닫는 “구제척인 과정(구현 방식)”은 생각하지 않는다.즉 “어떻게”가 아니라 “무엇을 할 수 있는가”에 초점을 맞춘 개념이 바로 추상 자료형(ADT)이다.struct wallet{ int coin100Num; int bill5000Num;}wallet; int TakeOutMoney(w..