임진규의 Devlog

Jinkyu's Devlog

0%

Stack / Queue / Deque

작성일 Edited on In , Disqus:
Symbols count in article: 728 Reading time ≈ 3 mins.

스택 (Stack)

스택은 LIFO (Last In First Out)의 구조를 가진다.
가장 마지막에 Push 된 Node가 POP연산시 가장 먼저 나오는 구조이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#pragma once

typedef struct Node
{
	int data;
	struct Node* Next;
}Node;

typedef struct LinkedList
{
	struct Node* head; // HEAD를 가르키는 Node 포인터 변수
	int numdata;
};

void Initialize(LinkedList* plist)
{
	plist->head = NULL;
	plist->numdata = 0;
}

void Push(LinkedList* plist, int data)
{
	Node* nNode = (Node*)malloc(sizeof(Node));
	nNode->data = data;
	if (plist->head != NULL)
	{
		nNode->Next = plist->head;
		plist->head = nNode;
	}
	else
	{
		plist->head = nNode;
		nNode->Next = NULL;
	}
	plist->numdata++;
}


void POP(LinkedList* plist)
{
	Node* next = plist->head->Next;
	printf("%d ", plist->head->data);
	free(plist->head);
	plist->head = next;
	plist->numdata--;
}

void Peek(LinkedList* plist,int index)
{
	Node* pNode = plist->head;
	if (index > plist->numdata)
		return;
	for (int i = 0; i < index-1; i++)
		pNode = pNode->Next;
	printf("\nPeek : %d", pNode->data);
}

void Printall(LinkedList* plist)
{
	Node* head = plist->head;
	printf("\n\n");
	for(int i=0;i<plist->numdata;i++)
	{
		printf("%d", head->data);
		head = head->Next;
	}
}

int main()
{
	LinkedList Stack;
	Initialize(&Stack);
	Push(&Stack, 1);
	Push(&Stack, 2);
	Push(&Stack, 3);
	Push(&Stack, 4);
	Push(&Stack, 5);
	POP(&Stack);
	POP(&Stack);
	POP(&Stack);
	Push(&Stack, 1);
	Push(&Stack, 2);
	Push(&Stack, 3);
	POP(&Stack);


	Printall(&Stack);
	Peek(&Stack, 0);
}

큐 (Queue)

큐는 FIFO ( First in First Out)의 구조를 가진다.
가장 처음에 Push된 Node가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#pragma once

typedef struct Node
{
	int data;
	struct Node* Next;
}Node;

typedef struct LinkedList
{
	struct Node* head; // HEAD를 가르키는 Node 포인터 변수
	struct Node* tail; // HEAD를 가르키는 Node 포인터 변수
	int numdata;
};

void Initialize(LinkedList* plist)
{
	plist->head = NULL;
	plist->tail = NULL;
	plist->numdata = 0;
}

void EnQueue(LinkedList* plist, int data)
{
	Node* nNode = (Node*)malloc(sizeof(Node));
	nNode->data = data;
	if (plist->head == NULL)
	{
		nNode->Next = plist->head;
		plist->head = nNode;
		plist->tail = nNode;
	}
	else
	{
		plist->tail->Next = nNode;
		plist->tail = nNode;
		nNode->Next = NULL;
	}
	plist->numdata++;
}


void DeQueue(LinkedList* plist)
{
	Node* next = plist->head->Next;
	printf("%d ", plist->head->data);
	free(plist->head);
	plist->head = next;
	plist->numdata--;
}

void Peek(LinkedList* plist,int index)
{
	Node* pNode = plist->head;
	if (index > plist->numdata)
		return;
	for (int i = 0; i < index-1; i++)
		pNode = pNode->Next;
	printf("\nPeek : %d", pNode->data);
}

void Printall(LinkedList* plist)
{
	Node* head = plist->head;
	printf("\n\n");
	for(int i=0;i<plist->numdata;i++)
	{
		printf("%d", head->data);
		head = head->Next;
	}
}

int main()
{
	LinkedList Stack;
	Initialize(&Stack);
	EnQueue(&Stack, 1);
	EnQueue(&Stack, 2);
	EnQueue(&Stack, 3);
	EnQueue(&Stack, 4);
	EnQueue(&Stack, 5);
	DeQueue(&Stack);
	DeQueue(&Stack);
	DeQueue(&Stack);
	EnQueue(&Stack, 1);
	EnQueue(&Stack, 2);
	EnQueue(&Stack, 3);
	DeQueue(&Stack);
	Printall(&Stack);
	Peek(&Stack, 0);
}

덱 (Deque)

덱는 Front, Rear에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#pragma once

typedef struct Node
{
	int data;
	struct Node* Next;
	struct Node* Prev;
}Node;

typedef struct LinkedList
{
	struct Node* head; // HEAD를 가르키는 Node 포인터 변수
	struct Node* tail; // HEAD를 가르키는 Node 포인터 변수
	int numdata;
};

void Initialize(LinkedList* plist)
{
	plist->head = NULL;
	plist->tail = NULL;
	plist->numdata = 0;
}

void DequeInsert(LinkedList* plist,int type, int data)
{
	Node* nNode = (Node*)malloc(sizeof(Node));
	nNode->data = data;
	if (plist->head == NULL && plist->tail == NULL)
	{
		plist->head = nNode;
		plist->tail = nNode;
	}
	if (type == 0) // Insert Front
	{
		nNode->Next = plist->head;
		plist->head->Prev = nNode;
		plist->head = nNode;
	}// Insert Rear
	else
	{
		plist->tail->Next = nNode;
		nNode->Prev = plist->tail;
		plist->tail = nNode;
	}
	plist->numdata++;
}

void DequeDeleteF(LinkedList* plist)
{
	Node* next = plist->head->Next;
	printf("%d ", plist->head->data);
	free(plist->head);
	plist->head = next;
	plist->numdata--;
}

void DequeDeleteR(LinkedList* plist)
{
	Node* Prev = plist->tail->Prev;
	printf("%d ", plist->tail->data);
	free(plist->tail);
	plist->tail = Prev;
	plist->numdata--;
}

void Peek(LinkedList* plist,int index)
{
	Node* pNode = plist->head;
	if (index > plist->numdata)
		return;
	for (int i = 0; i < index-1; i++)
		pNode = pNode->Next;
	printf("\nPeek : %d", pNode->data);
}

void Printall(LinkedList* plist)
{
	Node* head = plist->head;
	printf("\n\n");
	for(int i=0;i<plist->numdata;i++)
	{
		printf("%d ", head->data);
		head = head->Next;
	}
}

int main()
{
	LinkedList Stack;
	Initialize(&Stack);
	DequeInsert(&Stack,0,1);//front
	DequeInsert(&Stack,0,2);//front
	DequeInsert(&Stack,0,3);//front
	DequeInsert(&Stack,0,4);//front
	DequeDeleteR(&Stack);
	DequeDeleteR(&Stack);
	DequeDeleteR(&Stack);
	DequeInsert(&Stack,0,5);//front
	DequeInsert(&Stack,1,1);//Rear
	DequeInsert(&Stack,1,2);//Rear
	DequeInsert(&Stack,1,3);//Rear
	DequeDeleteF(&Stack);
	Printall(&Stack);
	Peek(&Stack, 0);
}