[C++] 자료구조 – 스택(Stack) 코드 : Array / LinkedList 를 사용하여 구현


Stack을 구현하는건 쉬웟다. 의외엿던건, 코드를 짜기 전에는 LinkedList 를 사용하여 구현하는게 더 복잡할 줄 알았는데 LinkedList 를 사용하는건 정말 간단했고, 오히려 배열을 사용하여 구현하는게 조금 헷갈렸다.

배열로 구현 할 때 헷갈렸던 부분은 생성자에서 배열을 initialize 할 때, 처음엔 Node* nodes 를 사용하고 생성자에서 new Node[capacity] 로 설정했었는데, 불필요하게 capacity 만큼의 Node를 생성하게 되는 문제가 있었다. C언어에서는 malloc 을 사용하면 됐는데, C++에서는 malloc을 사용 할 수 있는데 사용하는게 비권장되어서 조금 더 생각해보니 포인터 배열을 사용하면 되겠다 싶어서 사용해보니 원하는대로 작동했다. Node** nodes 이렇게 별하나 더 붙여주고 생성자에는 Node*[capacity] 이렇게 사이에 별하나 추가.

그나저나 포인터 개념은 분명히 옛날에 알고리즘 공부하면서 분명히 충분히 이해했는데 오랫동안 안하면 또 헷갈리는것 같다.. 내 머리가 겨우 이 정도인가..
이럴 때 보면 프로그래밍이랑 수학은 은근히 비슷한것 같..ㄷ

링크드 리스트를 사용해서 스택을 구현 할 때는 의외로 쉬워서 간단했다.

책이나 인터넷상 몇몇 코드를 보니 Node 부분에서 ‘next‘ 를 사용했는데 음.. stack 인데 ‘next’ 라는 표현을 쓰는것보다 이전 노드인 ‘prev‘ 를 사용하는게 더 말이 되겠다 싶어서 연결될 노드의 이름을 ‘prevNode‘ 로 했다. 이 변수의 이름을 next 로 하면 코드를 짤 때 머릿속에서 틀이 잘 안그려진다 – 글을 작성하면서 알았는데, 처음엔 그냥 단순히 변수명의 문제인줄 알았으나. 책에 있는 코드랑 인터넷상 코드를 보니까 next 노드를 사용하게 하면서 pop 할 때 while 문 돌려서 끝에 있는 노드를 조회한다.. 도대체 왜 이렇게 짜는거야? 매우 비효율적이다..

아, 그리고 코드작성할때 초보스러운 실수를 저질렀었는데, 클래스를 만들고, 생성자에서 length 의 값을 안정해줬다. 그래서 나중에 테스팅할때보니 length 여러자릿수..
이런 실수를 코딩면접할떄 저지르면 얼마나 쪽팔릴까 허허허. 왜 까먹은거지. 주의하자.

생각해보니 난 학부시절 자료구조를 처음 배울때 어리석게도 stack 과 queue 의 개념이 헷갈렸다. 근데 옆에 있던 미국애가 stack 은 ‘think about a stack of papers’ 이러면서 쌓여있는 종이에 비유했다. 종이를 쌓아놓으면 맨 위 부터 본다고 생각하면 되고, queue 는 줄서는걸 생각하라고 했다. 걔는 그냥 지나가면서 설명해줬겟지만 난 요즘도 stack 과 queue 를 볼 떄 걔가 해준말을 기억한다

배열 기반 Stack

LinkedList 기반 Stack