[자료구조] 스택(Stack) - C/C++

 

< 스택 >

- 선형구조로 자료를 차례대로 저장하고, LIFO(Last In First Out = 후입선출)의 특성을 가진다.

- 자료의 추가/반환이 스택의 끝에서만 가능한 제약 사항으로 인해 리스트 자료구조와 구별되는 독특한 특성을 가진다.

 

< 스택 자료> * 본 게시물에서의 스택은 이중연결리스트(Double Linked List)로 구현하였다.

 

1. 노드 : 자료구조에 저장할 데이터를 가진 각각의 원소들을 구조체 Node로 선언한다.  

- 기존 이중연결리스트와 동일한 형태로 구성된다.

typedef struct Node {
	Node *rlink;
	Node *llink;
	void *data;
} Node;

 

2. 스택 : 구조체 Stack을 선언한다.

- 기존 이중연결리스트와 동일하되, 특별히 top이라는 노드 포인터가 추가된다.

- top : 가장 최근에 스택에 삽입된 노드를 가리키는 역할

         (스택은 끝에서만 자료의 추가/반환을 하므로, 끝을 알기 위해 top을 추가한다.)

typedef struct Stack {
	Node *head;
	Node *tail;
	int length;
	int datasize;
	Node *top;
} Stack;

 

< 스택 연산 >

1. createStack : 원하는 자료형의 데이터를 담은 노드를 저장할 수 있는 스택을 생성

  1-1. DoubleLinkedStack.c  - malloc함수를 사용하기 위해서 stdlib.h를 추가해야 함

void createStack(Stack *stack, int datasize)
{
	Node *headNode, *tailNode;
               
	headNode = (Node *)malloc(sizeof(Node)); 
	tailNode = (Node *)malloc(sizeof(Node));

	headNode->rlink = headNode;
	headNode->llink = tailNode;
	headNode->data = NULL;

	tailNode->rlink = tailNode;
	tailNode->llink = headNode;
	tailNode->data = NULL;

	stack->head = headNode;
	stack->tail = tailNode;
	stack->length = 0;
	stack->datasize = datasize;
	stack->top = headNode;
}

 1-2. test.c  - main 함수에서 createStack을 호출하기 위해서는 mystack을 동적할당한 후 인자로 넘겨주어야 한다

int main() {
	Stack *mystack = (Stack *)malloc(sizeof(Stack));
	createStack(mystack, sizeof(int));
}

 

2. deleteStack : 스택 제거(메모리 해제)

- 스택 내의 모든 노드들을 Pop연산으로 제거한 뒤, headNode와 tailNode, stack 구조체까지 제거한다.

 2-1. DoubleLinkedStack.c

void deleteStack(Stack *stack)
{
	void *popData = malloc(sizeof(stack->datasize));
	while (stack->pop(stack, popData))
		;
	free(popData);
	free(stack->head);
	free(stack->tail);
	free(stack);
}

 

3. Push : 스택의 top 위치에 새로운 노드를 추가

- Node를 생성한 뒤, Node의 llink를 top으로, rlink를 tail로 가리키도록 한다.

- top을 현재 추가된 Node로 가리키도록 한다.

- length를 증가시킨다.

  3-1. DoubleLinkedStack.c - memcpy함수를 사용하기 위해 memory.h를 추가해야 함

void push(Stack *stack, void *data)
{
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->data = malloc(stack->datasize);
	memcpy(newNode->data, (char *)data, stack->datasize);

	stack->top->rlink = newNode;
	stack->tail->llink = newNode;
	newNode->llink = stack->top;
	newNode->rlink = stack->tail;
	
	stack->top = newNode;
	stack->length++;
}

 

4. Pop : 스택의 top 위치에 있는 노드를 제거한 뒤 데이터를 인자에 복사. 성공 여부를 반환

- Pop연산이 실행되면 TRUE, Underflow가 발생하면(=공백 상태의 스택일 때) FALSE를 반환

  → Top이 headNode와 같으면 Underflow이다.

- Pop연산이 이루어지면 popData에 데이터의 메모리 영역이 복사된다.

  4-1. DoubleLinkedStack.c

int pop(Stack *stack, void *popData)
{
	if (stack->top != stack->head) 
	{
		Node *popNode;
		popNode = stack->top;

		memcpy(popData, popNode->data, stack->datasize);

		stack->top = popNode->llink;
		stack->length--;

		popNode->llink->rlink = popNode->rlink;
		popNode->rlink->llink = popNode->llink;
		free(popNode->data);
		free(popNode);

		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

 

5. Peak : 스택의 top 위치에 있는 데이터를 인자에 복사. 성공여부를 반환 (스택에서 제거하지는 않음)

  5-1. DoubleLinkedStack.c

int peak(Stack *stack, void *peakData)
{
	if (stack->top != stack->head)
	{
		memcpy(peakData, stack->top->data, stack->datasize);
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

 

※ 전체 소스 GitHub : https://github.com/waves123/DoubleLinkedStack

 

 

자료구조 더보기

2017/07/23 - [자료구조] - [자료구조] 배열로 구현한 원형 큐(Circular Queue) - C/C++

2017/07/20 - [자료구조] - [자료구조] 연결리스트로 구현한 큐(Linked Queue) - C/C++

2017/07/15 - [자료구조] - [자료구조] 스택(Stack) - C/C++

2017/07/02 - [자료구조] - [자료구조] 연결리스트(Linked List) - C언어