스택 응용 - 미로 찾기

스택을 활용하여 미로찾기

움직일 수 있는 공간 0 

장애물 숫자1

방문지점 숫자2

골인지점 숫자3

1. 출발지점 에서부터 다음 방향으로 이동 가능여부를 판단한다.

2. 다음 방향은 ↑ → ↓ ← 순으로 확인을 한다.

3. 움직일 수 있는 공간이면 현재 지점을 방문으로 지정하고 스택에 Push후 다음 지점으로 이동한다.

4. 이미 방문한 지점이고 이동할 수 없으면 스택에서 Pop을 한 후 이전지점의 으로 이동하고 방향을 확인한다.

5. 골인 지점에 도착하면 종료한다.

필요한 전역 함수

const int Width = 10;
const int Height = 10;
int Map[Height][Width] =
{
	0,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,1,1,
	1,1,1,0,1,1,1,1,1,1,
	1,1,1,0,1,1,1,1,0,1,
	1,1,1,0,1,1,1,1,0,1,
	1,0,0,0,0,0,0,0,0,1,
	1,0,1,1,1,1,1,1,1,1,
	0,0,1,1,1,0,0,0,0,1,
	0,1,1,1,1,0,1,1,0,1,
	0,0,0,0,0,0,1,1,0,3
};

int DirectionOffset[4][2] =
{
    {0, -1},
    {1, 0},
    {0, 1},
    {-1, 0}
};

스택 미로찾기 함수

MyStack* PathFinder()
{
    MyStack* Stack = new MyStack();

    Position Pos;
    Pos.X = 0;
    Pos.Y = 0;
    Pos.Dir = 0;

    int Dir = Pos.Dir;
    Stack->Push(Pos);

    while (1)
	{   
        Pos = Stack->Top();
        Dir = Pos.Dir;

		while (Dir < 4)
		{
			int NewX = Pos.X + DirectionOffset[Dir][0];
			int NewY = Pos.Y + DirectionOffset[Dir][1];

			if (NewX >= 0 && NewX < Width &&
				NewY >= 0 && NewY < Height &&
				Map[NewY][NewX] != 1 && Map[NewY][NewX] != 2)
			{
				Map[Pos.Y][Pos.X] = 2;

				Pos.X = NewX;
				Pos.Y = NewY;
				Pos.Dir = Dir + 1;
				Stack->Push(Pos);

				Dir = 0;

				if (Pos.X == 9 && Pos.Y == 9)
				{
                    			return Stack;
				}
			}
			else
			{
				Dir++;
			}
		}
		Stack->Pop();
	}

    return nullptr;
}

메인 함수

int main()
{
    MyStack* Stack = PathFinder();
    Stack->Show();
}

스택 응용 - 사칙연산 계산기

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

스택으로 사칙연산 계산기를 구한하기전 수식에서 중위 표기법과 후위 표기법을 알아야 한다.

중위 표기법은 사람이 알기 쉽게 표현이 가능하고, 후위 표기법은 컴퓨터가 연산을 하기 쉽게 표현한 방법이다.

후위 표기 수식 -> 중위 표기수식 으로 변환하는 알고리즘

1. 피연산자를 만나면 스택에 Push

2. 연산자를 만나면 연산에 필요한 개수만큼 스택에서 Pop

3. 연산한 결과를 다시 스택에 Push

4. 더이상 없으면 연산 후 출력

==후위 수식을 중위 수식으로 바꾸고 그 값을 계산해서 반환해주는 함수==

double Calc(const string PostfixExpression)
{
    int Value = -1;

    MyStack* Stack = new MyStack();

    int PostfixLength = PostfixExpression.length();

    for (int i = 0; i < PostfixLength; ++i)
    {
        char Ch = PostfixExpression[i];

        int CheckCh = isdigit(Ch);

        if (CheckCh > 0 || Ch == '.')
        {
            Stack->Push(Ch);
        }
        else
        {
            if (!Stack->IsEmpty())
            {
                int Value1 = (int)Stack->Pop() - 48;
                int Value2 = (int)Stack->Pop() - 48;
                switch (Ch)
                {
                case '+':
                    Value = Value2 + Value1;
                    break;
                case '-':
                    Value = Value2 - Value1;
                    break;
                case '*':
                    Value = Value2 * Value1;
                    break;
                case '/':
                    Value = Value2 / Value1;
                    break;
                }

                Stack->Push(char(Value + 48));
            }
        }
    }

    return Value;
}

스택 응용 - 사칙연산 계산기

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

스택으로 사칙연산 계산기를 구한하기전 수식에서 중위 표기법과 후위 표기법을 알아야 한다.

중위 표기법은 사람이 알기 쉽게 표현이 가능하고, 후위 표기법은 컴퓨터가 연산을 하기 쉽게 표현한 방법이다.

중위 표기 수식 -> 후위 표기수식 으로 변환하는 알고리즘

1. 피연산자를 만나면 바로 출력

2. 연산자를 만나게 되면 스택에 Push

3. 스택에 보관 중인 연산자 중에서 우선순위가 높은 연산자는 Pop을 하고 출력

4. 스택에 있는 연산자와 외부의 연산자는 우선순위가 다름

5. 닫는 괄호 연산자를 만나게 되면 스택에서 여는 괄호를 만날때 까지 스택에서 Pop을 하고 출력

이러한 규칙을 이용하여 중위 표기 수식을 후위 표기 수식으로 변환 할 수 있다.

==스택의 데이터에서 우선순위를 반환해주는 함수==

int GetStackPriority(const char& StackTopData)
{
    switch (StackTopData)
    {
    case '(':
        return 0;
    case ')':
        return 4;
    case '*':
    case '/':
        return 2;
    case '+':
    case '-':
        return 1;
    }
}

==중위 수식의 데이터에서 우선순위를 반환해주는 함수==

int GetInFixPriority(const char& StackTopData)
{
    switch (StackTopData)
    {
    case '(':
        return 5;
    case ')':
        return 4;
    case '*':
    case '/':
        return 2;
    case '+':
    case '-':
        return 1;
    }
}

==중위 수식을 후위 수식으로 바꾸고 반환 해주는 함수==

string GetPostfix(const string& InfixExpression)
{
	int InfixLength = InfixExpression.length();
	
	string PostfixExpression;

    MyStack* Stack = new MyStack();

	for (int i = 0; i < InfixLength; ++i)
	{
		if (InfixExpression[i] == ' ')
		{
			continue;
		}
		char Ch = InfixExpression[i];

		int CheckCh = isdigit(Ch);

		if (CheckCh > 0 || Ch == '.')
		{
			PostfixExpression.append(1, Ch);
		}
		else
		{
            if (!Stack->IsEmpty())
            {
                if (Ch == ')')
                {
                    while (Stack->Top() != '(')
                    {
                        PostfixExpression.append(1, Stack->Pop());
                    }
                    Stack->Pop();
                    continue;
                }

                char StackPopCh = Stack->Top();
                int InFixPriority = GetInFixPriority(Ch);
                int StackPriority = GetStackPriority(StackPopCh);

                if (InFixPriority < StackPriority)
                {
                    PostfixExpression.append(1, Stack->Pop());
                }
            }
            Stack->Push(Ch);
		}
	}

    while (!Stack->IsEmpty())
    {
        PostfixExpression.append(1, Stack->Pop());
    }

	return PostfixExpression;
}

스택(Stack)

스택 이란?

• 가장 마지막에 들어간 데이터가 제일 먼저 나온다 (Last In - First Out) LIFO
• 가장 먼저들어간 데이터는 가장 나중에 나온다 (First In - Last Out) FILO
• 변수를 선언 후 수명주기가 끝나면 자동으로 제거해주는 메모리도 스택으로 구현되어 있다.

스택의 주요 기능

위의 이미지는 싱글 링크드 리스트를 이용하여 스택을 구현한 그림이다.

처음 데이터를 헤드앞부분에 추가를 해주고 그다음 들어오는 데이터 또한 헤드 앞부분에 추가를 해준다.

그럼 처음 들어온 데이터는 자연히 뒤쪽으로 가게 되며 나중에 들어온 데이터는 헤드의 다음노드를 가르키는 포인터가

자연히 첫 데이터가 된다. 이를 이용하여 스택의 기능을 구현 할 수가 있다.

• 삽입
• 제거

링크드 리스트를 이용한 스택 클래스

#include <iostream>
 struct StackNode
{
    int Data;
    StackNode* Next;
};

class MyStack
{
public:
    MyStack();
private:
    StackNode* Head;

public:

    int Pop();
    void Push(const int& NewData);
    bool IsEmpty();
    void Clear();
    void Show();
};

저는 단순히 구조체를 이용했지만 노드를 클래스화 하고 프렌드를 사용해도 똑같을 것 이다.

링크드 리스트를 이용한 스택  삽입

위 그림처럼 헤드 앞부분에 삽입을 해주어야 한다.

그래야 스택처럼 먼저 들어온 데이터는 뒤쪽에 저장이되고 나중에 들어온 데이터를 헤드의 다음노드를 가르키는 부분부터 참조하여 먼저 빼낼 수 가 있다.

void MyStack::Push(const int& NewData)
{
    StackNode* NewNode = new StackNode();
    NewNode->Data = NewData;
    NewNode->Next = Head->Next;
    Head->Next = NewNode;
}

링크드 리스트를 이용한 스택  제거

스택에서 Pop은 제일 마지막에 들어온 데이터를 제거해준다.

위의 그림에서 제일 마지막에 들어온 데이터는 30을 가진 노드이다. 이 노드를 삭제 하기전에

헤드의 다음노드를 가르키는 포인터를 삭제되는 다음 노드를 가르키는 포인터쪽에 재설정을 해주어야 한다.

그럼 위의 그림처럼 30을 가진 데이터는 빠져나가고 순서대로 10의 데이터 20의데이터를 가진 리스트를 볼 수 있다.

int MyStack::Pop()
{
    if (!IsEmpty())
    {
        if (Head->Next != nullptr)
        {
            StackNode* RemoveNode = Head->Next;
            Head->Next = RemoveNode->Next;
            int Data = RemoveNode->Data;
            delete RemoveNode;
            return Data;
        }
    }
    return -1;
}

링크드 리스트를 이용한 스택  전체 제거

void MyStack::Clear()
{
    if (IsEmpty())
    {
        std::cout << "데이터가 없습니다" << std::endl;
        return;
    }

    StackNode* CurrentNode = Head;
    StackNode* RemoveNode = nullptr;

    while (CurrentNode->Next != nullptr)
    {
        RemoveNode = CurrentNode->Next;
        CurrentNode->Next = RemoveNode->Next;

        int Data = RemoveNode->Data;
        std::cout << Data << "삭제" << std::endl;

        delete RemoveNode;
    }
}

메인 코드

int main()
{
    MyStack* Stack = new MyStack();
    Stack->Push(1);
    Stack->Push(2);
    Stack->Push(3);
    Stack->Pop();
    Stack->Show();
    Stack->Clear();
}

Push함수를 통해 1,2,3을 집어넣으면 리스트엔 헤드부분 부터 3,2,1 순으로 저장되어있다.

그리고 Pop함수를 호출하면 3이 빠져나가고 2,1이 저장되거 있을 것 이다.

이를 Show함수를 통해 출력하면 2,1이 출력되고 Clear함수를 통해 리스트의 데이터를 지워버리면

헤드의 앞부분 부터 차례대로 지워질 것 이다.

스택 이란?

• 가장 마지막에 들어간 데이터가 제일 먼저 나온다 (Last In - First Out) LIFO
• 가장 먼저들어간 데이터는 가장 나중에 나온다 (First In - Last Out) FILO
• 변수를 선언 후 수명주기가 끝나면 자동으로 제거해주는 메모리도 스택으로 구현되어 있다.

스택의 주요 기능

• 삽입
• 제거

배열 형 스택 클래스 

class MyStack
{
public:
    MyStack();
private:

    int Capacity;
    int* Data;
    int Top;

public:

    int Pop();
    void Push(const int& NewData);
    bool IsEmpty();
    void Create(const int& Size);
    void Show();
};

배열 형 스택 초기화

MyStack::MyStack()
{
    Capacity = 0;
    Data = nullptr;
    Top = -1;
}

스택의 생성자를 통해 변수들을 초기화 해준다.

배열 형 스택 생성

void MyStack::Create(const int& Size)
{
    Capacity = Size;
    Data = new int[Capacity];
}

외부로부터 사이즈를 받고 그 사이즈만큼 배열형 스택을 만들어 준다.

배열 형 스택 삽입

void MyStack::Push(const int& NewData)
{
    if (Top < Capacity - 1)
    {
        Data[++Top] = NewData;
    }
}

외부로부터 데이터를 받고 그 데이터를 배열형 스택에 저장해준다.

처음의 Top은 -1이기에 전위증감연산자를 통해 0을 만들고 0의 위치에 데이터를 넣어준다.

그다음에 들어오는 데이터는 Top이 1이 될거고 1의 위치에 데이터를 넣게 된다.

배열 형 스택 확인

bool MyStack::IsEmpty()
{
    return Top == -1 ? true : false;
}

비어있는지 확인하는 코드이다.

Top이 -1이면 true를 반환하고 0이상이면 false를 반환한다.

bool MyStack::IsFull()
{
    return Top == Capacity - 1 ? true : false;
}

꽉차있는지 확인하는 코드이다.

Top이 Capacity-1 과 같다면  true를 반환하고 아니면 false를 반환한다.

배열 형 스택 제거

int MyStack::Pop()
{
    if (!IsEmpty())
    {
        return Data[Top--];
    }
    std::cout << "꺼낼 데이터가 없습니다" << std::endl;
    return -1;
}

비어있는지 확인 후 Top의 위치의 인덱스에 접근하여 데이터를 반환 후 Top의 위치를 -1만큼 감소시킨다.

메인 코드

int main()
{
    MyStack* Stack = new MyStack();
    Stack->Create(5);
    Stack->Pop();
    Stack->Push(1);
    Stack->Push(2);
    Stack->Pop();
    Stack->Push(3);
    Stack->Push(4);
    Stack->Push(5);
    Stack->Push(6);
    Stack->Show();
}

먼저 Create함수를 통해 5의 크기를 만들어 주고

Pop함수로 데이터를 꺼내옵니다. 이때 데이터가 없기에 무시되며

Push함수를 통해 1,2 를 집어 넣고 Pop함수를 실행하면 2가 제일 마지막에 들어왔기에 2가 빠져나가고

다시 Push함수를 통해 3,4,5,6을 집어 넣으면 1,3,4,5,6 이 스택배열에 존재 할 것이다.

환형 링크드 리스트(Circular Linked List)

환형 링크드 리스트란?

• 단일 연결 리스트로 구현 시 Tail의 다음 노드 포인터가 Head를 가리킴
• 이중 연결 리스트로 구현 시 Tail의 다음 노드 포인터가 Head이고 Head의 이전 노드 포인터는 Tail을 가르킨다.
• 데이터의 추가, 삽입, 삭제는 용이하나 그 과정까지 탐색 속도가 떨어진다.
• 머리와 꼬리가 서로 연결되어있기때문에 중간의 어디서든 탐색이 가능해진다.

저는 생성자에서 이를 미리 연결 시켜놨습니다.

LinkedList::LinkedList()
{
	Head = new Node();
	Tail = new Node();
	Head->Next = Tail;
	Head->Prev = Tail;
	Tail->Next = Head;
	Tail->Prev = Head;
}

환영 링크드 리스트 구현

• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

구현시 더블링크드 리스트와 거의 차이가 없다.

노드 추가

더블 링크드 리스트와 차이가 없다.

void LinkedList::Add(const int& NewData)
{
	Node* NewNode = new Node();

	if (NewNode != nullptr && Tail != nullptr)
	{
		NewNode->Data = NewData;
		NewNode->Prev = Tail->Prev;
		NewNode->Next = Tail;
		Tail->Prev->Next = NewNode;
		Tail->Prev = NewNode;
	}
}

노드 탐색

더블 링크드 리스트와 차이가 없다. 단지 어디서든 탐색이 가능해진다.

Node* LinkedList::Search(const int& Data)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		while (CurrentNode->Next != Tail)
		{
			if (CurrentNode->Next->Data == Data)
			{
				return CurrentNode->Next;
			}

			CurrentNode = CurrentNode->Next;
		}
		std::cout << "검색 할 노드가 없습니다" << std::endl;
		return nullptr;
	}
	else
	{
		std::cout << "헤드가 없습니다" << std::endl;
		return nullptr;
	}
}

노드 삭제

더블 링크드 리스트와 차이가 없다.

void LinkedList::Remove(Node* InRemoveNode)
{
	Node* CurrentNode = Head->Next;
	if (CurrentNode != nullptr && InRemoveNode != nullptr)
	{
		if (CurrentNode == InRemoveNode)
		{
			Head->Next = InRemoveNode->Next;
			InRemoveNode->Next->Prev = Head;
		}
		else
		{
			InRemoveNode->Prev->Next = InRemoveNode->Next;
			InRemoveNode->Next->Prev = InRemoveNode->Prev;
		}
		std::cout << InRemoveNode->Data << "제거" << std::endl;
		delete InRemoveNode;
	}
}

노드 삽입

더블 링크드 리스트와 차이가 없다.

void LinkedList::Insert(const int& NewData, const int& Index)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		for (int i = 0; i < Index; ++i)
		{
			if (CurrentNode != nullptr)
			{
				CurrentNode = CurrentNode->Next;
			}
			else
			{
				std::cout << Index << "번째의 노드가 없습니다" << std::endl;
				return;
			}
		}
	}

	if (CurrentNode == nullptr)
	{
		std::cout << Index << "번째의 노드가 없습니다" << std::endl;
		return;
	}

	Node* NewNode = new Node();
	if (NewNode != nullptr)
	{
		NewNode->Data = NewData;

		CurrentNode->Next->Prev = NewNode;
		NewNode->Next = CurrentNode->Next;
		NewNode->Prev = CurrentNode;
		CurrentNode->Next = NewNode;
	}
}

메인 코드

int main()
{
	LinkedList* List = new LinkedList();

	if (List != nullptr)
	{
		List->Add(5);
		List->Add(9);
		List->Add(7);
		List->Insert(3, 1);
		List->Show();
		Node* RemoveNode = List->Search(9);
		if (RemoveNode != nullptr)
		{
			List->Remove(RemoveNode);
		}
		List->Show();
	}
}

리스트에 5,9,7을 add함수를통해 넣어주고 1번째뒤에 3을 넣어주면 5 3 9 7이 된다.

헤드와 테일에는 0으로 초기화를 해주었고 이를 Show함수를통해 출력을 한다.

void LinkedList::Show()
{
	Node* CurrentNode = Head->Next;

	if (CurrentNode != nullptr)
	{
		while (1)
		{
			std::cout << CurrentNode->Data << std::endl;
			CurrentNode = CurrentNode->Next;
			Sleep(1000.f);
		}
	}
}

Sleep함수를 통해 1초마다 실행되게 하고 다음노드를 계속 출력해주는 코드이다.

이러면 0 5 3 9 7 0 이 반복적으로 출력된다.