07장 덱(Deque) – 연결리스트(LinkedList)를 이용한

Posted on: 2019년 03월 31일 2019년 03월 31일
Categories: 강의자료, 자료구조

연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #1 :S007_Deque.c

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
	int data;
	struct _node * next;
	struct _node * prev;
} Node;

Node *head = NULL;
Node *tail = NULL;

void main(int argc, char* argv[]){
}

#include <stdio.h>

#include <stdlib.h>

typedef struct _node{

int data;

struct _node * next;

struct _node * prev;

} Node;

Node *head = NULL;

Node *tail = NULL;

void main(int argc, char* argv[]){

}

연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #2

void Free(){ Node *cur; while(head != NULL){ cur = head; head = head->next; free(cur); } } void main(int argc, char* argv[]){ Free(); }

1
2
3
4
5
6
7
8
9
10
11
12
13

void Free(){
Node *cur;

while(head != NULL){
cur = head;
head = head->next;
free(cur);
}
}

void main(int argc, char* argv[]){
Free();
}

연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #3

void AddFirst(int data){
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = head;
	newNode->prev = NULL;
	if(head == NULL){		//비어있다면
		tail = newNode;
	}
	else{
		head->prev = newNode;
	}
	head = newNode;
}

void AddLast(int data){
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = tail;
	if(head == NULL){		//비어있다면
		head = newNode;
	}
	else{
		tail->next = newNode;
	}
	tail = newNode;
}

void main(int argc, char* argv[]){
	AddFirst(1);
	AddLast(3);
	Free();
}

void AddFirst(int data){

Node *newNode = (Node *)malloc(sizeof(Node));

newNode->data = data;

newNode->next = head;

newNode->prev = NULL;

if(head == NULL){ //비어있다면

tail = newNode;

}

else{

head->prev = newNode;

}

head = newNode;

}

void AddLast(int data){

Node *newNode = (Node *)malloc(sizeof(Node));

newNode->data = data;

newNode->next = NULL;

newNode->prev = tail;

if(head == NULL){ //비어있다면

head = newNode;

}

else{

tail->next = newNode;

}

tail = newNode;

}

void main(int argc, char* argv[]){

AddFirst(1);

AddLast(3);

Free();

}

연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #4

void printDeque(){
	Node *cur = head;
	while(cur != NULL){
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n\n");
}

void main(int argc, char* argv[]){
	AddFirst(1);	printDeque();
	AddFirst(3);	printDeque();
	AddLast(5);		printDeque();
	AddLast(7);		printDeque();
	Free();
}

void printDeque(){

Node *cur = head;

while(cur != NULL){

printf("%d ", cur->data);

cur = cur->next;

}

printf("\n\n");

}

void main(int argc, char* argv[]){

AddFirst(1); printDeque();

AddFirst(3); printDeque();

AddLast(5); printDeque();

AddLast(7); printDeque();

Free();

}

연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #5

int RemoveFirst(){
	int data = -1;
	if(head == NULL){
		printf("Empty\n");
	}
	else{
		Node *cur = head;
		data = cur->data;
		head = cur->next;
		free(cur);
	}

	if(head == NULL){
		tail = NULL;
	}
	else{
		head->prev = NULL;
	}
	return data;
}

int RemoveLast(){
	int data = -1;
	if(head == NULL){
		printf("Empty\n");
	}
	else{
		Node *cur = tail;
		data = cur->data;
		tail = cur->prev;
		free(cur);
	}

	if(tail == NULL){
		head = NULL;
	}
	else{
		tail->next = NULL;
	}
	return data;
}

void main(int argc, char* argv[]){
	AddFirst(1);	printDeque();
	AddFirst(3);	printDeque();
	AddLast(5);		printDeque();
	AddLast(7);		printDeque();
	AddFirst(9);	printDeque();
	AddLast(11);	printDeque();
	printf("POP_First : %d\n", RemoveFirst());	printDeque();
	printf("POP_Last  : %d\n", RemoveLast());	printDeque();

	Free();
}

int RemoveFirst(){

int data = -1;

if(head == NULL){

printf("Empty\n");

}

else{

Node *cur = head;

data = cur->data;

head = cur->next;

free(cur);

}

if(head == NULL){

tail = NULL;

}

else{

head->prev = NULL;

}

return data;

}

int RemoveLast(){

int data = -1;

if(head == NULL){

printf("Empty\n");

}

else{

Node *cur = tail;

data = cur->data;

tail = cur->prev;

free(cur);

}

if(tail == NULL){

head = NULL;

}

else{

tail->next = NULL;

}

return data;

}

void main(int argc, char* argv[]){

AddFirst(1); printDeque();

AddFirst(3); printDeque();

AddLast(5); printDeque();

AddLast(7); printDeque();

AddFirst(9); printDeque();

AddLast(11); printDeque();

printf("POP_First : %d\n", RemoveFirst()); printDeque();

printf("POP_Last : %d\n", RemoveLast()); printDeque();

Free();

}

연결리스트(LinkedList)를 이용한 덱(Deque) #6

int peekFirst(){
	if(head == NULL){
		printf("Empty\n");
		return -1;
	}
	else{
		return head->data;
	}
}

int peekLast(){
	if(head == NULL){
		printf("Empty\n");
		return -1;
	}
	else{
		return tail->data;
	}
}

void main(int argc, char* argv[]){
	AddFirst(1);	printDeque();
	AddFirst(3);	printDeque();
	AddLast(5);		printDeque();
	AddLast(7);		printDeque();
	AddFirst(9);	printDeque();
	AddLast(11);	printDeque();
	printf("PEEK_First : %d\n", peekFirst());	printDeque();
	printf("POP_First : %d\n", RemoveFirst());	printDeque();
	printf("POP_Last  : %d\n", RemoveLast());	printDeque();
}

int peekFirst(){

if(head == NULL){

printf("Empty\n");

return -1;

}

else{

return head->data;

}

int peekLast(){

if(head == NULL){

printf("Empty\n");

return -1;

}

else{

return tail->data;

}

void main(int argc, char* argv[]){

AddFirst(1); printDeque();

AddFirst(3); printDeque();

AddLast(5); printDeque();

AddLast(7); printDeque();

AddFirst(9); printDeque();

AddLast(11); printDeque();

printf("PEEK_First : %d\n", peekFirst()); printDeque();

printf("POP_First : %d\n", RemoveFirst()); printDeque();

printf("POP_Last : %d\n", RemoveLast()); printDeque();

}

연결리스트(LinkedList)를 이용한 덱(Deque) 완성 버전

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
	int data;
	struct _node * next;
	struct _node * prev;
} Node;

Node *head = NULL;
Node *tail = NULL;

////// Deque의 기본함수 Add/Push/EnQueu(), Remove/Pop/Dequeue(), Peek()

void AddFirst(int data){
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = head;
	newNode->prev = NULL;
	if(head == NULL){		//비어있다면
		tail = newNode;
	}
	else{
		head->prev = newNode;
	}
	head = newNode;
}

void AddLast(int data){
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = tail;
	if(head == NULL){		//비어있다면
		head = newNode;
	}
	else{
		tail->next = newNode;
	}
	tail = newNode;
}

int RemoveFirst(){
	int data = -1;
	if(head == NULL){
		printf("Empty\n");
	}
	else{
		Node *cur = head;
		data = cur->data;
		head = cur->next;
		free(cur);
	}

	if(head == NULL){
		tail = NULL;
	}
	else{
		head->prev = NULL;
	}
	return data;
}

int RemoveLast(){
	int data = -1;
	if(head == NULL){
		printf("Empty\n");
	}
	else{
		Node *cur = tail;
		data = cur->data;
		tail = cur->prev;
		free(cur);
	}

	if(tail == NULL){
		head = NULL;
	}
	else{
		tail->next = NULL;
	}
	return data;
}

int peekFirst(){
	if(head == NULL){
		printf("Empty\n");
		return -1;
	}
	else{
		return head->data;
	}
}

int peekLast(){
	if(head == NULL){
		printf("Empty\n");
		return -1;
	}
	else{
		return tail->data;
	}
}

////////// stack 추가 함수

void initDeque(){
	head = NULL;
	tail = NULL;
}

int isEmpty(){
	if(head == NULL){
		return 1;	//true
	}
	else{
		return 0;	//false
	}
}

int isFull(){} //존재할 필요가 없음

void printDeque(){
	Node *cur = head;
	while(cur != NULL){
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n\n");
}

void Free(){
	Node *cur;

	while(head != NULL){
		cur = head;
		head = head->next;
		free(cur);
	}
}

///////// 메인 함수
void main(){
	AddFirst(1);	printDeque();
	AddFirst(3);	printDeque();
	AddLast(5);		printDeque();
	AddLast(7);		printDeque();
	AddFirst(9);	printDeque();
	AddLast(11);	printDeque();
	printf("PEEK_First : %d\n", peekFirst());	printDeque();
	printf("POP_First : %d\n", RemoveFirst());	printDeque();
	printf("POP_Last  : %d\n", RemoveLast());	printDeque();
	AddFirst(13);	printDeque();
	AddLast(15);	printDeque();
	printf("POP_First  : %d\n", RemoveFirst());	printDeque();
	printf("PEEK_Last : %d\n", peekLast());		printDeque();
	printf("POP_First  : %d\n", RemoveFirst());	printDeque();
	printf("POP_Last  : %d\n", RemoveLast());	printDeque();
	printf("POP_Last  : %d\n", RemoveLast());	printDeque();
	Free();
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

#include <stdio.h>

#include <stdlib.h>

typedef struct _node{

int data;

struct _node * next;

struct _node * prev;

} Node;

Node *head = NULL;

Node *tail = NULL;

////// Deque의 기본함수 Add/Push/EnQueu(), Remove/Pop/Dequeue(), Peek()

void AddFirst(int data){

Node *newNode = (Node *)malloc(sizeof(Node));

newNode->data = data;

newNode->next = head;

newNode->prev = NULL;

if(head == NULL){ //비어있다면

tail = newNode;

}

else{

head->prev = newNode;

}

head = newNode;

}

void AddLast(int data){

Node *newNode = (Node *)malloc(sizeof(Node));

newNode->data = data;

newNode->next = NULL;

newNode->prev = tail;

if(head == NULL){ //비어있다면

head = newNode;

}

else{

tail->next = newNode;

}

tail = newNode;

}

int RemoveFirst(){

int data = -1;

if(head == NULL){

printf("Empty\n");

}

else{

Node *cur = head;

data = cur->data;

head = cur->next;

free(cur);

}

if(head == NULL){

tail = NULL;

}

else{

head->prev = NULL;

}

return data;

}

int RemoveLast(){

int data = -1;

if(head == NULL){

printf("Empty\n");

}

else{

Node *cur = tail;

data = cur->data;

tail = cur->prev;

free(cur);

}

if(tail == NULL){

head = NULL;

}

else{

tail->next = NULL;

}

return data;

}

int peekFirst(){

if(head == NULL){

printf("Empty\n");

return -1;

}

else{

return head->data;

}

int peekLast(){

if(head == NULL){

printf("Empty\n");

return -1;

}

else{

return tail->data;

}

////////// stack 추가 함수

void initDeque(){

head = NULL;

tail = NULL;

}

int isEmpty(){

if(head == NULL){

return 1; //true

}

else{

return 0; //false

}

int isFull(){} //존재할 필요가 없음

void printDeque(){

Node *cur = head;

while(cur != NULL){

printf("%d ", cur->data);

cur = cur->next;

}

printf("\n\n");

}

void Free(){

Node *cur;

while(head != NULL){

cur = head;

head = head->next;

free(cur);

}

///////// 메인 함수

void main(){

AddFirst(1); printDeque();

AddFirst(3); printDeque();

AddLast(5); printDeque();

AddLast(7); printDeque();

AddFirst(9); printDeque();

AddLast(11); printDeque();

printf("PEEK_First : %d\n", peekFirst()); printDeque();

printf("POP_First : %d\n", RemoveFirst()); printDeque();

printf("POP_Last : %d\n", RemoveLast()); printDeque();

AddFirst(13); printDeque();

AddLast(15); printDeque();

printf("POP_First : %d\n", RemoveFirst()); printDeque();

printf("PEEK_Last : %d\n", peekLast()); printDeque();

printf("POP_First : %d\n", RemoveFirst()); printDeque();

printf("POP_Last : %d\n", RemoveLast()); printDeque();

Free();

}

whan0623

517