/////단순 연결리스트로 스택 구현하기./////
/*
#include <stdio.h>
#include <memory.h>
typedef struct stackNode // 스택의 노드 구조 정의.
{
int data;
struct stackNode* link; // 스택의 순서=링크
}stackNode;
stackNode* top; // 전역변수로 스택의 top노드를 지정하기 위해 포인터 top 사용, 초기값은 NULL
void push(int data)
{
stackNode* tmp=(stackNode*)malloc(sizeof(stackNode)); // 스택 하나하나 메모리 할당.
tmp->data= data;
tmp->link=top;
top=tmp;// 새로 삽입하는 노드가 스택의 top노드 되도록.
}
int pop() // 스택 삭제 후 삭제된 노드의 원소 반환. 1개씩.
{
int data;
stackNode* tmp=top; // 삭제할 노드 가리키기 하기
if(top==NULL) return 0; // 스택이 공백 되면 끝
else
{
data= tmp->data;
top=tmp->link; // top위치는 이제 삭제할 노드의 바로 아래 노드.
free(tmp);
return data;
}
}
int peek() // 스택의 탑노드 원소만 검색하기.
{
int data;
if(top==NULL) return 0;
else
{
data= top->data;
return data;
}
}
void del() // 스택 삭제하기.
{
stackNode* tmp;
if(top!=NULL)
{
tmp=top; // 마지막 노드로 지정.
top=tmp->link; // 탑노드 아래의 노드가 새로운 탑
free(tmp);
}
}
void view()
{
stackNode* p= top;
while(top!=NULL)
{
printf("%d ", p->data);
p=p->link; // 계속 다음 노드로 연결.
}
printf("\n");
}
int main()
{
int data, a, b;
top=NULL; // 초기값 지정.
push(1);
push(2);
push(3);
push(4);
del();
printf("%d ", pop());
printf("%d", peek());
//view();
}
[정리]
malloc으로 스택 만들 것.
-단순연결리스트: 스택의 원소=노드// 스택의 순서=링크
스택의 top노드를 지정하기 위해 포인터 top 사용
초기 상태는 포인터 top 선언 포인터 top 초기값은 NULL이 됨.
스택 쌓을 때마다 노드 연결하기
1. stackNode 구조체 만들고, 전역변수 stackNode* top 생성
2. void push(data) 스택의 원소 A를 노드에 넣고. tmp->link=top; 지정 top=temp; 하기.
3. int pop() 스택의 제일 마지막 원소 빠지면서 삭제된 노드의 원소 반환// top!=NULL일 때까지만.
4. int search() 스택의 top노드 원소 찾기// main 함수에서 a=search();하기
5. void del() 스택 삭제// push와 달리 return data; 안함. 다만 tmp=top; top=tmp->link; free(tmp); 해서 탑노드 아래의 노드가 새로운 탑 되게 하기
6. void view() 스택 내용 보기// p라는 스택노드를 탑 노드로 지정. 그리고 top이 NULL이 아닐 동안 탑위치의 data 계속 보여주고, p=p->link해서 다음 노드 연결.
*/
/*
/////단순 연결리스트 큐 구현하기./////
FIFO
노드==큐
첫 번째 노드==front 포인터/// 마지막 노드==rear 포인터
--> 이것도 구조체로 지정해야 함!!
!!초기에는 front, rear 포인터 모두 NULL값
연결 큐가 공백이면(노드가 없음) front==NULL인 상태.
#include <stdio.h>
#include <memory.h>
/*
struct Q// 이러면 이후 무조건 번거롭게 struct Q로 지칭해야 함.
{
int data;
struct Qnode *link;
};
*/
/*
typedef struct Q// 이름은 struct Q인데 typedef를 씀으로써 아래의 별칭 사용 가능.
{
int data;
struct Q *link;
}QNode;// 그 별칭이 Qnode. 이후로는 다 QNode로 하면 됨.
typedef struct
{
// struct Q *front, *rear;
QNode *front, *rear; //첫 번째 노드==front 포인터,,,마지막 노드==rear 포인터가 가리킴.
} LQueueType;
LQueueType *linkQueue() // 공백인 상태에서 새 연결 큐 만들기
{
LQueueType *LQ;
LQ=(LQueueType *)malloc(sizeof(LQueueType));
LQ->front=NULL; // !!초기에는 front, rear 포인터 모두 NULL값 지정. (즉 NULL 노드)
LQ->rear=NULL;
return LQ;
}
void enqueue(LQueueType *LQ, int data)
{
QNode *newNode=(QNode *)malloc(sizeof(QNode)); // 삽입할 새 노드.
newNode->data=data;
newNode->link=NULL; // 이게 연결 큐의 마지막 노드라는 것을 알려줘야 함.
if(LQ->front==NULL) // 삽입 전 기존 연결 큐가 공백인 경우(front가 가리키는 노드가 공백)
{
LQ->front=newNode; // !!새 노드가 첫 노드이자 마지막 노드. 포인터 front, rear가 이 새 노드 가리키도록.
LQ->rear=newNode;
}
else
{
LQ->rear->link=newNode; // 기존 rear가 가리키는 노드의 다음 노드로서 newNode가 온다.
LQ->rear=newNode; // '포인터' rear가 newNode 가리키도록 하기.
}
}
int dequeue(LQueueType *LQ)// front의 원소 삭제하고, 원소 반환하기.
{
QNode *old= LQ->front;// old라는 포인터가 front포인터가 가리키는 노드(LQ->front)를 가리키도록 하기.
int data;
if(LQ->front==NULL) return 0;// 기존 큐가 공백이면 안됨.
else
{
data=old->data;
LQ->front=LQ->front->link; // front 포인터 노드의 다음 노드가 새로운 front 되도록.
if(LQ->front==NULL) // 공백 되었을 시.
{
LQ->rear=NULL; // 이제 아무것도 큐에 안 남음. 마지막 노드도 NULL
}
free(old);
return data;
}
}
int del(LQueueType *LQ) // 큐의 front원소만 삭제하기.
{
QNode *old= LQ->front;
if(LQ->front==NULL) return 0;
else
{
LQ->front=LQ->front->link;
if(LQ->front==NULL) // 공백 됨.
{
LQ->rear=NULL; // 이제 아무것도 큐에 안 남음.
}
}
free(old);
return 1;
}
int peek(LQueueType *LQ) // front 원소만 검색해서 반환
{
int data;
if(LQ->front==NULL) return 0;
else
{
data=LQ->front->data; // data= front가 가리키는 노드의 data에 지정된 것.
return data;
}
}
void view(LQueueType *LQ)
{
QNode *tmp=LQ->front;
while(LQ->front!=NULL)// rear을 대신 써도 나옴.
{
printf("%d ", tmp->data);
tmp=tmp->link;
}
printf("\n");
}
int main()
{
LQueueType *NQ= linkQueue(); // 공백 큐 생성.
int data;
enqueue(NQ, 1);
enqueue(NQ, 2);
enqueue(NQ, 3);
enqueue(NQ, 4);
//del(NQ);
//printf("%d ", dequeue(NQ));
//printf("%d ", peek(NQ));
view(NQ);
}
*/
/*
1. newQueue() 연결 큐 생성하기: malloc으로 메모리 할당, front, rear NULL로
--> 이때 연결 큐가 공백이면(노드가 없음) front==NULL인 상태.
2. void enqueue(큐, data) 연결 큐의 rear에 원소 삽입하기: 삽입할 새 노드 생성,
data 저장, 그리고 링크는 NULL 저장해야 이게 연결 큐의 마지막 노드가 될 수 있음.
새 노드 삽입 전에 기존 연결 큐가 공백인지 검사 필요.
왜? 기존이 공백이면 삽입하는 새 노드가 첫 노드이자 마지막 노드 되니까, 포인터 front와 rear가 모두 새 노드가 되도록 하기.
만약 기존 큐가 공백이 아니다? 그러면 새 노드가 rear '노드'의 다음 노드가 될 것이고, rear '포인터'는 새 노드를 가리킴
3. char/int dequeue(큐) 연결 큐의 front 삭제하고 그 원소 반환하기:
연결 큐가 절대 공백이 아닌 상태에서만 수행// old라는 포인터 지정(삭제용), front가 가리키는 노드를 old가 가리키게 하기.
그리고 front의 링크(다음 노드)가 front되도록 포인터 front 재설정.
근데 기존 큐가 한 개 뿐이면(front 다음 노드가 NULL) 삭제 시 공백이 되므로 포인터 rear를 NULL로 재설정.
마지막으로 free(old), return data;
4. int del(큐) 그냥 front 원소만 삭제하기: dequeue과정에서 return data; 만 안 하면 됨
5. char/int peek(큐) front 원소만 검색해서 반환: 공백큐가 아닌 경우에, return front->data하면 됨
6. void view(큐) 연결 큐 내용 보기: tmp 노드가 front 노드로 지정. 공백큐가 아닌 경우에 tmp노드의 data 반환, tmp=tmp->link하면 됨.
*/
숙제
- 프로그래머스 코딩테스트 --> 고득점 kit, 모든 문제들
- 프로그래머스 실력체크--> 스킬체크--> 레벨 1, 2