[code-states][we-win] 37일차 - Data Structure : stack, queue

오늘의 일정 : Stack and Queue

 

​

오늘은 흔히 듣는 '자료구조와 알고리즘' 의 자료구조를 배우는 날

​

뭔가... 상당히 떨렸다

이름만 보아도 상당히 어려워보인다는 인상을 받았기 때문이다

​

누군가는 "자료구조를 모르고 코딩을 한다는 것은, 알파벳을 익히지 않고 영어를 쓰겠단 것과 마찬가지다"

라는 이야기를 하는 것으로 보면 아무래도 무조건 제대로 된 시작을 위해서는 필요한 기초적인 것인데, 어렵다?

​

그런 사항들을 감안하면 영어가 아니라 러시아 키릴문자정돈 되지 않을까 하는 생각이 들었다

​

 

 

​

---

 

 

자료구조를 시작하기 전 :

자료의 정의, 자료구조의 정의, 자료구조의 의의

​

​

자료구조의 정의를 논하기 전에 일단 자료의 정의란 무엇인가부터 짚고 넘어가보자면, 아래와 같다

문자, 소리, 그림, 영상, 단어 등의 형태로 된 의미 단위를 의미하며

이러한 자료를 의미있게 정리하여 도출해 내는 것이 정보이다

출처 : 위키백과

오늘 배울 내용인 자료구조는 위에 말한 자료를 뭉쳐내는, 다양한 형태의 구조들을 의미하는데

컴퓨터가 조금 더 사람의 명령을 효율적으로 처리하기 위한 수단 이라는 의의를 가지기도 한다

다시 말 해, 저기에 나와있는 것처럼 의미있게 자료를 정리하는 데 쓰이는 효율적인 구조라고 볼 수 있다

​

 

그렇다면, 우리가 자료구조를 배우는 이유는 무엇인가?

그것은 상황에 따른 적절한 자료구조의 사용을 통해 자원관리를 효율적으로 하기 위함 이겠다

​

강의에서 그 예시로 들었던 것이 "1,000만 개의 인자 속에서 내가 원하는 특정 인자값 찾기" 였다

​

이것들을 배열(Array) 라는 자료구조 타입으로 이용하면, 저 1,000만개가 담긴 배열이 만들어지게 되는데

내가 원하는 값들을 찾기 위해선 최대 1,000만번만큼의 연산이 필요하다

처음부터 혹은 끝부터 iteration 을 도는데 그와 정 반대에 있는 경우가 분명히 존재하니깐

그러나, 특정 자료구조를 이용하면 최대 24번만의 검색으로도 찾아낼 수 있다고 한다

​

이는 엄청난 효율 향상으로, 자료구조를 왜 공부하는가? 라고 누군가 물어볼 때

"1,000만번 노가다 뛰어야 할 거 24번만 노가다 뛰게 해 줄게, 할래?" 라고 역으로 질문하면 될 일이다

* 참고로 해당 자료구조는 아직 알려주지 않으셨다, 언젠가 공부하다보면 '아 이게 그 예시의 자료구조구나' 라고 알게 될 것이라면서...

​

​

 

 

---

​

 

 

 

이 글을 읽는 사람들은 익히 알겠지만, 그리고 나도 찾아보고 나서 알게 된 것이지만

JS 에서 stack 과 queue 를 구현할 때 사용하는 것은 대부분 두 가지

​

1. 배열

2. linked list

​

그러나 이번엔 객체를 이용해서 했다

​

이는 분명 색다른 경험(사실 자료구조 구현 자체를 처음 해보는 것이지만) 이었으나

정석적인 저 두 방법을 통해서 stack 과 queue 를 구현하는 과정도 언젠간 해야 할 거 같다는 생각이 든다

​

주말을 활용해서 배열과 linked list 를 통해 구현해보자

​

 

 

​

---

 

 

Stack

​

stack 구조를 설명하는 도식

 

​

라는 그림으로 설명하고 싶지만, 이 그림을 보기 전에

아주 적절한 예시가 있어서 그것부터 설명하고자 한다

​

그것도 바로 우리 일상 속에 있는 예시이다

​

쌓여있는 접시

 

회전초밥집이나, 에슐리같은 뷔페를 갈 때 쌓여져 있는 접시들

이 접시를 한 장씩 쌓고 한 장씩 빼는 과정을 생각해보자

​

제일 마지막에 쌓은 접시가, 가장 위로 올라가고

접시를 치워야 할 때도, 가장 마지막에 쌓아서 가장 위로 올라간 접시들이 먼저 빠진다

​

맨 밑에 있는 접시를 빼려면?

그 맨 밑에 있는 접시의 위에 있는 모든 접시들을 빼야 한다

​

스택은 바로 이런 쌓여있는 접시와도 같은 자료구조이다

​

​

​

그러면, 다시 한 번 이 그림을 보자

​

stack 구조를 설명하는 도식

 

​

FILO 라고 흔히들 말하는, First In Last Out 이다

즉, 먼저 들어온 놈은 제일 마지막에 나가는 구조

​

이 특성을 고려한 Stack 구조에서 주로 쓰이는 method 는 총 세 개

​

push() : 위에 접시를 쌓듯 element 를 stack에다가 밀어넣어 주는 기능을 하며

pop() : method 는 위에 쌓여있는 접시를 빼듯 제일 위에 있는 element 를 return 함과 동시에 stack 에서 삭제하는 기능을 한다

​

그리고 저 화면엔 나오지 않았지만, peek() 이라는 method 도 존재하는데,

이는 stack 최 상단에 있는 element를 return 만 하되 pop()처럼 삭제하진 않는다는 차이점이 존재한다

​

 

 

 

 

---

 

 

 

 

어찌어찌 Object 에 numeral keys 를 통해서 구현은 했지만, 의문점이 드는 한 가지

"그래서 이건 어디다 쓰는 거고, 어디다 쓰고 있는걸까?"

​

자료구조 수업 맨 앞에 나왔던 "상황에 맞는 적절한 자료구조를 사용하여 자원을 효율적으로 사용한다" 라는

그런 본질적인 의문이 든 상황이다

​

그리고 나서 찾게 된 글 하나, 정말 최고의 글이다 (링크, 클릭 시 이동)

​

정말 내 머리를 땅 하고 울리는 Stack 의 사용...

When I learned about Stacks, I wondered what a practical use case for them would be.

One of the most common use cases for a Stack is to implement “Undo” (e.g. ⌘+Z or Ctrl+Z).

출처 : https://medium.com/@nicolaisafai

Nicolai Safai – Medium

 

그렇다, Undo, 흔히 말하는 "컨트롤제트" 였다

​

내가 한 작업들의 로그가 하나하나 Stack 에 쌓이는데, 뭔갈 실수해서 "바로 전의" 과정으로 돌아가고 싶다면?

바로 전의, 즉, pop() method 를 사용해서 되돌려 주기만 하면 된다, Stack 구조에 내 작업 로그를 쌓아놨다면 말이다

​

그 외에도 Recursion 도 Stack 에 해당된다

내가 방금까지 했던 것들을 다시 한 번 시행하는 것이니, Stack 구조의 pop() method 를 사용한 것과 비슷하다고 볼 수 있다

​

​

 

 

---

Queue

​

큐는, 조금 생소하지만, 마찬가지로 우리 일상 속에서 정말 많이 볼 수 있는 개념과 비슷한 자료구조이다

정말로, 정말로 많이 볼 수 있는 구조이다...

​

​

Queue 를 설명하기 정말 좋은 세 개의 예시

 

 ​

첫 번째 사진은, 롯데월드의 줄이다

두 번째 사진은, 제주도 연돈의 줄이다

세 번째 사진은 삼각김밥이다

​

차이점은 많지만 확실한 공통점이 하나가 존재하는 사진들인데

그 공통점은 바로, "먼저 줄 서서 기다린 놈이 결국 먼저 줄에서 나간다"

다시 말해 선입선출 이 이뤄진다는 점이다

​

선입선출을 영어로 하면 First In First Out, 줄여서 FIFO

그 기반으로 만들어진 자료구조가 바로 Queue 이다

​

​

​

queue 구조를 설명하는 도식

 

​

Back 과 Front 는 있으면 좋지만 혼동되는 개념이다

그저, FIFO 이 네 글자만 기억하자

추가되는 놈은 Last 로 보내고, 빠지는 놈은 First 에서부터 빼 주는 구조

​

이 일련의 기능들을 method 로 만든 것이

​

enqueue() : Add elements at the end of queue

dequeue() : Return the upfront element of queue and delete it from queue

​

이 두 가지 메소드 enqueue와 dequeue 되시겠다

 

 

 

 

---

 

 

 

 

Stack 과 마찬가지로 Queue 는 어디서 쓰이는가 궁금해서 찾아본 결과

대략 "먼저 자원을 요청한 파트에 자원을 먼저 배분해 주는, 순차할당의 과정이 필요한 경우 Queue 구조를 쓴다" 라고 한다

​

빡 꽂히는 예제를 가져온다면

​

대기열

 

왜 내 학교가 수강신청 대기열 로 구글링 하자마자 뜨는진 모르겠지만 (얼마나 대기열 운영에 충격을 먹었던건가)

이런 대기열이 있겠다

​

먼저 접속한 사람은 먼저 들여보내주는, 그런 시스템에서 주로 사용하는 자료구조가 바로 queue 구조이다

​

다른 수강생분이 들어주신 상당히 적절한 또 다른 예시

 

+ 이 외에도 게임에서 스킬 누르면 누른 순서대로 실행하게끔 하는것도 queue 구조와 비슷하다고 한다

​

​

 

 

---

 

 

 

 

내일은 Linked list, Hashtable 을 구현하는 시간이다

일단... 오늘 너무 피곤했으니 일찍 자야겠다...

​

요즘 이 멘트를 잘 안쓰네

​

37일차 개발일지 끝!