코딩/데이터 구조 썸네일형 리스트형 7. 데이터 구조 - Queue의 이해 및 구현 1. queue의 개념스택의 경우, 나중에 들어온 데이터가 먼저 나가는 구조인 후입선출인 반면, 큐는 먼저 들어온 데이터가 먼저 나가는 구조로 이러한 특성은 선입선출(FIFO : first-in first-out)이라고 한다. 또한 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 이루어져있기때문에 스택에서 삽입과 삭제를 구현하기 위해 사용되었던 변수가 top 1개만 사용하였지만, 큐는 삽입에 관련된 변수를 rear 라고 하고, 삭제에 관련된 변수를 front라고 한다. 큐는 은행에서 기다리는 사람들의 대기열, 혹은 인터넷에서 전송되는 데이터 패킷들을 모델링하는데에 사용되곤 한다. 2. queue의 ADT그렇다면 queue의 ADT에 대해서 살펴보자.일단 queue를 기본적인.. 더보기 6. 데이터 구조 - 스택의 응용(후위 표기 수식의 정의와 계산) 1. 후위표기 수식이란?우리는 많은 수식을 사용한다. 그중 우선 순위가 다른 연산자들이 있어 계산을 해야하는 순서가 정해져 있다.우리야 각각의 연산자들의 모양을 보고 우선 순위를 파악하지만, 컴퓨터는 어떠한 방식으로 수식을 계산할까? 수식을 표기하는 방식에는 3가지 방식이 있고, 이를 구분하는 방식은 연산자와 피연산자의 위치이다.1. 중위표기법 : 연산자가 피연산자 사이에 있음2. 후위표기법 : 연산자가 피연산자 뒤에 있음3. 전위표기법 : 연산자가 피연산자 앞에 있음 중위전위후위3+4*5+3*45345+*a*b+5+*ab5ab*5+ 컴퓨터는 이 3가지 표기중 후위표기법을 사용한다. 그래서 프로그래머가 인간들이 자주쓰는 표기법인 중위표기법으로 작성하면 컴파일러는 이것을 후위표기법으로 바꾸어 사용한다. 그.. 더보기 5. 데이터 구조 - 동적할당(malloc,realloc)과 스택(stack) https://spatz.tistory.com/119 위의 글에서 구현한 스택은 배열의 크기를 이미 #define을 통해서 정해놓고 시작한다. 하지만 대부분의 코딩 문제나, 프로그래밍할 때는 내가 원하는 배열의 크기를 미리 정해놓을 수 없다. 그러므로 그 크기를 동적할당(malloc)이라는 것으로 메모리를 할당시킨 후에 이를 realloc()이라는 함수를 통해 내용을 그대로 두고 크기를 증가시키며 사용한다. 밑에 있는 코드는 이를 구현한 것이다.#include #include typedef struct { int* data; //동적할당 받을 준비 하기 int capacity; // 할당 받을 메모리의 현재 크기 int top; } stacktype;void init_stack(stacktype* s).. 더보기 2. 데이터 구조 - 포인터의 개념과 swap 함수 만들어 보기 데이터 구조를 처음 시작 할때 기본적으로 알아야 하는 것들은 많다.순환, 구조체, 배열, 포인터 를 대표적으로 뽑을 수 있는데, 이들 중 포인터에 대해서 이야기 해보려고 한다. 1. 포인터 : 다른 변수의 주소를 가지고 있는 변수int a = 100;int *p; // p는 int형을 가리키는 포인터 라는 것을 정의!!p = &a; // 변수의 주소는 & 연산자를 변수에 적용시켜서 추출 할 수 있다. 포인터에서 중요한 개념 두가지! &연산자 , *연산자&연산자 - 주소 연산자&연산자는 변수의 주소를 추출하는 연산자이다. p라는 것은 이제 "주소" 만 가리킬 수 있는 화살표인데, 그 화살표가 a의 주소를 가리키게 만들고 싶으면,"p = &a" ,즉 &를 통해서 a의 주소를 추출한 후 이것을 p라는 화살표.. 더보기 4. 데이터 구조 - stack의 구조체화 2024.08.07 - [코딩/데이터 구조] - 3. 데이터 구조 - ADT의 개념과 stack의 이해 및 구현 위의 링크의 stack 구현은 이해하기는 쉽지만 stack배열과 top이 전역변수로 선언되어 있기 때문에 하나의 프로그램에서 여러 개의 stack을 구현할 수 없다. 그래서 top과 stack 배열을 하나의 구조체로 만들면 여러 개의 스택을 쉽게 만들 수 있게 된다.#include #include #define MAX 100typedef struct { //stack 배열과 top 을 하나의 구조체로 만듬 int data[MAX]; int top;}stackType;void init_stack(stackType* s) { s->top = -1; // 구조체 포인터를 받으면 top을 사용하는.. 더보기 3. 데이터 구조 - ADT의 개념과 stack의 이해 및 구현 1. ADT란 ?실제적인 구현으로 부터 분리되어 정의된 자료형이다.즉 복잡한 소프트웨어 시스템을 관리하기 위해 각각의 주요한 부분을 분리해 추상적으로 관리하는 것이다. 2. stack의 개념스택이란 더미, 낟가리라는 뜻으로, 어떠한 것들이 쌓여있는 상태를 의미한다.만약 상자라고 예를 든다면, 쌓여있는 상자에서 상자를 빼야할때 밑에서 빼거나 중간에서 빼면 상자가 무너져 내릴것이다.즉 상자를 뺄때는 맨 위(맨 마지막)에 놓은 상자부터 차례대로 빼야 무너지지 않는다. 이러한 과정을 후입선출(LIFO)라고 한다. 그래서 stack은 중간이나 맨 처음(맨 아래)에 넣은 상자를 자신의 차례(맨 위)가 될 때까지 어떤 상자인지 확인 할 수 없다. 무조건 맨 위에 있는 상자만 확인 할 수 있는 것이다! 즉 자료의 출력.. 더보기 1. 데이터 구조 공부를 시작하며... 저는 사실 데이터 구조가 if문이나 for문, 배열 등 새로운 개념일 줄 알았습니다. 그래서 굉장히 기대하며 시작했던 기억이 납니다. 하지만 처음 배울 때부터 생각보다 난관이었습니다. 제가 배웠던 여러 개념들을 잘 조합해서 하나의 거대한 구조를 돌아가게 만드는 것, 그것이 데이터 구조였습니다. 과거의 개념을 정확하게 잡지 않았던 저는 단순히 외우는 데에 급급했습니다. 결국 머릿속에 들어오는 것은 거의 없었습니다.(ㅠ) 그래서 다시 공부를 시작하며 이 블로그에 정리해보려고 합니다...이 글을 보는 여러분도 꼭 기본 개념을 정확하게 익히고 데이터 구조 공부를 시작하길 바라며!!데이터 구조 공부를 시작해보겠습니다...! 더보기 이전 1 다음
