알고리즘 스터디 2회차 - Stack & Queue 구현

저번 시간에 만들었던 연결 리스트를 이용해 Stack과 Queue를 만들어보았다. 끝에서만 항목(item)을 삭제하거나 저장하는 자료구조인 LIFO의 Stack, 양 끝에서 삽입과 삭제가 각각 수행되는 자료구조인 FIFO의 Queue를 몇 가지 특징과 함께 정리해보았다. 나중에 다시 볼 수 있게 나만의 언어로 작성하는 글이라 읽기 불편할 수 있지만...

1. Stack

Stack의 주요 함수는 삽입을 담당하는 push와 삭제를 담당하는 pop이다.

기본적으로 자료구조의 끝에서만 삽입과 삭제가 일어나기 때문에 구현하는데에는 그리 어렵지 않았다.

push :: list와 KeyData를 입력받아 리스트의 끝에 연결해준다.

pop :: 리스트의 끝에 있는 항목을 날려준다.

print :: 리스트의 항목들을 보여준다.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
 
// size_MaxValue = 10;
 
int size = 0;
 
typedef struct stack {
    struct node *head;
    struct node *tail;
}stack;
 
typedef struct node {
    int key;
    struct node *next;
}node;
 
void push(stack *list, int keyData) {
    
    if (size < 10) {
        node *newNode = (node *)malloc(sizeof(node));
        newNode->key = keyData;
        newNode->next = NULL;
 
        if (list->head == NULL && list->tail == NULL) {
            list->head = newNode;
            list->tail = newNode;
        }
        else {
            list->tail->next = newNode;
            list->tail = newNode;
        }
        size++;
        printf("Succeessfully pushed");
    }
    else {
        printf("stack is full\n");
    }
}
 
void pop(stack *list) {
 
    if (size > 0) {
        node *lastNode = list->head;
        if (size == 1) {
            list->head = NULL;
            list->tail = NULL;
        }
        else {
 
            for (int i = 0; i < size - 2; i++) {
                lastNode = lastNode->next;
            }
 
            lastNode->next = NULL;
            list->tail = lastNode;
        }
        size--;
        printf("Succeessfully popped");
    }
    else {
        printf("stack is empty\n");
    }
    
}
 
void print(stack *list) {
 
    if (list->head != NULL) {
        node *currentNode = list->head;
        printf("******\n");
        while (1) {
            printf("%d\n", currentNode->key);
            if (currentNode == list->tail) break;
            currentNode = currentNode->next;
        }
        printf("******\n");
    }
    else {
        printf("stack is empty\n");
    }
}
 
int main(void) {
    int com, key;
    stack *list = (stack *)malloc(sizeof(stack));
    list->head = NULL;
    list->tail = NULL;
    while (1) {
        printf("\nstack :: 1-push, 2-pop, 3-print // size is %d\n", size);
        scanf_s("%d", &com);
 
        switch (com) {
        case 1:
            scanf_s("%d", &key);
            push(list, key);
            break;
        case 2:
            pop(list);
            break;
        case 3:
            print(list);
            break;
        }
    }
}

2. Queue

Queue의 주요 함수는 삽입을 담당하는 add와 삭제를 담당하는 remove이다.

Stack의 코드를 살짝 변형만 해주었다.

add :: 새 노드를 만들어 list의 끝에 KeyData를 삽입한다.

remove :: list의 Head를 삭제하고, 그 다음 노드를 Head로 지정해준다.

print :: 리스트의 항목들을 보여준다.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
 
// size_MaxValue = 10;
 
int size = 0;
 
typedef struct queue {
    struct node *head;
    struct node *tail;
}queue;
 
typedef struct node {
    int key;
    struct node *next;
}node;
 
void add(queue *list, int keyData) {
    
    if (size < 10) {
        node *newNode = (node *)malloc(sizeof(node));
        newNode->key = keyData;
        newNode->next = NULL;
 
        if (list->head == NULL && list->tail == NULL) {
            list->head = newNode;
            list->tail = newNode;
        }
        else {
            list->tail->next = newNode;
            list->tail = newNode;
        }
        size++;
        printf("Succeessfully added");
    }
    else {
        printf("queue is full\n");
    }
}
 
void remove(queue *list) {
 
    if (size > 0) {
        node *lastNode = list->head;
        if (size == 1) {
            list->head = NULL;
            list->tail = NULL;
        }
        else {
 
            list->head = lastNode->next;
        }
        size--;
        printf("Succeessfully removed");
    }
    else {
        printf("queue is empty\n");
    }
    
}
 
void print(queue *list) {
 
    if (list->head != NULL) {
        node *currentNode = list->head;
        printf("******\n");
        while (1) {
            printf("%d\n", currentNode->key);
            if (currentNode == list->tail) break;
            currentNode = currentNode->next;
        }
        printf("******\n");
    }
    else {
        printf("queue is empty\n");
    }
}
 
int main(void) {
    int com, key;
    queue *list = (queue *)malloc(sizeof(queue));
    list->head = NULL;
    list->tail = NULL;
    while (1) {
        printf("\nqueue :: 1-add, 2-remove, 3-print // size is %d\n", size);
        scanf_s("%d", &com);
 
        switch (com) {
        case 1:
            scanf_s("%d", &key);
            add(list, key);
            break;
        case 2:
            remove(list);
            break;
        case 3:
            print(list);
            break;
        }
    }
}
 

파이썬 배열로도 해버렸다

1. stack

def push(item):
    stack.append(item)
 
def peek():
    if len(stack) != 0:
        return stack[-1]
 
def pop():
    if len(stack) != 0:
        item = stack.pop(-1)
        return item
 
stack = []
 
while(1):
    s = int(input('명령어를 입력하세요 ( 1-push / 2-pop / 3-print / 4-quit ) : '))
    if s == 1:
        v = input('어떤 값을 push 할까요? : ')
        push(v)
    elif s == 2:
        if len(stack) == 0:
            print('stack 이 비어있습니다.')
        else:
            print('pop 되었습니다.')
            pop()
    elif s == 3:
        for i in stack:
            print(i)
    elif s == 4:
        break
    else:
        print('잘못 입력 하셨습니다.')