Week 5-1 : Circular Doubly Linked List / Stack ADT

< 180503 >

1) 원형 이중연결리스트 with 더미노드

- 더미노드 : 말그대로 더미인 노드.

>> 더미노드를 사용하면, head 포인터가 가리키는 대상이 바뀔일이 없다. 항상 더미노드를 가리키므로.

>> 이전에는 head 포인터가 가리키는 대상이 변경될 여지가 있으면 이중 포인터를 써야했는데, 

     더미노드를 쓰면 그럴 필요가 없어진다. 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct listNode {
    int data;
    struct listNode *llink, *rlink;
} ListNode;
 
int main()
{
    ListNode *head = NULL;
    head = (ListNode*)malloc(sizeof(ListNode));
    head->rlink = head;
    head->llink = head;
 
}

>> 또한 지금까지는 head 포인터는 NULL 로만 초기화 했지만, 더미노드 사용하는 경우 더미노드를 만드는 과정을 추가해야한다.

>> 여기서의 더미노드 초기화 코드는 양방향 원형 연결리스트이므로 저런식으로 하면 될 것 같다.

- 삽입하기 / 삭제하기

void addNode(ListNode *before, ListNode *newNode)
{
    newNode->rlink = before->rlink;
    newNode->llink = before;
    before->rlink = newNode;
    newNode->rlink->llink = newNode;
}
 
 
void delNode(ListNode *phead, ListNode *remove)
{
    if(remove == phead) return ;
    remove->rlink->llink = remove->llink;
    remove->llink->rlink = remove->rlink;
    free(remove);
}

>> 노드를 삽입하는 함수에서는 순서가 중요하다. 

>> 12번 라인의 예외처리는 삭제하려는 노드가 더미노드인경우 이다. 더미노드를 사용하는 리스트인데 더미노드를 삭제하면 안되기 때문..!

- 지금까지의 내용을 그림으로 그려보면 다음과 같다. (PPT로 안그릴꺼임...ㅡㅡ)

2) 스택 구현하기

- 스택의 정의 : 나중에 들어온 데이터가 먼저 꺼내진다. 

>> 그냥 프링글스 ㅎㅎ

- 스택의 ADT 및 구현하기

#include <stdio.h>
#define MAX 100
 
typedef struct stack {
    int s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, int data)
{
    if(isFull(s)) return ;
    s->s[++(s->top)] = data;
}
 
int peek(Stack *s)
{
    return s->s[s->top];
}
 
int pop(Stack *s)
{
    return s->s[(s->top)--];
}
 
int main()
{
    Stack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    isFull(&s) ? puts("Full") : puts("Not Full");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    if(!isEmpty(&s)) printf("%d\n", peek(&s));
    if(!isEmpty(&s)) printf("%d\n", pop(&s));
 
    return 0;
}

>> 실행결과

Empty

Not Full

7

7

>> isFull() 에서 왜 MAX-1 일때가 가득찬 상태인지 생각해보기..!!

>> top 의 역할은 스택을 구성하는 배열에서 가장 마지막에 위치한 데이터의 인덱스..!!

2-2) 연결리스트를 이용한 구현 (참고)

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
   char data;
   struct node * next;
} Node;
 
typedef struct listStack {
   Node * top;
} ListStack;
 
void init(ListStack * list) {
   list->top = NULL;
}
 
int isEmpty(ListStack * list) {
   return list->top == NULL;
}
 
int peek(ListStack * list) {
   if(isEmpty(list)) {
      printf("빈 스택임");
      return -111111;
   }
   
   return (list->top)->data;
}
 
void push(ListStack * list, int data) {
   Node * tmp = (Node*) malloc(sizeof(Node));
   tmp->data = data;
   tmp->next = list->top;
   list->top = tmp;
}
 
void pop(ListStack * list) {
   Node *tmp = list->top;
   list->top = tmp->next;
   free(tmp);
}
 
int main()
{
    ListStack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    return 0; 
}
 

>>  여기서는 pop 할때 데이터를 꺼내지 않도록 설계를 한 경우.

### 스택의 응용 ###

3) 올바른 괄호 문자열

- "()()" 는 올바른 괄호 문자열

 - "(())" 는 올바른 괄호 문자열

- "(()())" 는 올바른 괄호 문자열

- "()(" 는 x

- "())(" 는 x

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

void RightBracket(const char * str) {    ListStack l1;    init(&l1);     for(int i=0; str[i]; i++) {       if(str[i] == '(') push(&l1, '(');       if(str[i] == ')') {          if(!isEmpty(&l1)) pop(&l1);          else {             printf("NO\n");             return;          }       }    }        if(isEmpty(&l1)) printf("YES\n");    else printf("NO\n"); } Colored by Color Scripter

cs

>> 5 줄에서 for 문의 조건식을 보자. 

>> 문자열의 마지막은 널문자이다. 널문자의 아스키코드값은 0.

>> 0은 조건식에서 거짓이다.