1. 큐
- 큐(Queue)는 우리 말로 번역하면 대기행렬
- 대기가 "기다리다", 행렬이 "줄"이라는 뜻이니 큐는 "기다리는 줄"이라고 할 수 있다.
2. 큐의 주요 기능 : 삽입과 제거
- 전단(Front)과 후단(Rear)
- 삽입(Enqueue)
- 제거(Dequeue)
3. 끝은 새로운 시작이다: 순환 큐
- 배열로 큐를 구현할 때의 문제점 :
1. 스택이란?
- 스택은 나중에 들어간 요소가 가장 먼저 나오는 (Last-In, First-Out:LIFO) 자료구조
2. 스택의 주요 기능 : 삽입과 제거
- 삽입(Push)
- 삭제(Pop)
3. 배열로 구현하는 스택
- 스택 구조체의 선언
typedef struct tagArrayStack{ int Capacity; /* 용량 */ int Top; /* 최상위 노드의 위치 */ Node* Nodes; /* 노드 배열 */ } ArrayStack; |
- 스택의 생성
void AS_CreateStack(ArrayStack** Stack, int Capacity) { /* 스택을 자유저장소에 생성 */ (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack)); /* 입력된 Capacity만큼의 노드를 자유저장소에 생성 */ (*Stack)->Nodes = (Node*)malloc(sizeof(Node)*Capacity); /* Capacity 및 Top 초기화 */ (*Stack)->Capacity = Capacity; (*Stack)->Top = 0; } |
- 스택의 소멸
void AS_DestroyStack(ArrayStack* Stack) { /* 노드를 자유 저장소에서 해제 */ free(Stack->Nodes); /* 스택을 자유 저장소에서 해제 */ free(Stack); } |
- 삽입(Push) 연산
void AS_Push(ArrayStack* Stack, ElementType data) { int Position = Stack->Top; Stack->Nodes(Position)Data = Data; Stack->Top++; } |
- 제거(Pop) 연산
ElementType AS_Pop(ArrayStack* Stack) { int Position = --(Stack->Top); return Stack->Nodes(Position)Data; } |
4. 링크드 리스트로 구현하는 스택
- 노드 구조체
typedef struct tagNode { char* data; struct tagNode* NextNode; } Node; |
- 스택 구조체
typedef struct tagLinkedListStack { Node* List; Node* Top; } LinkedListStack; |
- 삽입(Push) 연산
void LLS_Push(LinkedListSTack* Stack, Node* NewNode) { if(Stack->List == NULL) { Stack->List = NewNode; } else { /* 최상위 노드를 찾아 NewNode를 연결한다.(쌓는다.) */ Node* OldTop = Stack->List; while(OldTop->NextNode != NULL) { OldTop = OldTop ->NextNode; } OldTop->NextNode = NewNode; } /* 스택의 Top 필드에 새 노드의 주소를 등록한다. */ Stack->Top = NewNode; } |
- 삭제(Pop) 연산
Node* LLS_Pop(LinkedListStack* Stack){ /* 현재 최상위 노드의 주소를 다른 포인터에 복사해 둔다. */ Node* TopNode = Stack->Top; if(Stack->List == Stack->Top) { Stack->List = NULL; Stack->Top = NULL; } else { /* 새로운 최상위 노드를 스택의 Top 필드에 등록한다. */ Node* CurrentTop = Stack->List; while(CurrentTop != NULL && CurrentTop->NextNode != Stack->Top) { CurrentTop = CurrentTop -> NextNode; } Stack->Top = CurrentTop; CurrentTop->NextNode = NULL; } return TopNode; } |
5. 스택의 응용: 사칙 연산 계산기
- 중위 표기법 : 연산자가 피연산자의 가운데 위치
- 후위 표기법 : 연산자가 피연산자의 뒤에 위치
중위 표기법 |
후위 표기법 |
1 + 3 |
1 3 + |
23 / 7 + 12 |
23 7 / 12 + |
(117.32 + 83) * 49 |
117.32 83 + 49 * |
1 - 3 * 2 |
1 3 2 * - |
- 후위 표기식 계산 알고리즘
- 중위 표기법에서 후위 표기법으로의 변환 알고리즘
+ 입력받은 중위 표기식에서 토큰을 읽는다.
+ 토큰이 피연산자이면 토큰을 결과에 출력한다.
+ 토큰이 연산자(괄호포함)일 때, 이 토큰이 스택의 최상위 노드에 저장되어 있는 연산자보다 우선순위가 높으면(왼쪽 괄호는 우선 순위가 가장 낮다.) 스택에 삽입하고, 그렇지 않다면 결과에 출력한다.
+ 토큰이 오른쪽 괄호 ')' 이면 최상위 노드에 왼쪽 괄호'('가 올때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지는 않는다.
+ 중위 표기식에 더 읽을 것이 없다면 빠져나가고, 더 읽을 것이 있다면 1부터 다시 반복한다.
토큰 |
작업 |
출력 |
스택 |
(117.32 + 83) * 49 |
스택에 '(' 삽입 |
|
( |
(117.32 + 83) * 49 |
117.32 출력 |
117.32 |
( |
(117.32 + 83) * 49 |
스택에 '+' 삽입 |
117.32 |
+ ( |
(117.32 + 83) * 49 |
83 출력 |
117.32 83 |
+ ( |
(117.32 + 83) * 49 |
스택의 모든 연산자 제거 후 출력 ('('는 출력 안함) |
117.32 83 + |
|
(117.32 + 83) * 49 |
스택에 '*' 삽입 |
117.32 83 + |
* |
(117.32 + 83) * 49 |
49 출력 |
117.32 83 + 49 |
* |
(117.32 + 83) * 49 |
식 모두 읽었음. 스택의 모든 연산자 제거 후 출력 |
117.32 83 + 49 * |
|
1. 링크드 리스트
1-1. 특징
- 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조
- 각 노드는 다음 노드를 가리키는 포인터를 가짐.
- 각 노드를 다음 노드를 가리키는 포인터로 연결하여 만든 리스트. Single Linked List라고도 함.
- 링크드 리스트의 첫 번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 한다.
- 헤드(Head) : 첫번째 노드의 주소값을 가지고 있음(Pointer Type)
- 테일(Tail) : 마지막 노드의 주소값을 가지고 있음(Pointer Type)
1-2. 단점
- 앞에 있는 노드를 찾아갈 방법이 없다.
1-3. 배열과의 차이점
- 리스트는 주소를 통해 다른 노드로 접근하나 배열은 index 값을 통해 접근한다.
1-4. C언어로 표현하는 링크드 리스트의 노드
|
1-5. 노드의 추가
1-6. 노드의 삭제
1-7. 노드의 삽입
2. 더블 링크드 리스트
2-1. 특징
- 각 노드가 앞 노드/뒷 노드 양쪽에 대한 포인터를 모두 갖고 있어 각 노드들을 이중으로 연결하는 리스트.
2-2. 노드의 추가
2-3. 노드의 삭제
2-4. 노드의 삽입
3. 환형 링크드 리스트
- 우로보로스처럼 머리(헤드)가 꼬리(테일)를 물고 있는 형태의 링크드 리스트
3-1. 노드 추가
- 최초의 노드를 추가하는 경우(즉, 노드가 한 개 뿐)
- 리스트에 노드가 이미 한 개 이상 존재하는 경우에는 테일과 헤드 사이에 새 노드를 삽입한다.
- 코드
void CDLL_AppendNode(Node** Head, Node* HeadNode) { /* 헤드 노드가 NULL이라면 새로운 노드가 Head */ if((*Head) == NULL) { *Head = HeadNode; (*Head)->NextNode = *Head; (*Head)->PrevNode = *Head; } else { /* 테일과 헤드 사이에 HeadNode를 삽입한다. */ Node* Tail = (*Head)->PrevNode; Tail->NextNode->PrevNode = HeadNode; Tail->NextNode = HeadNode; HeadNode->NextNode = (*Head); HeadNode->PrevNode = Tail /* 기존의 테일을 새로운 */ /* 테일의 PrevNode가 가리킨다. */ } } |
3-2. 노드의 삭제
-코드
void CDLL_RemoveNode(Node** Head, Node* Remove){ if(*Head == Remove) { (*Head)->PrevNode->NextNode = Remove->NextNode; (*Head)->NextNode->PrevNode = Remove->PrevNode; *Head = Remove->NextNode; Remove->PrevNode = NULL; Remove->NextNode = NULL; } else { Node* Temp = Remove; Remove->PrevNode->NextNode = Temp->NextNode; Remove->NextNode->PrevNode = Temp->PrevNode; Remove->PrevNode = NULL; Remove->NextNode = NULL; } } |
