Week 7-1 : Stack, Queue by Linked List

<180517>

- 연결리스트로 구현한 스택

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} Node;
 
typedef struct stack {
    Node *top;
} Stack;
 
void init(Stack *ps)
{
    ps->top = NULL;
}
 
int isEmpty(Stack *ps)
{
    return ps->top ==  NULL; 
}
 
void push(Stack *ps, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->link = NULL;
    if(!isEmpty(ps)) 
        newNode->link = ps->top;    
    ps->top = newNode;
}
 
int peek(Stack *ps)
{
    return ps->top->data;
}
 
int pop(Stack *ps)
{
    Node *delNode = ps->top;
    int ret = delNode->data;
 
    ps->top = ps->top->link;
    free(delNode);
    return ret;
}
 
int main()
{
    Stack s;
    init(&s);
    isEmpty(&s) ? puts("Empty") : puts("No");
 
    push(&s, 10);
    push(&s, 20);
    if(!isEmpty(&s)) printf("%d\n", peek(&s));
    if(!isEmpty(&s)) printf("%d\n", pop(&s));
    if(!isEmpty(&s)) printf("%d\n", peek(&s));
    return 0;
}
 

>> 실행결과

Empty

20

20

10

- 연결리스트로 구현한 큐

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} Node;
 
typedef struct queue {
    Node *f, *r;
} Queue;
 
void init(Queue *pq)
{
    pq->f = pq->r = NULL;
}
 
int isEmpty(Queue *pq)
{
    return pq->f ==  NULL; 
}
 
void enqueue(Queue *pq, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->link = NULL;
 
    if(isEmpty(pq)) pq->f = newNode;
    else pq->r->link = newNode;
 
    pq->r = newNode;
}
 
int peek(Queue *pq)
{
    return pq->f->data;
}
 
int dequeue(Queue *pq)
{
    Node *delNode = pq->f;
    int ret = delNode->data;
 
    pq->f = pq->f->link;
    
    free(delNode);
    return ret;
}
 
int main()
{
    Queue q;
    init(&q);
    isEmpty(&q) ? puts("Empty") : puts("No");
 
    enqueue(&q, 10);
    enqueue(&q, 20);
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
    if(!isEmpty(&q)) printf("%d\n", dequeue(&q));
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
    return 0;
}

>> 실행결과

Empty

10

10

20