[스택] 링크드 스택 - C++

저번 글에서는 배열을 이용해 스택을 구현해봤다. 배열로 스택을 만들면 빠르다는 장점이 있지만 크기가 한정되어 있다는 단점이 있다. 무한정 공간을 늘리자니 메모리가 낭비될 수 있고 공간을 적게 하자니 부족할 수도 있다. 링크드 스택을 구현해 메모리를 동적 할당 하면 메모리의 낭비나 부족 현상을 대비할 수 있다. 동적 할당이기 때문에 메모리 관리를 신경써야 하고 속도도 배열보다 살짝 느리지만 메모리를 효율적으로 사용할 수 있다는 장점이 있다. 링크드 스택은 노드와 노드를 연결해 데이터를 저장하는 스택이다. 노드는 데이터와 내 다음 노드의 주소를 저장하는 하나의 단위이다. 노드의 왼쪽에는 저장하고자 하는 데이터가 담겨 있고 오른쪽에는 이전 노드가 어디있는지 가르키는 주소 데이터가 담겨져 있다. 동적으로 할당받..

• format_list_bulleted 공부/자료구조 핥기
• · 2020. 8. 29.
• textsms

[스택] 배열로 스택 알아보기 - C++

자료구조를 공부하기 시작하면 처음 만나게 될 친구가 스택이지 않을까 싶다. 스택의 입출력 형태는 후입선출, LIFO(Last-In First-Out)로써 실행취소(Ctrl+Z) 기능을 떠올리면 쉽다. 작업 목록을 보면 먼저 했던 작업들은 밑에 있고, 나중에 했던 작업은 목록의 상단에 있다. 되돌릴 때는 목록의 상단부터 터 되돌릴 수 있으니 나중에 들어온 것이 먼저 나가는 구조, 즉 스택이라고 할 수 있겠다. 스택에서 쓰이는 용어들은 push, pop, top이 있다. top은 스택의 최상단에 위치한 값을 뜻하고, push는 요소를 스택에 삽입하는 연산, pop은 top이 가르키고 있는 요소를 제거해 반환하는 연산이다. int형 배열을 이용해 스택을 만들어보고자 할 때 필요한 변수와 함수, 함수가 해야 할..

• format_list_bulleted 공부/자료구조 핥기
• · 2020. 8. 25.
• textsms