I'll never know if I never commit

덱 이란? 덱은 큐와 스택의 기능을 모두 갖춘 만능 리스트라고 생각하면 된다. 즉, 앞 ,뒤 모두에서 데이터가 삽입가능하고, 앞, 뒤 모두에서 데이터가 삭제가 가능한 자료구조이다. 즉 add rear 와 delete front는 큐의 성질이고, add rear 와 delete rear는 스택의 성질이라고 보면 된다. 덱은 주로 이중연결리스트로 구현이 되는데, 그 이유는 front와 rear에서 모두 삽입 , 삭제하려면 양쪽으로 링크를 가진 이중연결리스트가 편리하기 때문이다. 또한 덱은 앞,뒤에서 삭제삽입이 이루어지기 때문에, 큐처럼 head 포인터와 tail포인터를 모두 가지고 있어야한다. 덱은 앞서 봤던 큐와 스택을 짬뽕?! 해놓은 개념이라 까다롭지 않으므로 바로 소스코드를 살펴보도록 하겠다! 역시나 ..

큐 란 무엇인가? FIFO, "가장 먼저 들어온 것이 가장 먼저나가는 " 자료구조의 형태이다. 이는 영화관 매표소의 줄을 생각하면 쉽다. 가장 먼저 온 사람이 가장 먼저 티켓을 받고 줄에서 나간다! 그래서 큐는 리스트의 두군데에서 입출력을 담당한다. 스택의 경우 tail 즉 꼬리부분이 입출력을 모두 담당했지만, 큐의 경우 입력은 뒤에서! 출력은 앞에서 ! 담당한다. 그래서 각각 출력을 담당하는 부분을 front , 입력을 rear 라고 한다. 그러면 이러한 큐를 어떻게 구현하는가 ? 일단 크게 세가지의 방법이 있다. 1) 배열리스트 구현 2)원형 배열 구현 3)연결리스트 구현 1번 배열리스트 구현은 너무 쉽게 구현되기 때문에 패스하고, 2번과 3번을 구현해보도록 하겠다. 먼저 원형큐를 살펴보자! 배열을 ..

먼저 해당 문제의 로직이다 이렇게 스택의 성질을 이용해서, 스택 배열을 구현하거나, STL stack을 이용하면 비교적 쉽게 풀린다. 하지만..! 나는 '스택'이란 것 자체를 이용하지 않고 이문제를 풀어보고싶었다( ?!?) 그래서 두가지의 소스코드가 나왔다. 일단 스택을 이용한 소스코드이다. 매우간결하다 #include #include #include #include using namespace std; vectorans; int main(void) { int n; int num; cin >> n; stack s; int j = 1; for (int i = 0; i > num; if (s.empty() || s.top() < num) { //stack이 empty거나, to..

스택은 LIFO , "가장 늦게 들어간 요소가 가장 먼저나오는" 데이터 구조이다. 그럼 이 스택을 어떻게 구현할 수 있을까? 아마 첫번째로 떠오르는 것은 배열리스트 일 것이다. 동적으로 배열을 할당받는 방법도 있겠지만, '배열'의 형태로 구현할 경우 어쩔수없이 스택은 저장할 수 있는 자료에 있어서 한계가 있다. 이를 위해서는 '연결리스트'로 스택을 구현해주면 된다. 동적할당된 배열의 형태가 아니라, 연결리스트의 link 필드로, 동적 할당된 요소들을 계속해서 연결시켜주면, 우리는 길이의 제한 없이 스택을 이용할 수 있다. 먼저 소스코드에 구현된 세가지 클래스를 설명한 이미지이다. 이 코드는 세가지의 class로 나뉜다. 1) Node Class: 스택의 'Node'가 될 요소들의 데이터와 요소들을 이어줄..