ㅇTL
Stack, queue 본문
** 갑자기 포인터 이해하기
그냥 포인터 = 변수의 주소를 저장. -> 해당 변수의 값 변경 가능 ! (그걸 위함)
포인터의 포인터 = 변수의 주소를 담고있는 포인터변수의 주소를 저장 -> 포인터변수안의 값 접근, 변경 가능 ! 포인터 변수안에는 변수의 주소가 저장되어 있음 -> 주소 변경 가능 = 해당 포인터 변수가 다른 주소를 가리키게 할 수 있다 !
-> 실습 스택 코드에서 push할 때 top노드의 이중포인터 사용하는것은
top은 첫번째 노드의 주소 가지고 있는데
push하면 첫번째 노드가 달라지므로 top이 다른 주소를 저장해야댐 !!
-> 걍 top의 값을 변경해줘야하니까 *한번 더붙임 !!
-> 걍 *을 붙이는 것은 해당 변수 내부의 값을 바꿔주기 위해서 하나 더 붙여준다고 생각하자 !! (변수의주소의주소..이렇게 복잡하게 생각x)
Stack
: 쌓는거 ~ 나중에 들어온게 먼저 나감.^^
함수는
-push() : 맨 위에 쌓는다
-pop() : 스택에서 자료를 꺼낸다, 그리고 반환!
-Top() : 스택의 현재 위치 자료에 접근한다 ( 젤 위에꺼에 접근 )
구현 -> 맨 앞에 topPointer을 둔다 ! (맨처음엔 암것도 담아주지 않음) -> Top->link로 첫 노드 접근하도록 함 !(암것도 x면 link=NULL)
코드 구현
1. linked list로 구현
얘는 Stack* top 이 바로 첫번째 노드의 주소 저장함 !
(첫번째 노드 빈노드 아님. 바로 top 이 첫번째 노드가 됨 ! (엄밀히 말하면 이 노드가 가리키는 노드. next는 절대아니고^^))
typedef struct Stack{
int data;
Stack* next;
}Stack;
int main(){
Stack* top=NULL;
}
// < push > //
//top노드(포인터)가 가리키는 거에 첫 노드 담는 경우
void push(Stack** top, int d){
Stack* node=malloc;
node->next=*top;
*top = node;
}
//첫노드 top엔 data 암것도 안담고 top의 next 노드가 첫노드인 경우
void push(Stack* top, data){
Stack* node=malloc;
node->next=top->next;
top->next=node;
}
// < pop > //
//top노드(포인터)가 가리키는 거에 첫 노드 담는 경우
Stack* pop(Stack* top){
Stack* node=*top;
*top=*top->next; (=node->next)
}
// 첫노드 암것도 안담고 next노드가 첫노드인 경우
Stack* pop(Stack* top){
Stack* node=top->next;
top->next=top->next->next;
return node;
}
2. array 로 구현
: 구조체에 arr을 저장한다. topOfStack은 top 인덱스를 가리킴 !
3 4 5 6(top인덱스) 이런식으로 저장됨
해당 인덱스의 다음인덱스가 담에들어오는 친구가 들어오는 곳이고 그게 top이됨
// 자료구조 정의
struct StackRecord{
int Capacity;
int TopOfStack;
int* arr;
}선언할 때는
StackRecord* S = malloc(sizeof(StackRecord));
S->arr=(int*)malloc(sizeof(int)*길이));
이러캐
* 함수들의 parameter은 포인터형 아님! 그냥 스택의 array에만 접근하면 되므로 그냥 Stack 하면 됨!
void MakeEmpty(Stack S){
//걍 top 인덱스를 -1로 해주면 되믕
S->TopOfStack=-1;
}
void push(Stack s, int data){
s->arr[++s->TopOfStack]=data;
} //걍 이렇게 하면 댐 !! easy
int Top(Stack s){
return s->arr[s->topOfStack];
}
void Pop(Stack s){
s->TopOfStack--;
} // 굳이 0이나 다른 값으로 배열 값을 바꾸지 않음 ! 어차피 탑 인덱스 전 애들만 접근하고 해당 인덱스만 중요하기 땜에 그냥 인덱스 -1만 해주면 됨!!Evaluation of expressions
• Parentheses Matching
- 왼쪽 괄호가 나왔을 때 스택에 쌓음
- 오른쪽 괄호 나오면 스택 봐서 그 괄호에 해당하는 왼쪽 괄호 잇으면 pop시킴 !
-> 결국 스텍 비게됨!
• Evaluation of expressions
식의 representation
- infix : 원래 식
- prefix : 괄호 바로 앞에 연산자 (예뻐서 앞으로 옴) !!
- postfix : 괄호 바로 뒤에 연산자 !!
- Postfix 계산 방법
: 연산자가 (숫자 숫자)연산자 이렇게 오기 땜에 연산자 순서대로 쭉
연산자 앞에잇는 두 숫자로 계산한거를 적는거 반복하면 됨!!
=> Stack으로 구현하면
숫자를 스택에 주루룩 저장 -> 연산자 만나면 젤 위에잇는 두 숫자로 계산하고 그걸 저장 !! -> 숫자가 하나 남을때까지!
- infix -> postfix 식 변환 알고리즘
1. 괄호를 다 친다 (fully parenthesize) - 일단 곱/나눗셈을 다 괄호 쳐주고 나머지 +-에 대한 괄호 차례로 쳐준다
2. 해당 연산에 대한 괄호의 바로 오른쪽으로 (바로옆으로) 연산자를 다 옮긴다
3. 괄호를 다 삭제한다 ^^
ex A/B - C + D * E - A * C -> AB/C-DE*+AC*-
-> 스택으로 구현하기
stack에 연산자들을 담고 output에 알파벳을 하나씩 뺀다 (괄호 치기 안하고시작!! 안한채로 하는거!! 다 풀고한당)
예를 들어 (a+(b*c)) 에서 스택에 연산자를 담을때 +를 넣고 *을 넣게 되는데,
이때 c가 더 먼저하는 연산이기땜에 c바로 옆에 가고 그 옆에 +가 붙게 된다
-> 스택에 연산자 넣을 때 넣게 되는 연산자보다 있던 애가 더 크거나 같으면-> 있던 그 친구를 우선 빼주고 -> 다시 넣기 시도함!
그리고 알파벳 다 담아서 끝낫는데 스택에 연산자가 잇으면 그냥 마지막에 스택에서 하나씩 순차적으로 빼서 옆에 적어줌!
**
여는 괄호인 경우
우선 여는 괄호인 경우, 무조건 operators스택에 push!!!
operators스택에 push된 여는괄호는 닫는괄호의 경우에서 제거가 됩니다.
닫는 괄호인 경우
닫는 괄호인 경우, operators스택에서 여는괄호를 만날 때까지 pop해서 postfix배열에 push합니다 !!
)나오면 무조건 (나올때까지 다 pop시킨다 !!
코드
몰라띠발
Queue ~
= 먼저 들어온게 먼저 나감. 줄서있는거. 울건물 카페..; FIFO ! first in first out
- enqueue : insert! 맨뒤로 들어옴
- dequeue : delete ! 맨앞에꺼 지움
- front : 맨 앞 가리키는 포인터 (이쪽이 dequeue)
- rear : 맨 뒤 가리키는 포인터 (이쪽에 enqueue)
코드
* circular 로 생각해야 하므로 다음 인덱스 인덱스 나타낼때는 항상 (index+1)%capacity 이렇게 한다 !!
(인덱스 하나 추가해줄때는 꼭 저렇게 쓰기 !!)
*front = (rear+1)%capacity -> 꽉참 !!
struct Queue{
int Capacity;
int rear;
int front;
int data[capacity]; //or int* arr; 이렇게 선언만 해놓음
}
Queue* create(){
Queue* q = (*Queue)malloc(sizeof(Queue));
q->front=0;
q->rear=0;
return q;
}
// front는 시작 인덱스보다 하나 전, rear은 마지막 인덱스 ! 하나전 하는이유는 꽉찻을때 바로 확인하려고
void show(Queue* q){
for(int i=front+1; i!=rear; i=(i+1)%capacity){ //짱중요 !!! front+1부터 레어까지, 나머지를인덱스로 !!
printf(q->data[i]);
}
printf(q->data[i]); //마지막꺼 한번 더 !!!
}
static int Succ (int value, Queue Q){
if(++value==->Q->capacity){
value=0;
}
return value;
} // 이건 인덱스 반환해주는거. 원래걍 +1하면 되는데 맨 끝일 때 그다음인 0을 반환해줌
//그리고 걍 (index+1)%capacity 해도 되긴함..;
void Enqueue(Queue* q, int data){
if (!isFull(q)){
rear=(rear+1)%capacity;
q->data[rear]=data;
}
}
void dequeue(Queue* q){
front=(front+1)%capacity;
// 값 안지워줘도 된다 ~~
}
//엔큐 디큐에서 인덱스 구할때 만들었던 insucc함수 써도됨 같은 의미임
//교수의 addq
void addq(Queue* q, int data){
rear=(rear+1)%capacity;
if(rear==front){
queueFull(); // 사이즈 두배 늘려주는 연산
}
queue[rear]=data; //
}
int isFull(Queue* q){
if((rear+1)%capacity==front)
return True;
return False;
}
// empty는 front==rear일 때!이제 꽉찰때 사이즈 두배 해주는 함수!!
1. 용량 두배인 배열 만듦
2. queue[front+1] ~ queue[capacity-1] (front원소~마지막원소)를 newQueue 맨 앞부터 채운다 (복사 ㄲ)
3. queue[0] ~ queue[rear] (첨에저장된애~rear애) 를 newQueue에 남은 자리부터 쭉 채운다
( 위에거 개수가 capacity-1-(front+1)+1 일것이므로 인덱스도 그거부터 ! capacity-front-1 인덱스부터 채운다)(capacity-start)
void queueFull(){
newQueue에 malloc;
//실제 front구함 (실제 값은 front 다음에 담겨있으므로)
int start=(front+1)%capacity;
if (start<2){ //start 인덱스가 0 또는 1이면 그냥 첨부터끝까지 잘리는거없이 담겨잇으므로 그대로복사하면됨
copy(queue+start, queue+start+capacity-1, newQueue);
}
else{
copy(queue+start, queue+capacity, newQueue);
copy(queue, queue+rear, newQueue+capacity-start);
}
//그리고 정보바꿔줌
rear=capacity -2 ; //!!!1
front=2*capacity -1; (왜..?)
capacity*=2;
free(queue);
queue=newQueue;
}
