연결 리스트로 구현한 스택 (Linked Stack) 지난 스택에 관한 포스팅(여기)에서는 스택을 구현할 때, "배열"을 이용해서 구현했습니다. 이번 포스팅에서는 연결 리스트로 구현하고자 합니다. 어찌 되었든 스택을 구현하는 것이기에 배열을 이용하나, 연결 리스트를 이용하나 외부적으로 볼 때는 큰 차이가 없습니다. 그러나, 스택의 내부를 살펴보면 차이점이 있습니다. 바로 배열과 달리, 연결 리스트로 구현한 스택은 "크기에 제한을 받지 않는다는 것"입니다. 동적 메모리 할당을 통해 스택에 새로운 요소를 삽입할 수 있습니다. 다만, 삽입과 삭제 시에 동적 메모리 할당을 하고 해제해야 하기 때문에 시간이 조금 더 걸립니다. 연결된 스택(Linked Stack) 구현 C언어로 구현한 연결된 스택은 다음과 같습니..

이번 포스팅은 "단순 연결 리스트"를 이해했다는 전제 하에 내용을 진행합니다. 단순 연결 리스트에 대해 잘 알지 못한다면 이전 포스팅을 참고해주시고 그 후 이 포스팅을 읽어주세요 (단순 연결 리스트 공부하기) 원형 연결 리스트의 정의 원형 연결 리스트는 단순 연결 리스트와 달리 "마지막 노드가 첫 번째 노드를 가리키는 리스트"입니다. 즉, 마지막 노드가 NULL 값을 가지는 것이 아니라 첫 번째 노드 주소값을 가지는 것입니다. 원형 연결 리스트는 하나의 노드에서 모든 노드로의 접근이 가능하다는 장점을 가지고 있습니다. 링크를 따라가다가 보면 모든 노드에 접근한 후, 다시 처음으로 돌아오게 되는 것입니다. 이렇게 되면 노드의 삽입과 삭제 연산이 기존 단순 연결 리스트보다 더욱 단순해지게 됩니다. (삽입과 ..

연결 리스트의 정의 연결 리스트(Linked List)는 "노드(Node)"라고 불리우는 일종의 상자들의 집합이라 할 수 있습니다. 물리적으로 흩어져있는 자료들을 줄로 연결하여 하나로 묶는 자료구조 형태를 "연결 리스트"라고 합니다. 위의 그림과 같이 노드는 메모리의 어떤 위치에나 있을 수 있습니다. 노드는 "데이터 필드"와 "링크 필드"로 분류됩니다. 데이터 필드에는 우리가 저장하고자 하는 데이터가 들어갑니다. 그림과 같이, "Hi", "How" 등 문자열 자료가 들어갈 수도 있고, 정수와 같은 숫자가 들어갈 수도 있습니다. 링크 필드에는 다른 노드를 가리키는 줄이 저장됩니다. 각 노드를 연결하는 줄은 "포인터"로 구현할 수 있습니다. 이를 통해서 다음 노드로 갈 수 있습니다. 연결 리스트에서는 반드시..

제어장치 개요 중앙처리장치(CPU)는 데이터를 처리하는 연산을 실행하는 "처리장치(Processing Unit)"와 연산의 실행 순서를 결정하는 "제어장치(Control Unit)"로 분류된다. 제어장치는 처리장치로부터 상태 신호(Status Signals)를 전송받는다. 제어장치는 상태 비트를 이용해서 실행할 연산의 순서를 정한다.NOTE!제어장치는 기억장치에 저장된 명령어를 순차적으로 읽어서 연산코드를 해독하고 결과에 따라 컴퓨터 시스템 내 각 요소에 제어신호를 발생시켜 명령을 수행한다. 이때, 한 명령어는 한 클록 펄스 기간 동안 수행되는 마이크로연산의 집합이다.제어장치 구성요소 제어장치는 특정한 데이터 연산을 실행하도록 처리장치에 마이크로연산을 구동시키는 여러 신호를 제공한다. 제어장치에서는 외부..

처리장치 개요 중앙처리장치(CPU)는 데이터를 처리하는 연산을 실행하는 "처리장치(Processing Unit)"와 연산의 실행 순서를 결정하는 "제어장치(Control Unit)"로 분류된다. 처리장치는 연산장치와 레지스터들로 구성되며 연산장치는 말 그대로 산술, 논리, 비트 연산들을 수행하고, 레지스터는 데이터나 연산의 결과를 저장한다. 이때, 연산장치는 독립적으로 데이터 처리를 할 수는 없고 레지스터들과 조합되어 데이터를 처리한다.마이크로연산 (Micro-Operations) 마이크로연산이란 레지스터에 저장된 데이터에 대해 실행하는 기본 연산을 말한다. 마이크로연산은 일반적으로 "레지스터 전송 마이크로연산", "산술 마이크로연산", "논리 마이크로연산", "시프트 마이크로연산" 이렇게 4가지로 분류..

큐의 정의 스택과 함께 큐도 프로그래밍에서 굉장히 자주 사용되는 자료구조입니다. 스택이 후입선출(LIFO) 형태를 따르는 자료구조라면, 큐는 반대로 선입선출(FIFO, First In First Out) 형태를 따르는 자료구조입니다. 선입선출의 예시로는 은행 업무를 보기 위해 기다리는 사람들의 대기열을 예시로 들 수 있습니다. 가장 먼저 대기표를 뽑은 사람이 가장 먼저 은행 업무를 보게 될 것입니다. 이처럼 큐는 "뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조"를 가지고 있습니다. 즉, 삽입과 삭제가 서로 다른 곳에서 일어납니다. 큐에서 삽입이 일어나는 곳(가장 뒤 부분)을 후단(Rear)이라고 하고, 큐에서 삭제가 일어나는 곳(가장 앞 부분)을 전단(Front)이라고 합니다. E..

레지스터 (Register) 레지스터는 데이터를 일시 저장하거나 전송하는 장치로, 여러 개의 플립플롭을 연결한 플립플롭의 그룹으로 이루어진다. 플립플롭 1개는 1비트 이진 정보를 저장하기에, $N$비트 레지스터는 $N$개의 플립플롭으로 구성되며, $N$비트의 이진 정보를 저장할 수 있다. 레지스터는 여러 비트를 일시적으로 저장하거나 배열된 비트를 좌우로 자리이동을 시키는데 사용된다. 레지스터는 자신의 고유한 기능을 나타내기 위해 머리 글자를 대문자로 나타낸다. 다음이 바로 그 예시이다.`주소 레지스터(Address Registe: AR)`: 기억장치에 대한 주소를 저장하는 레지스터`명령어 레지스터(Instruction Register: IR)`: 현재 실행 중인 명령어 자체를 저장하는 레지스터`프로그램 ..