컴퓨터 공학/자료 구조 (9) 썸네일형 리스트형 자료구조/Python3) 큐 두 개로 스택 구현하기 두 개의 큐로 스택을 구현할 수 있다. 이때 큐는 이미 구현된 것 클래스를 사용했다. class Stack: def __init__(self) -> None: self.inq = linked_list_queue.Queue() self.outq = linked_list_queue.Queue() ... push 큐 둘 중 하나에 값을 enqueue해주면 된다. 이건 일반적인 스택 push 방법과 동일하다. ... def push(self, data) -> None: self.inq.enqueue(data) ... pop 이 부분에 조작이 필요하다. 일단 값을 추가한 큐(=inq)에 값이 1개 남을 때까지 dequeue에서 앞에 있는 값들을 모두 또 다른 큐(=outq)에 넣어준다. 그러면 먼저 들어간 요소들.. 자료구조/Python3) 스택 2개로 큐 구현하기 스택과 큐는 출력되는 순서가 정반대다. 스택은 가장 나중에 들어간 요소가 가장 먼저 나오고, 큐는 가장 먼저 들어간 요소가 가장 먼저 나온다. 이러한 특성을 이용해서 스택 2개로 큐를 구현할 수도 있다. 스택은 미리 구현해 둔 클래스를 사용했다. 일단 스택 두개를 가지고 있어야 한다. import linked_list_stack class Queue: def __init__(self): self.in_stack = linked_list_stack.Stack() self.out_stack = linked_list_stack.Stack() ... enqueue 데이터 삽입은 그냥 스택 둘 중 하나에 넣으면 된다. 이 스택은 나는 In_stack이라고 선언했다. ... def enqueue(self, data.. 자료구조/Python3) 연결 리스트로 큐 구현하기 Queue는 선입선출 (First In First Out) 형식의 자료구조이다. 브라우저가 Javascript를 동작시킬 때 api콜, setTimeout 등 비동기로 처리할 수 있는 함수들은 콜 스택에 쌓지 않고 web api에서 비동기로 처리한 후 처리 결과와 함께 콜백 함수를 테스크 큐에 넣는다. 이 때 테스크 큐가 큐 구조로 이루어져 선입선출 방식으로 작동한다. python에서는 collections라는 라이브러리에 deque 모듈을 임포트해서 사용하면 간단하지만 원리를 이해하기 위해 연결리스트로 구현해보았다. class Node 연결리스트의 노드는 각 노드의 값과 다음 노드를 가리키는 포인터로 이루어져있다. class Node: def __init__(self, data) -> None: sel.. 자료구조/Python3) 연결리스트로 스택 구현 후입 선출 (Last in First Out) 자료구조인 스택은 Python에서 이미 list[]라는 자료형으로 구현되어 있다. 그래서 내장된 append, pop 함수를 이용해서 push,pop 메소드를 간단하게 구현할 수 있다. 그래서 이번에는 리스트 자료형을 사용하지 않고 각 노드가 next 노드에 대한 포인터를 가지고 있는 연결리스트로 스택을 구현해보았다. class Node class Node: def __init__(self, data): self.data = data self.next = None 연결 리스트의 각 노드들은 값(=data)을 가지고 다음 노드에 대한 포인터 (=next)를 갖는다. class Stack 스택은 기본적으로 top 포인터를 가지고 있다. LIFO 구조로 데이터에 .. 자료구조) 딕셔너리 ADT 딕셔너리 ADT ADT 탐색 가능한 형태의 { key, value } 쌍 데이터 상목들의 집단을 모델링한 것이다. 주요 작업 searching ** key 탐색을 통해 원하는 데이터를 찾는 것 inserting deleting 종류 unordered ordered key 순서를 기준으로 딕셔너리 ADT 메소드 int size() : 사전의 항목 수 반환 bool isEmpty() element findElement(key) insertItem(key, element) element removeElement(key) 탐색 데이터 집단으로부터 지정된 key를 가진 element를 추출하는 것 유일키 사전 : 한 개의 키에 대해 하나의 element만 존재 중복키 사전 : 한 개의 키에 여러 개의 elemen.. 자료구조/C) 연결리스트를 이용한 실습 문제 풀이 문제 소스코드 #include #include typedef struct node { int coef; int exp; struct node* next; } Node; Node* newNode(int c, int e) { Node* p = (Node*)malloc(sizeof(Node)); p->coef = c; p->exp = e; p->next = NULL; return p; } Node* appendTerm(Node *k, int c, int e) { //k는 마지막항 Node* t = newNode(c, e); Node* khead = newNode(NULL, NULL); khead->next = k; while ((khead->next) != NULL) { khead = khead->next; .. 자료구조/C) 연결리스트 ADT #include #include #include typedef struct node { char item; struct node *next; struct node *prev; } Node; typedef struct list { Node *head; Node *tail; int n; }List; typedef List *Plist; void initList(Plist list){ list->head = NULL; list->tail = NULL; list->n = 0; printf("initlist success\n"); } Node* newNode(char item) { Node *node = (Node*)malloc(sizeof(Node)); node->item = item; node->prev = .. 자료구조/C) 이진탐색트리 BST 응용 문제 소스 코드 문제 이전에 설명한 방식대로 트리 정보와 탐색 정보가 주어졌을 때, 트리를 생성하고 탐색 도중 방문하는 노드의 번호를 차례로 출력하는 프로그램을 작성하시오. 입력 예시 1 9 ↦ 노드 개수 5 3 9 (preorder - VLR) 3 8 15 8 0 2 2 0 0 15 0 0 9 7 10 7 12 0 12 0 0 10 0 0 3 ↦ 탐색 횟수 RLL LL LR 출력 예시 1 (□는 공백) □5 9 7 12 ↦ 첫 번째 탐색 결과 □5 3 8 ↦ 두 번째 탐색 결과 □5 3 15 ↦ 두 번째 탐색 결과 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include typedef struct node { int data; struct node* left; struct no.. 이전 1 2 다음
