배열 스택(Array Stack)란? 배열을 이용해 구현한 스택을 의미한다. 배열 리스트와 마찬가지로 물리적으로 연결되어있어야 하며 그에 따라 스택을 생성할 때 무조건 스택의 크기를 미리 지정해 주어야 한다. 각 함수 중간에 AS가 있는데 ArrayStack을 의미한다. 배열 스택의 구현 소스 파일 구성은 다음과 같다. 파일 이름 내용 arraystack.h 구조체 및 함수 선언 arraystack.cpp 함수 구현 arraystackmain.cpp main 함수 실행 1.arraylist.h #pragma once #include using namespace std; #define TRUE 1 #define FALSE 0 typedef struct ArrayStackNode { int data; }; ..

연결 리스트로 구현한 스택 앞서 배운 연결 리스트를 이용하여 구현하는 스택이다. 이러한 방식의 스택의 장점은 미리 스택의 크기를 정하지 않아도 되어 실제 사용하는 자료의 양보다 배열의 크기가 더 클 때 발생하는 메모리 공간 낭비가 일어나지 않는다는 점이다. 그러나 구현은 비교적 어렵다. 연결 리스트로 구현한 스택에서는 노드에 대해 위치 인덱스를 이용한 접근이 불가능하기 때문에 앞서 연결 리스트를 구현했을 때 사용한 헤더 노드와 비슷하게 스택의 탑에 위치한 노드에 접근하기 위한 포인터가 필요하고 push, pop 연산을 실행할 때마다 스택의 탑 노드에 대한 링크를 재설정해주어야 한다. 또한 pop 연산 시 기존에 탑 노드가 사라지면 그다음 위에 있는 노드에 접근할 수 있게 스택의 탑 노드부터 맨 아래에 저..

스택(Stack)이란? 영어 단어 stack은 ‘쌓다‘‘쌓다 ‘라는 뜻이 있고 명사로는 물건들이 쌓여있는 '더미'를 의미한다. 자료구조에서의 스택도 자료를 쌓아두는 기능을 한다. 일반적인 ’더미‘’ 더미‘와 다르게 스택은 스택만의 고유 특성을 가지고 있다. 그 특성은 LIFO(Last-In-First-Out) - 후입선출(後入先出), 즉, 가장 나중에 들어간 자료가 가장 먼저 나오는 자료이다'라는 특성이다. 이러한 특성 때문에 스택에서 자료를 꺼낼 때에는 앞서 배운 리스트와 다르게 가장 나중에 들어간 자료만 꺼낼 수 있다. 추가적으로 스택은 선형 자료구조로, 선형의 의미는 저장된 자료들 사이의 선후관계가 모두 1대11대 1 관계라는 뜻이다. 다시말해 하나의 물건 위에는 오직 하나의 물건만을 쌓을 수 있다..

이중 연결 리스트(Doubly Linked List)란? 이중 연결 리스트는 노드들이 양방향으로 연결되어 있는 연결 리스트를 말한다. 그림과 같이 이중 연결 리스트는 노드들을 양방향으로 연결하기 위해 링크를 2개씩 가지고 있다. 이때 왼쪽으로 가는 링크는 pLLink 오른쪼으로 가는 링크는 pRLink라고 할것이고 이중 연결 리스트에서는 다음과 같은 식이 성립한다. pNode==pNode->pLLink->pRLink; 이중 리스트의 장점 원형 리스트는 양방향으로 연결되어 있기 때문에 어떠한 노드에 접근할때 정해진 방향으로만 가야하는 단순 연결 리스트,원형 연결 리스트에 비해 용이하다. 예를 들어 위치 인데스 position에 존재하는 노드를 이용해 position 이전에 있는 노드에 접근하라고 한다면 단..

원형 연결 리스트(Circular Linked List)란? 기본적인 구조는 단순 연결 리스트와 똑같은 구조지만 맨 마지막 노드의 링크가 NULL값인 단순 연결 리스트와 다르게 원형 연결 리스트에서 맨 마지막 노드의 링크는 맨 처음 노드를 가리킨다. 따라서 노드끼리 연결된 형태가 원형을 이루고 순환구조라는 점에서 차이가 있다. 그림과 같이 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리킨다. 이때 노드가 딱 1개 존재하는 경우가 생길 수도 있는데 이때 그 노드는 첫 번째 이자 마지막 노드이기 때문에 그 노드의 링크는 자기 자신을 가리키게 된다. 원형 리스트의 장점 만약 연결 리스트 위에서 어떠한 위치에 존재하는 노드의 이전에 위치하는 노드를 탐색한다고 가정해보자 단순 연결 리스트에서 현재 노드의 ..

연결 리스트(Linked List)란? 연결 리스트는 배열 리스트와 다르게 포인터를 이용하여 구현한다. 포인터를 이용하여 순차적으로 자료를 연결하기 때문에 물리적으로 각 자료들이 어디에 위치해 있는지 상관이 없어진다. 아래 그림과 같이 각 자료들이 어디에 물리적 위치는 인접해 있지 않지만 자료들은 순차적으로 연결되어 있다. 추가적으로 연결 리스트는 배열 리스트와 다르게 저장 가능한 최대 원소의 개수를 지정해 주지 않아도 된다. 연결 리스트는 자료들끼리 붙어있어야 한다는 물리적 제약이 없기 때문에 그냥 새로운 원소를 생성하고 포인터를 이용해 연결만 잘해주면 된다. 연결 리스트의 구조 배열 리스트의 노드(원소)는 자료(Data)만 담고 있었지만 연결 리스트의 노드는 자료에 다음 노드로 연결되는 링크(Link..

배열 리스트(Array List)란? 배열 리스트는 c 언어에서 사용되는 배열을 통해 구현한 리스트를 말한다. 배열을 구성하는 원소,자료 들이 순서대로 연속하여 메모리에 저장된다. 즉 배열 리스트에서 논리적 순서와 물리적 순서는 같다고 할 수 있다. 위 그림에서 (1)에서 정수형 원소 1,2,3,4가 차례대로 저장되었음을 알 수 있고 (2)를 통해 실제 메모리상에서도 4개의 원소가 차례대로 저장되어 있으므로 논리적인 순서와 물리적인 순서가 같음을 알 수 있다. 또한 (2)를 통해 저장할 수 있는 원소는 최대 6개이고 현재 4개가 저장되어 있음을 알 수 있다. 배열 리스트의 원소 추가 배열 리스트의 기본적인 연산중 하나인 원소 추가 연산을 구현을 어떻게 해야할지 생각을 해보자. 그냥 리스트의 맨 뒤에 원소..

리스트(List)란? 리스트는 가장 단순한 구조를 가지는 기초적인 자료구조이며 스택(Stack), 트리(Tree), 그래프(Graph), 큐(Queue) 등등 다른 자료구조들의 구현에도 사용된다. 리스트는 자료를 순서대로 저장하는 자료구조이다. 여기서 순서는 '한 줄'을 의미하며 여러 개의 자료가 일직선으로 서로 연결된(Sequential) '선형구조‘를 의미한다. 예를 들어 아래 파일을 저장하는 프로그램을 생각해보자 파일이 순서대로 저장되어 있음을 볼 수 있다. 이때 리스트와 배열이 상당히 비슷하다고 생각하는 사람이 있을 것이다. 실제로 매우 비슷하다 하지만 배열과 다르게 원소 중 하나가 제거된다면 그 빈자리를 채워야 하고 또한 중간에 원소를 추가하기 위해서는 뒤에 있는 원소들을 한 칸씩 뒤로 이동시켜..