|
스택과 큐를 응용해서 만든
프로그램입니다.
그냥 마우스의 움직임을 기억해서 그대로 플레이 하는 프로그램입니다.
스택용은 올리지
않았습니다.
이 것은 큐만을 응용한 것입니다.
아래 글은 이 것을 만들 때 생각했던
것들입니다^^
스택은 하나의 자료 구조입니다. 우리가 배열을 말 할때 같은 형의 자료만 모을 수 있는 자료 구조 라고 말하듯
이 스택도 하나의 자료 구조입니다. 하지만 스택은 자신이 행위적 측면을 포함하는 자료 구조라는 것이 좀 다르
죠. 여기서 행위적 측면이라는 것이 바로 알고리즘을 말합니다. 스택은 pop() 과 push() 라는 행위적 측면이 있
습니다. pop()은 자료를 스택에서 하나 꺼내오는 것이고 push()는 자료를 스택에 하나 집어 넣는 것을 말합니
다. 그리고 스택은 자료를 꺼내고 저장 하는데 방법이 있습니다. 바로 처음 들어온 자료가 제일 마지막에 나간다
입니다. 바로 이것을 LIFO(Last In First Out) 구조라고 합니다.
위의 그림을 보면 4를 한번 push() 하고 다시 pop() 하였습니다. 여기서 중요한 것은 바로 top 이라는 것입니다.
이 top이라는 것은 스택의 꼭대기를 가리키고 있는 인덱스가 되겠습니다. 그래서 스택이 꽉 차면 더이상 push()
할 수 없으므로 top() 값을 조사하여 지금 스택이 Full 인지 아니면 Empty 인지 알아봅니다.
1차 예제는 배열을 사용하여 제한된 크기를 가지는 스택을 만들어 보겠습니다. 이 것은 C로 배우는 알고리즘 책
의 예제를 참고(배꼈습니다^^;;;)했습니다.
<예제 1 배열로 구현하는 스택>
//#############################//
// Stack Test Simulation No. 1 //
//#############################//
#include <stdio.h>
#define MAX 10
int stack[10]; //우리가 사용할 스택 크기는 int형 변수를 10개 넣을 수 있는 20바이트(16bit컴파일러 기준)
int top; //스택의 상단을 가리킬 변수
void init_stack(void)
{
top = -1; //top의 초기값을 -1로 세팅
}
int push(int t)
{
if( top >= MAX - 1) //스택이 꽉 차있는지를 조사하고 있다
{
printf("\t\n Stack overflow.");
return -1;
}
stack[++top] = t; //인덱스를 먼저 증가시키고 자료저장 top을 왜 -1로 했는지 아시겠죠?
return t;
}
int pop(void)
{
if(top < 0) //스택이 텅 비어 있는지를 조사하고 있다
{
printf("\n Stack underflower.");
return -1;
}
return stack[top--]; //자료를 꺼내고 인덱스 하나 감소
}
void print_stack(void) //스택의 현재 모습을 보여준다.
{
int i;
printf("\n Stack contents : top -----> Bottom\n");
for(i= top; i>=0; i--)
printf("%-6d",stack[i]);
}
void main(void)
{
int i;
init_stack();
printf("\nPush 5,4,7,8,2,1");
push(5);
push(4);
push(7);
push(8);
push(2);
push(1);
print_stack();
printf("\nPop");
i = pop();
print_stack();
printf("\n popping value is %d",i);
printf("\push 3, 2, 5, 7, 2");
push(3);
push(2);
push(5);
push(7);
push(2);
print_stack();
printf("\Now stack is full, push 3");
push(3);
print_stack();
printf("\nInitialize stack");
init_stack();
print_stack();
printf("\nNow stack is empty, pop");
i = pop();
print_stack();
printf("\n popping value is %d", i);
}
결과는 여기에 적지 않겠습니다. 직접 해보시길 바랍니다. ^^ 그래야 실력이...^^
이 스택은 배열로 구현하였습니다. 그럼 이 스택은 좋은 스택이 될 수 있을까요? 대답은 아니오 입니다.
상황에 따라 그럴 수도 있겠지만 되부분 유용한 스택이 되질 못 합니다. 왜 그럴까요? 그것은 배열은 크
기가 한 정되어 있어서 메모리 낭비를 초래할 수도 있습니다. 예를 들어 사용자는 3개의 자료만 저장하는
스택이 필요한데 설계자는 이 것을 모르고 10개의 자료를 저장하는 스택을 만들어 주었다고 생각해 봅시다.
그러면 7개의 자료를 저장하는 메모리가 낭비가 되는 것이겠죠. 그럼 때에 따라 스택의 크기가 달라 져야 하는
데 그렇게 할려면 어떻게 해야 할까요? 바로 동적인 메모리 할당입니다.(동적인 메모리 할당은 프로그램 수행
도중에 메모리를 잡는 것을 말합니다.)그리고 링크드 리스트라는 것을 사용해서 스택을 구현합니다. 다음에는
링크드리스트를 이용하여 스택을 구현해 보겠습니다.
################################################################################################
링크드 리스트를 이용하여 스택을 구현하면 다음과 같은 이점이 있습니다.
1. 현재 스택에 저장되어 있는 자료 만큼만 메모리를 잡아먹기 때문에 메모리가 절약된다.
2. 메모리가 허용하는 한도에서 커질 수 있다.
연결리스트를 이용하는 스택의 모양은 아래의 그림과 같습니다.
< 예제 2. 링크드 리스트를 이용한 스택 >
#include <stdio.h>
#include <alloc.h>
//노드의 모양새(?)를 만들고 있다.
typedef struct tagNode
{
int data; //노드가 저장할 자료
struct tagNode *next; //다음 노드를 가리킬 포인터 (이부분은 기초문법서적을 참고하세요^^)
}node;
node* head; //head 노드와 tail 노드를 선언하고 있다.
node* tail;
void init_stack(void) //노드를 초기화 해주는 함수
{
head = (node *)malloc(sizeof(node)); //head와 tail노드를 메모리에 잡고 있다
tail = (node *)malloc(sizeof(node)); //원래 head와 tail은 메모리에 잡을 필요가 없다
head->next = tail; //이들은 자료를 갖지 않고 단지 가리킬 뿐이기 때문이다.
tail->next = tail; //하지만 여기서는 이것이 더 쉽기 때문에 ^^....
}
//자료를 push 하는 함수
int push(int k)
{
node* temp; //노드를 추가시키기 위하여 임시 노드를 만듦
if((temp = (node *)malloc(sizeof(node))) == NULL) //만약 메모리가 없을 때에는 에러를 출력
{
printf("\n Out of Memory...");
return -1;
}
temp->data = k;
temp->next = head->next; //이부분을 잘 이해하셔야 합니다.
head->next = temp; //이부분은 노드를 링크드리스트에 추가시키는 부분입니다.
return k;
}
//자료를 pop하는 함수
int pop(void)
{
node* temp;
int i;
if(head->next == tail) //head의 다음이 tail이면 링크드 리스트가 빈 것이므로 에러를 출력
{
printf("\n Stack underflow.");
return -1;
}
temp = head->next; //이부분을 잘 이해하셔야 합니다.
i = temp->data; //이부분은 링크드 리스트에서 노들르 지우는 것입니다.
head->next = temp->next;
free(temp);
return i;
}
//모든 노드를 지우는 함수
void clear_stack(void)
{
node* current; //현재 노드를 가리키는 포인터
node* old; //이전 노드를 가리키는 포인터
current = head->next; //현재 노드를 head의 다음으로 하고 있다
while( current != tail) //현재 노드가 tail 일 때까지
{
old = current; // 현재 노드를 가리키는 포인터를 예전 노드를 가리키는 포인터에 저장
current = current->next; //현재노드를 현재노드의 다음 노드로 옮김
free(old); // 예전 노드 삭제
}
head->next = tail;
}
//모든 노드를 보여주는 함수
void print_stack(void)
{
node* temp;
temp = head->next;
printf("\n Stack contents : Top ----> Bottom\n");
while( temp != tail)
{
printf("%-6d",temp->data);
temp = temp->next;
}
}
void main(void)
{
int i;
init_stack();
printf("\n Push 5, 4, 7, 8, 2, 1");
push(5);
push(4);
push(7);
push(8);
push(2);
push(1);
print_stack();
printf("\n Pop");
i = pop();
print_stack();
printf("\n popping value is %d", i);
printf("\nPush 3, 2, 5, 7, 2");
push(3);
push(2);
push(5);
push(7);
push(2);
print_stack();
printf("\nPush 3");
push(3);
print_stack();
printf("\nInitialize stack");
clear_stack();
print_stack();
printf("\nNow stack is empty, pop");
i = pop();
print_stack();
printf("\n popping value is %d",i);
}
링크드 리스트를 이용한 스택을 구현해 봤습니다. 아주 좋아보이죠? 메모리의 제약도 거의 받지 않고 메모리가
무한대라면 스택을 무한대로 늘릴 수 있는 방법입니다. 하지만 이것의 문제가 아니라 티가 있다면 무엇일까요?
이 소스를 망치에 비유하자면 이렇습니다. 망치를 쓸 때마다 망치 자체를 조립한 다음에 망치를 써야 합니다.
하지만 망치가 필요할 때 우리는 그냥 망치를 쓰지 누가 망치를 그 때마다 조립해서 씁니까? 그럼 어떻게 해야
할까요?
음... 스택을 객체로 정의하면 어떨까요? 나중에 다른 프로그램에서 필요할 때 스택 클래스만 갖다가 쓰면 되겠
죠..^^ 그럼 망치가 필요할 때 바로 망치만 가져다 쓰듯이 우리도 스택이 필요할 때는 스택만 가져다 쓸 수 있습
니다. 다음에는 스택을 클래스로 구현해 보겠습니다.
################################################################################################
기존의 소스를 클래스화 하였습니다. 이렇게 함으로써 나중에 클래스를 하나의 부품 또는 도구로 사용할 수 있는
것입니다. ^^ 아래 소스 나갑니다^^..
< 예제 3. 클래스화 한 스택 >
#include <stdio.h>
#ifndef STACK
#define STACK
typedef struct tagNode
{
int data;
tagNode* next;
}node;
class kStack
{
public:
//constructure /destructure
kStack();
~kStack();
//operation
int Pop(void);
int Push(int k);
void PrintStack(void);
void ClearStack(void);
private:
//attribute
node* head;
node* tail;
};
kStack::kStack() //생성자에서 스택링크드리스트의 head와 tail을 초기화 하고 있습니다.
{
head = new node[1];
tail = new node[1];
head->next = tail;
tail->next = tail;
}
kStack::~kStack() //소멸자에서 head와 tail 에 해준 동적 메모리 할당을 지우고 있습니다. *중요*
{
delete [] head;
delete [] tail;
}
int kStack::Push(int k)
{
//C++의 new 연산자가 더 편하고 좋기 때문에 malloc 대신에 이것을 사용했습니다
node* temp = new node[1];
if(temp == NULL)
{
printf("\n Out of Memory...");
return -1;
}
temp->data = k;
temp->next = head->next;
head->next = temp;
return k;
}
int kStack::Pop(void)
{
node* temp;
int i;
if(head->next == tail)
{
printf("\n Stack underflow.");
return -1;
}
temp = head->next;
i = temp->data;
head->next = temp->next;
delete [] temp;
return i;
}
void kStack::PrintStack(void)
{
node* temp;
if(head->next == tail)
{
printf("\n Stack is Empty");
return;
}
temp = head->next;
printf("\n Stack contents : Top ----> Bottom\n");
while(temp != tail)
{
printf("%-6d",temp->data);
temp = temp->next;
}
}
void kStack::ClearStack(void)
{
node* current;
node* old;
if(head->next == tail)
{
printf("\n Stack is Empty do not clear");
return;
}
current = head->next;
while(current != tail)
{
old = current;
current = current->next;
delete [] old;
}
head->next = tail;
}
void main()
{
int i;
kStack stack;
printf("\n Push 5, 4, 7, 8, 2, 1");
stack.Push(5);
stack.Push(4);
stack.Push(7);
stack.Push(8);
stack.Push(2);
stack.Push(1);
stack.PrintStack();
printf("\n Pop");
i = stack.Pop();
stack.PrintStack();
printf("\n popping value is %d", i);
printf("\nPush 3, 2, 5, 7, 2");
stack.Push(3);
stack.Push(2);
stack.Push(5);
stack.Push(7);
stack.Push(2);
stack.PrintStack();
printf("\nPush 3");
stack.Push(3);
stack.PrintStack();
printf("\nInitialize stack");
stack.ClearStack();
stack.PrintStack();
printf("\nNow stack is empty, pop");
i = stack.Pop();
stack.PrintStack();
printf("\n popping value is %d",i);
}
#endif //STACK
어떻습니까? 클래스로 구현하니깐 의미가 더욱더 정확해 지지 않았습니까? 하지만 이 클래스에도 문제가 있습
니다. -_-;; 자꾸만 무슨 문제냐구요...? 왜 자꾸 따지냐구요? 그야 더 좋게 만들기 위해서지요 ^^;; 그럼 문제점
을 말해 보겠습니다. 사실 이 스택은 자료를 int형의 자료 밖에 저장하지 못 합니다. 그런데 실제 프로그램에서는
그렇지 않거든요. 하나의 윈도우의 정보를 저장한다거나... 아니면 다른 여러가지 정보가 섞인 자료를 스택에 저
장 할 수도 있습니다. 그럼 그 때마다 그에 맞는 스택 클래스를 만들어 줘야 할까요???? 그렇다면 프로그래머들
은 스트레스 때문에 죽을 것입니다. 그 때 이용하는 것이 C++의 다형성이라는 것입니다. 여기서는 다형성의 극
치인 바로 template(템플릿) 을 사용하는 것입니다. 템플릿을 사용하여 클래스를 만들면 어떤 자료형이 들어와도
상관이 없겠죠? 그럼 다음에 템플릿으로 만든 스택을 올리겠습니다. ^^
##############################################################################################################
안녕하세요^^ 여기까지 오시느라구 힘드 셨죠? 조금만 힘내시길 바랍니다. 이제 스택은 거의 다 끝나가니까요^^
여기서 소스를 설명하고 다음에는 실제적으로 프로그램에 스택을 사용한 경우를 보여드리겠습니다.^^
#include <stdio.h>
#include <stdlib.h>
#ifndef TEMPLATE_STACK
#define TEMPLATE_STACK
template<class T>
class Stack
{
protected:
struct Node
{
Node* next;
T data;
};
private:
Node* head;
Node* tail;
public:
Stack();
~Stack();
void Push(T* d);
T* Pop(void);
T* Get(int index);
};
template<class T>
Stack::Stack()
{
head = new Node[1];
tail = new Node[1];
head->next = tail;
tail->next = tail;
}
template<class T>
Stack::~Stack()
{
delete [] head;
delete [] tail;
}
template<class T>
void Stack::Push(T *d)
{
Node* temp = new Node[1];
temp->data = *d;
temp->next = head->next;
head->next = temp;
}
template<class T>
T* Stack::Pop(void)
{
Node* temp;
T data2;
if(head->next == tail)
{
printf("\nStack is Empty");
exit(1);
}
temp = head->next;
data2 = temp->data;
head->next = temp->next;
delete [] temp;
return &data2;
}
template<class T>
T* Stack::Get(int index)
{
if(index == 0)
{
exit(1);
}
Node* temp;
temp = head;
for(int i=0; i < index; i++)
{
temp = temp->next;
}
return &(temp->data);
}
#endif
위의 소스를 보면 클래스 안에 구조체가 있습니다. 왜 그런 것일까요? 아래의 그림을 보세요.
이 그림을 보면 스택 객체안에 노드들이 들어 있습니다. 만약 이렇게 설계하지 않으면 우리가 노드에 넣을 자료형
에 반드시 그 자료형을 가리킬 수 있는 포인터가 있어야 합니다. 구조체로 예로 들면 .. 내가 POINT라는 구조체를
노드에 넣으려 할 때 반드시 POINT를 가리킬 수 있는 포인터를 선언해 주어야 한다는 말이죠 다음과 같이..
struct POINT
{
int x;
int y;
POINT* next; //POINT를 가리킬 수 있는 포인터
};
하지만 우리가 저장하고 싶은 자료 형태를 만들 때만다 저것을 챙겨줘야 하면 좀 불편하겠죠... 그래서 클래스에
Node라는 구조체를 포함한 것입니다.^^
이 stack의 사용법은 Stack<POINT> stack 이런 형식으로 선언해 주고요 POINT pt 자료를 Push 할 때는 ........
stack.Push(&pt); 이렇게 포인터를 넘겨 줍니다. 이렇게 해야 메모리 낭비가 없겠죠?
그리고 Pop()은 POINT 자료형의 포인터(주소)를 넘겨줍니다. 그래서 POINT* ptr = stack.Pop(); 이렇게 사용 해
줍니다. 그리고 몇 번째 자료를 알고 싶을 때 POINT* ptr = stack.Get(2); // 두번째 자료를 알고 싶을 때 ............
이렇게 사용해 줍니다. ^^ 이렇게 함으로써 모든 자료형을 저정할 수 있는 스택이 만들어 졌습니다. ^^
##############################################################################################################
이 번에는 큐를 이용하여 고스트 마우스라는 프로그램을 만들어 보겠습니다. 고스트 마
우스라는 프로그램은 마우스 움직임을 기억했다가 플레이를 누르면 마우스가 움직였던 대로 재생이 되는 프로그램
입니다.^^ 마우스가 거꾸로가 아닌 똑 같이 재생이 되니깐 큐가 필요하겠죠?
여기서 큐(Queue)란 스택과는 반대로 처음에 들어온 자료가 처음에 나가는 자료가 되겠습니다. 스택을 이해하셨다
면 이해가 잘 되실 것입니다. 우리가 고스트 마우스를 만들기 위해 저장해야할 정보는 마우스 좌표 X,Y 와 마우스 왼
쪽 누름 버튼 확인(True/False) 그리고 오른쪽 마우스 누름 버튼 확인(True/False) 입니다. 구조체로 표현하면....
struct MouseData{
LONG x;
LONG y;
BOOL IsLButtonDown;
BOOL IsRButtonDown;
};
이 되겠죠. ^^
그럼 이 런 자료형도 저장할 수 있고 또 다른 자료형도 저장할 수 있는 템플리트 큐를 만들면 좋을 것 같습니다.
자 아래 템플리트로 만든 큐 소스를 뿌립니다. 링크드 리스트를 이용했지만 이중 링크드 리스트를 이용했습니다.
이중을 사용한 것은 큐가 입구와 출구가 나위어져 있기 때문에 이중 링크드 리스트를 사용하는 것이 표현하기에
편합니다. 단일로도 물론 억지로라면 구현할 수도 있습니다.. 하지만 왠만하면 정신건강을 위하여 ^^
//##########################################################//
//## Template Queue ##//
//## 김성철 ##//
//## http://paran.pe.kg ##//
//## 2000. 5. 3 ##//
//##########################################################//
#ifndef KQUEUE
#define KQUEUE
#ifndef NULL
#define NULL 0
#endif
#include <stdio.h>
template<class T>
class Queue
{
protected:
struct Node
{
T data;
Node* next;
Node* prev;
};
public:
Queue();
virtual ~Queue();
//operation
void Push(T* d); //tail 노드 앞에 새로운 노드를 추가
void Get(T* buffer,int index); //index 순서에 있는 값을 얻어 올 수 있음
void RemoveAll(void); //모든 노드를 지운다
void Remove(T* buffer); //head 노드 다음 노드의 값을 얻고 그 노드를 삭제한다.
private:
Node* head;
Node* tail;
};
//생성자에서 head와 tail을 생성하고 그들의 서로 연결한다.
template<class T>
Queue::Queue()
{
head = new Node[1];
tail = new Node[1];
head->prev = head;
head->next = tail;
tail->prev = head;
tail->next = tail;
}
//소멸자에서 head와 tail을 삭제한다.
template<class T>
Queue::~Queue()
{
delete [] head;
delete [] tail;
}
//Push 함수는 tail 앞에 새로운 노드를 만든다
template<class T>
void Queue::Push(T* d)
{
Node* insert = new Node[1];
if(insert == NULL)
{
printf("Error :: Push Function");
return;
}
insert->data = *d;
//tail 노드 앞에 노드를 추가하는 모습(?)
tail->prev->next = insert;
insert->prev = tail->prev;
tail->prev = insert;
insert->next = tail;
}
//index 에 3이라고 주면 3번째 노드의 값을 얻어온다.(만약 3번째 노드가 있다면..)
template<class T>
void Queue::Get(T* buffer,int index)
{
if(head->next == tail)
{
printf("\nError :: Get Function");
return;
}
Node* temp;
temp = head->next;
for(int i=0; i < index; i++)
{
temp = temp-> next;
}
*buffer = temp->data;
}
//모든 노드를 삭제한다.
template<class T>
void Queue::RemoveAll(void)
{
if(head->next == tail)
{
printf("Error :: RemoveAll");
return;
}
Node* current;
Node* old;
current = head->next;
while(current != tail)
{
old = current;
current = current->next;
delete [] old;
}
head->next = tail;
tail->prev = head;
}
//head 의 다음 노드의 값을 얻고 그 노드를 삭제한다.
template<class T>
void Queue::Remove(T* buffer)
{
if(head->next == tail)
{
printf("\nError :: Remove Function");
return;
}
Node* temp;
temp = head->next;
*buffer = temp->data;
//head 의 다음다음 노드와 연결하고 있다.
head->next = temp->next;
temp->next->prev = head;
tail->prev=tail->prev->prev;
delete [] temp;
}
struct POINT
{
int x;
int y;
};
void main(void)
{
POINT pt[5] = {1,1,2,2,3,3,4,4,5,5};
Queue queue;
for(int i=0; i<5; i++)
{
queue.Push(&pt[i]);
}
POINT temp;
// queue.RemoveAll();
for(int j=0; j<5; j++)
{
queue.Get(&temp,j);
printf("\n%d %d",temp.x, temp.y);
}
}
#endif //class Queue
|