본문 바로가기

쉽게 풀어본 IT 기술

큐와 스택을 쉽게 비교하면 그리고 배열

컴퓨터 구조에서는 또는 프로그램을 개발을 할 때 큐나 스택이라는 말이 가끔 등장을 한다. 큐와 스택 값을 저장하는 방식인데, 그 형태가 다르다. 큐는 먼저 들어온 값이 먼저 나간다. 가게에서 물건을 사기 위해서 줄을 섰다면 당연하게도 먼저 계산대에 온 사람부터 계산을 해줄 것이다. 그래서 그 사람이 끝나면 다음 사람을 계산해주는 순을 한다. 이렇게 온 순서대로 처리를 해주는 것이 큐이다.

스택은 나중에 들어온 것부터 처리를 해준다. 큐는 지극히 생활속에서 많이 봐왔고, 그렇게 처리하는 것이 당연한 거 같지만, 알고리즘에서는 의외로 스택과 같은 저장 방식이 필요한 상황도 있다. 예를 들면 계산기에서 덧셈 뺄셈 또 곱셈 나눗셈을 할 때 스택이라는 저장 방식을 이용하기도 한다. 우선순위라는 것이 있고, 그 우선순위에 맞게 계산을 하고 나서 값을 스택이라는 곳에 저장을 하고 나중에 들어온 값을 그 결과를 가지고 처리를 한다.

큐를 FIFO(First In First Out)이라는 말로 그 방식을 표현하고, 스택은 FILO(First In Last Out) 이라고 표현한다. 먼저 들어와서 먼저 나간다고 해서 FIFO이고, 먼저 들어와서 나중에 나간다고 해서 FILO이다. 큐나 스택은 배열이나 링크드 리스트라는 자료 구조로 만들 수가 있다. 배열은 저장 공간을 의미하는 것이고, 어떤 곳에 먼저 저장 시키고, 삭제 할 것인가를 설계 하는 것이 큐나 스택과 같은 형태이다.

데이터를 연결하여 저장한다는 개념은 자료구조 상에서 필요하다.
1에서 100까지를 저장한다고 했을 때 여러가지 형태로 저장을 할 수 있다. 변수를 100개 선언할 수도 있다. 가장 쉽게 접근하는 방식이 배열이다. 100개의 저장소를 선언하고 숫자를 각각 저장소에 저장한다. 변수를 100개 선언했다면 물리적인 저장 공간의 위치가 어디 일지 모르고, 연결 여부도 알 수 없다. 대부분은 비슷한 위치일 수 있지만, 꼭 그렇다고 할 수는 없다. 배열은 물리적 공간도 바로 옆으로 메모리 공간을 확보한다. 이런 배열의 물리적 공간 확보로 빠른 엑세스를 보장 받을 수 있다. 단점은 그 공간만큼은 미리 확보하고 사용하기에 혹시 사용하지 않더라도 다른 변수들이 쓸 수 없기에 비효율적인 부분이 있을 수 있다. 배열은 그리고 메모리를 미리 잡고 사용한다는 점도 단점이기도 하고, 다시 메모리 할당을 받지 않아도 되서 효율적이기도 하고, 어떤 때 사용하느냐에 따라서 효율적일 수도 있고, 아닐 수도 있다. 이와 비교되는 것이 연결 리스트이다. 연결 리스트는 변수 또는 저장소를 할당 받고, 연결을 하여 다음 값을 저장한다. 배열은 연결된 메모리 공간을 할당받는다고 한다면 연결 리스트는 다음 값의 위치를 연결하여 가진다. 포인트와 같은 변수로 다음 값의 위치를 저장한다. 그리고 그 위치를 따라가면서 값을 얻어오거나 저장한다. 이렇게 되면 효율적인 메모리 관리를 할 수 있다.


책처럼 전체를 보기를 원하시면 아래 링크를 클릭하시고 북마크 하셔서 보시면 편리합니다. 

https://wikidocs.net/22373