(C++) 자료구조 - 스택(Stack) - 배열(Array), 링크드리스트(Linked List)

안녕하세요

오늘은 자료구조 스택입니다!

오늘은 2가지 스택을 구현해 보려고 하는데요

배열을 이용한 스택과

링크드리스트를 이용한 스택입니다.

그래서 두가지 클래스를 정의 하고 동적할당 하여 생성, 해제를 해보도록 하겠습니다.

 

1. 스택이란?

LIFO(Last In First Out)

제일 마지막에 들어간 것이 제일 먼저 나오는 구조의 자료구조입니다. 

값을 넣는 Push 와 값을 빼는 Pop 으로 이루어져 있습니다.

 

배열 스택과 링크드리스트 스택의 가장 큰 차이점이라면

배열 스택은 처음에 배열의 크기를 할당해서 사용하고

링크드 리스트는 값을 추가 하거나 뺄때마다 크기를 조절한다고 볼 수 있겠습니다.

 

2. 배열을 이용한 스택 구현

 

class StackArray
{
private :
	int top;			//가장 위를 가르킨다.(값이 없으면 -1 첫번째 값은 0)
	int maxSize;			//배열 크기
	int* arrays;			//동적 할당할 배열
public:
	StackArray(int size = 10);	//생성자 (디폴트는 10)
	~StackArray();			//소멸자
	bool Push(int value);		//값을 넣는다
	bool Pop(int &value);		//값을 뺀다
	void Clear();			//모든 값을 비운다
	void PrintAll();		//모든 값을 출력한다.
};

배열 스택의 헤더 입니다.

생성자를 보시면 디폴트 값으로 10이 들어가 있습니다

이렇게 디폴트 값을 선언하면 생성할때 size 에 값을 넘겨주지 않으면 자동으로 10이 들어가게 됩니다.

Pop 에는 &value 가 들어가 있는데 어떤 문법인지 잘 모르시다면

아래 Call by reference 글을 읽고 오시면 될듯 합니다.

(C/C++) Call by value 와 Call by reference

 

#include "StackArray.h"
#include <stdio.h>

StackArray::StackArray(int size)
{
    printf("생성자\n");
    top = -1;					//top이 음수면 스택이 비어있다.
    maxSize = size;				//size를 정해준다
    arrays = new int[maxSize];			//배열 동적 할당
    printf("max %d\n", maxSize);
}

StackArray::~StackArray()
{
    delete[] arrays;				//배열로 동적할당 했기 때문에 delete[]
    printf("소멸자\n");
}

bool StackArray::Push(int value)
{
    if (top >= maxSize -1)			//스택이 꽉차있으면
        return false;

    *(arrays + ++top) = value;			//arrays[++top] 와 같습니다.
    printf("push %d\n",value);
    return true;
}

bool StackArray::Pop(int &value)
{
    if (top < 0)				//스택이 비어있으면
        return false;

    value = *(arrays + top--);			//arrays[top--]와 같습니다.
    printf("pop %d\n", value);
    return true;
}

void StackArray::Clear()
{
    top = -1;					//top을 -1로 하면 끝난다.
	printf("Clear\n");
}

void StackArray::PrintAll()
{
    for (int i = 0; i <= top; i++)
    {
        printf("%d \t", *(arrays + i));
    }
    printf("\n");
}

배열 스택의 CPP 입니다.

*(arrays + temp) 와 arrays[temp] 는 같습니다!

즉 둘이 바꿔서 적용해도 내용에는 차이가 없습니다.

포인터와 배열에 대해서 포스팅할 기회가 있으면 좋겠네요!

 

Clear 를 보시면 단순히 top 을 -1 로만 바꿔주는데

배열은 미리 메모리를 잡아 놓고 그 범위 안에서 사용하기 때문에

따로 메모리를 지울 필요가 없어서 그렇습니다.

 

#include "StackArray.h"

int main()
{
	StackArray* arrayStack = new StackArray(2);

	arrayStack->Push(1);
	arrayStack->Push(2);
	arrayStack->Push(3);
	arrayStack->PrintAll();

	int temp;
	arrayStack->Pop(temp);
	arrayStack->Pop(temp);
	arrayStack->Pop(temp);

	arrayStack->Push(4);
	arrayStack->Push(5);
	arrayStack->Push(6);
	arrayStack->PrintAll();

	arrayStack->Clear();
	arrayStack->PrintAll();
	delete arrayStack;
}

배열 스택 결과

 

동적할당 할때 크기를 2로 지정 했기 때문에

크기를 벗어나는 값들은 반영 안되는 것을 볼 수 있습니다.

위에서도 말씀 드렸지만

만약 new StackArray() 를 했으면 배열의 크기가 10이 되겠죠!

배열이기 때문에 새로운 값이 들어오면 가장 뒤에 값이 추가 되고

PrintAll 함수를 보시면 먼저 들어간 순서대로 출력하고 있습니다.

 

3. 링크드리스트를 이용한 스택 구현

 

링크드리스트 스택은 단일연결 리스트를 사용하여 구현하였습니다.

넣는 위치, 빼는 위치가 모두 맨 위(뒤) 로 고정되어있기 때문입니다!

아래에 C로 구현한 링크드리스트를 보고 오시면 도움이 될듯 합니다.

(C) 자료구조 - 단일 연결 리스트(Singly Linked List)

 

class StackLinkedList
{
	struct Node			//노드
	{
		int data;
		Node* next;
	};

private:
	Node* head;			//머리노드(더미)
	Node* tail;			//꼬리노드(더미)

public:
	StackLinkedList();		//생성자 (링크드리스트는 크기를 정하지 않는다.)
	~StackLinkedList();		//소멸자
	bool Push(int value);		//값을 넣는다.
	bool Pop(int& value);		//값을 뺸다.
	void Clear();			//모든 값을 지운다.	
	void PrintAll();		//모든 값을 출력한다.
};

링크드리스트 스택의 헤더입니다.

 

머리노드와 꼬리노드 는 더미 노드 입니다.

배열과는 다르게 크기를 지정하지 않습니다.

링크드리스트 특성상 그떄그때 크기를 늘리고 줄이고 하니까요!

 

#include "StackLinkedList.h"
#include <stdio.h>

StackLinkedList::StackLinkedList()
{
	printf("생성자\n");
	head = new Node();			//머리 노드 할당
	tail = new Node();			//꼬리 노드 할당
	head->next = tail;			//머리 다음은 꼬리
	tail->next = tail;			//꼬리 다음도 꼬리
}

StackLinkedList::~StackLinkedList()
{
	Clear();				//안에있는 노드들을 다 비워주고
	delete head;				//머리 삭제
	delete tail;				//꼬리 삭제
	printf("소멸자\n");
}

bool StackLinkedList::Push(int value)
{
	Node* newNode = new Node();		//노드를 만들고
	newNode->data = value;			//값을 넣어준다.
	newNode->next = head->next;		//머리가 가르키던 값을 가르킨다.
	head->next = newNode;			//머리 다음으로 넣어준다.

	printf("push %d\n", value);
	return true;
}

bool StackLinkedList::Pop(int& value)
{
	if (head->next == tail)			//스택이 비어있으면
		return false;

	Node* deleteNode = head->next;		//맨위에 있는 노드 찾기
	value = deleteNode->data;		//맨위에 있는 값 반환
	head->next = deleteNode->next;		//머리 다음은 맨위 다음을 가르킨다.

	printf("pop %d\n", value);		
	delete deleteNode;			//맨위 노드 삭제
	return true;
}

void StackLinkedList::Clear()
{
	Node* temp = head->next;		//순회할 노드.
	Node* deleteNode;			//지울 노드 값을 저장할 변수 노드
	while (temp != tail)			//스택 끝까지 돈다.
	{
		deleteNode = temp;		//지울 노드 저장
		temp = temp->next;		//순회 노드는 다음 노드를 가르킨다.
		delete deleteNode;		//지울 노드 삭제
	}
	head->next = tail;			//다 지웠으면 머리는 꼬리를 가르킨다.

	printf("Clear\n");
}

void StackLinkedList::PrintAll()
{
	Node* temp = head->next;		
	while (temp != tail)
	{
		printf("%d\t", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

 

기본적으로 C 로 구현한 단일링크드리스트 글에 개념이 다 들어있으니 건너뛰고

Clear를 살펴보도록 하겠습니다.

배열과는 다르게 Clear 함수에서 모든 노드를 지우고 있습니다.

head -> next = tail;

이렇게 값을 넣어주면

중간에 있던 노드들이 메모리에서 해제되지 않아서 메모리의 낭비가 생기기 떄문입니다.

그래서 소멸자에서도 Clear 를 해주고 있습니다.

 

#include "StackLinkedList.h"

int main()
{
	StackLinkedList* LinkedStack = new StackLinkedList();
	LinkedStack->Push(1);
	LinkedStack->Push(2);
	LinkedStack->Push(3);
	LinkedStack->PrintAll();

	int temp;
	LinkedStack->Pop(temp);
	LinkedStack->Pop(temp);
	LinkedStack->Pop(temp);
	LinkedStack->Pop(temp);
	LinkedStack->PrintAll();

	LinkedStack->Push(4);
	LinkedStack->Push(5);
	LinkedStack->PrintAll();

	LinkedStack->Clear();
	LinkedStack->Push(6);
	LinkedStack->Push(7);
	LinkedStack->PrintAll();

	delete LinkedStack;
}

링크드리스트 스택 결과

 

범위를 벗어난 Pop 은 적용이 되지 않는 것을 볼 수 있네요.

delete 했을때 Clear 도 잘 작동하는 것을 볼 수 있습니다.

배열과는 다르게 head 노드 다음으로 값을 Push 했기 때문에

마지막에 들어온 값이 Head 앞에 있고 마지막 값부터 차례대로 출력되는 것을 볼 수 있습니다!

 

감사합니다!

 

 

다른 자료구조

단일 연결 리스트(Singly Linked List)

이중 연결 리스트(Doubly Linked List)

스택(Stack) - 배열(Array), 링크드리스트(Linked List)

큐(Queue) - 배열(Array), 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)