[자료 구조]#0_선형 자료구조

 

[자료 구조] #0_선형 자료구조

 

선형 자료구조에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 개념
2. 스택
3. 큐
4. 원형 큐
5. 덱
6. 배열
7. 벡터
8. 리스트
9. 이중 연결 리스트

 

#0. 개념

1. 선형 자료구조?

• [정의] : 선형 자료구조는 데이터 항목이 순차적으로 배열되는 자료구조입니다. 선형 자료구조에서 각 항목은 전후 관계를 가지며, 이를 통해 리스트의 처음부터 끝까지 순차적으로 접근할 수 있습니다.
• [종류] : 선형 자료구조의 대표적인 예로 스택, 큐, 배열, 리스트가 있습니다.

 

2. 장점

1. 비교적 빠른 접근 속도 : 선형 자료구조는 데이터가 연속적으로 저장되어 특정 인덱스 혹은  포인터를 통해 빠르게 데이터에 접근할 수 있습니다.
2. 간단한 구현

 

3. 단점

1. 비교적 느린 검색 속도 : 선형 자료구조 안에서 특정 데이터를 검색하는 과정은 모든 데이터들을 확인해야 하므로 검색 속도가 비교적 느립니다.
2. 비 효율적인 삽입/삭제 작업 : 선형 자료구조의 중간에서 데이터의 삽입/삭제 연산이 이루어지면, 추가적으로 데이터들을 이동시키는 작업이 소요되어 비효율적입니다.

 

#1. 스택

1. 스택?

[Basic C++] #64_stack

 

Details

 

• [정의] : 스택은 후입선출 방식으로 동작하는 선형 자료구조로, 지정된 형식의 데이터를 정해진 한 방향으로만 접근/삽입/제거 작업이 가능합니다.

 

2. 접근

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;

    s.push(1); // 스택에 1을 push
    s.push(2); // 스택에 2를 push
    s.push(3); // 스택에 3을 push

    cout << "Top element: " << s.top() << endl; // 스택의 맨 위에 있는 데이터인 3 출력

    s.pop(); // 스택에서 데이터 3을 pop

    cout << "Top element: " << s.top() << endl; // 스택의 맨 위에 있는 데이터인 2 출력

    return 0;
}

 

Details

 

• Stack에 접근하는 방법은 "top"을 사용하는 방법이 유일합니다. 

 

3. 삽입/삭제

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;

    // 스택에 데이터 추가
    s.push(1);
    s.push(2);
    s.push(3);

    // 스택의 크기 출력
    cout << "Stack size: " << s.size() << endl;

    // 스택의 모든 데이터 출력
    cout << "Stack contents: ";
    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    // 스택이 비어있는지 확인
    if(s.empty())
        cout << "Stack is empty" << endl;

    return 0;
}

 

Details

 

• 스택 자료구조에 새로운 항목을 삽입하거나 기존의 항목을 제거하는 방법은 push와 pop입니다.

 

4. 스택의 연산자 표기법

• 스택을 통해 연산을 표기하는 방법은 총 세 가지가 있습니다.
• 첫 번째는 전위 표기법으로 연산자가 피연산자의 앞에 위치하는 방법입니다(eg. + 2 3)
• 두 번째는 중위 표기법으로 연산자가 피연산자의 중간에 위치하는 방법입니다(eg. 2 + 3)
• 세 번째는 후위 표기법으로 연산자가 피연산자의 뒤에 위치하는 방법입니다(eg. 2 3 +)

 

5. 예제-1

bool isBalanced(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char topChar = st.top();
            st.pop();
            if ((c == ')' && topChar != '(') || (c == ']' && topChar != '[') || (c == '}' && topChar != '{')) {
                return false;
            }
        }
    }
    return st.empty();
}

 

Details

 

• 괄호 검사(Parenthesis Matching) 문제는 스택을 사용하여 구현할 수 있는 대표적인 예제입니다. 
• 여는 괄호는 스택에 push 하고, 닫는 괄호가 나오면 pop 하여 검사합니다. 이때, 스택이 비어있거나, 여는 괄호가 닫는 괄호와 짝이 맞지 않으면 오류로 판단합니다.

 

2. 예제-2

#include <iostream>
#include<string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = 0;

    if(s.size()%2 != 0) return answer;

    stack<char> stk;
    for(size_t i=0; i<s.size(); i++)
    {
        if(stk.empty() || stk.top() != s[i])
            stk.push(s[i]);
        else
            stk.pop();
    }

    if(stk.empty())
        answer++;

    return answer;
}

 

Details

 

• Programmers 코딩 테스트 연습 문제 중 "짝 지어 제어하기" 문제입니다.
• 단순히 Stack을 활용해 이전에 삽입한 문자와 현재 문자를 비교해서 두 문자가 같다면 Stack에서 pop 하고, 다르다면 새로운 문자를 push 하는 문제입니다.

 

#2. 큐

1. 큐?

[Basic C++] #67_queue

 

Details

 

• [정의] : 큐는 선입선출 방식으로 동작하는 선형 자료구조로, 지정된 형식의 데이터를 데이터 목록의 한쪽 끝에서는 삽입 작업이 이루어지고, 다른 한쪽 끝에선 삭제 작업이 이루어집니다.

 

2. 접근

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    // Enqueue 3 elements to the queue
    q.push(10);
    q.push(20);
    q.push(30);

    // Display the queue
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
        cout << q.back() << " ";
    }

    return 0;
}

 

Details

 

• 간단하게, STL 컨테이너를 활용해 큐에 대해 살펴봅시다.
• 큐는 스택과 동일하게 임의의 접근이 불가능합니다. 더불어, 한쪽 끝에서 top을 통해 데이터에 접근하는 스택과 달리 queue는 양쪽 끝에서 삽입/제거 작업이 이루어져 front와 back을 통해 양쪽  끝에 저장된 데이터에 접근할 수 있습니다.

 

3. 삽입/제거

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    // 큐에 데이터 삽입
    q.push(1);
    q.push(2);
    q.push(3);

    // 큐의 맨 앞 데이터 제거
    q.pop();

    // 큐의 맨 앞 데이터 출력
    cout << "Front element of the queue: " << q.front() << endl;

    // 큐의 맨 뒤 데이터 출력
    cout << "Back element of the queue: " << q.back() << endl;

    // 큐의 크기 출력
    cout << "Size of the queue: " << q.size() << endl;

    return 0;
}

 

Details

 

• 삽입/제거의 위치와 방법이 제한된 유한 순차 리스트라는 점에서 스택과 동일하지만, 스택과 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 한쪽에서는 제거 작업이 이루어집니다. 따라서, 스택에서 push 한 데이터와 pop 한 데이터는 동일하지만, 큐는 다릅니다.

 

4. 예제-1

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

void bfs(int start, vector<vector<int>>& adjList, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int currNode = q.front();
        q.pop();
        cout << currNode << " ";

        for(int neighbor : adjList[currNode]) {
            if(!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    // 그래프의 인접 리스트를 생성합니다.
    vector<vector<int>> adjList(7);
    adjList[0] = {1, 2};
    adjList[1] = {0, 2, 3};
    adjList[2] = {0, 1, 4};
    adjList[3] = {1, 4, 5};
    adjList[4] = {2, 3, 5};
    adjList[5] = {3, 4, 6};
    adjList[6] = {5};

    // 방문 여부를 저장하는 벡터를 생성합니다.
    vector<bool> visited(7, false);

    // 0부터 시작하는 BFS 탐색을 수행합니다.
    bfs(0, adjList, visited);

    return 0;
}

 

Details

 

• BFS(Breadth First Search) 알고리즘은 큐를 활용하여 가장 짧은 경로를 찾아내는 알고리즘입니다.
• 이때, 방문한 노드를 큐에서 추출하고, 그 노드의 인접 노드를 큐에 삽입하는 동작들을 반복하며 가장 짧은 경로를 찾아냅니다.

 

#3. 원형 큐

1. 원형 큐

• [정의] : 원형 큐는 큐의 한 종류로, 큐의 머리와 꼬리가 연결되어 있는 순환구조를 갖습니다.
• [특징] : 원형 큐는 Head와 Tail의 위치를 추적하여 항목을 삽입/삭제합니다.

 

#include <iostream>
using namespace std;

const int MAX_SIZE = 5; // 배열의 크기 (5보다 작은 수로 설정)
int queue[MAX_SIZE];    // 원형 큐 배열
int head = 0;           // 큐의 머리
int tail = 0;           // 큐의 꼬리

void enqueue(int data) { // 삽입 연산
    int next = (tail + 1) % MAX_SIZE; // 꼬리의 다음 위치 계산
    if (next == head) { // 큐가 가득 찬 경우
        cout << "Queue is full." << endl;
    } else {
        queue[tail] = data; // 데이터 삽입
        tail = next; // 꼬리 위치 갱신
    }
}

int dequeue() { // 삭제 연산
    if (head == tail) { // 큐가 비어있는 경우
        cout << "Queue is empty." << endl;
        return -1;
    } else {
        int data = queue[head]; // 삭제할 데이터 저장
        head = (head + 1) % MAX_SIZE; // 머리 위치 갱신
        return data; // 삭제한 데이터 반환
    }
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    cout << dequeue() << endl; // 1 출력
    enqueue(4);
    enqueue(5);
    enqueue(6); // Queue is full. 출력
    cout << dequeue() << endl; // 2 출력
    cout << dequeue() << endl; // 3 출력
    cout << dequeue() << endl; // 4 출력
    cout << dequeue() << endl; // 5 출력
    cout << dequeue() << endl; // Queue is empty. 출력, -1 반환
    return 0;
}

 

Details

 

• [주의할 점] : 원형 큐는 순환 구조로 Head와 Tail이 동일한 위치를 가리킬 때 해당 큐가 포화 상태인지, 아닌지 구분하기 어렵습니다. 따라서, 큐에 저장할 수 있는 항목의 개수를 큐의 최대 크기보다 하나 작게 정의합니다. 따라서, Head == Tail일 경우는 큐가 비어있는 경우를 의미하고, (Tail+1)% MAX_SIZE == Head일 경우는 큐가 포화상태임을 의미하게 됩니다. 결과적으로, 원형 큐의 한 칸을 비워둠으로써, 큐의 포화상태와 비어있는 상태의 구분을 명확히 할 수 있게 됩니다.

 

#4. 덱(deque)

1. 덱(양방향 큐)

[Basic C++] #68_deque

 

Details

 

• [정의] : 덱(deque)은 큐의 양쪽 끝에서 요소를 추가하거나 삭제할 수 있는 자료구조로, 선입선출 방식의 큐 자료구조의 특징과 후입선출 방식의 스택 자료구조의 특징을 결합한 형태입니다. 이로 인해, 덱은 다양한 상황에서 유연하게 사용됩니다.

 

2. 구현 방법-1

#include <iostream>
using namespace std;

// #1. 배열
const int MAX_SIZE = 100;

class DequeArr
{
private:
	int arr[MAX_SIZE];
	int front, back;

public:
	DequeArr() :front(-1), back(-1) {}

public:
	bool IsEmpty()
	{
		return front == -1;
	}

	bool IsFull()
	{
		return (front == 0 && back == MAX_SIZE - 1) || (front == back + 1);
	}

	int get_front()
	{
		if (IsEmpty())
		{
			cout << "Deque Is Empty!" << endl;
			return -1;
		}

		return arr[front];
	}

	int get_back()
	{
		if(IsEmpty())
		{
			cout << "Deque Is Empty!!" << endl;
			return -1;
		}

		return arr[back];
	}

	void push_front(int val)
	{
		if (IsFull())
		{
			cout << "Deque Is Full!";
			return;
		}

		if (front == -1)
		{
			front = back = 0;
		}
		else if (front == 0)
		{
			front = MAX_SIZE - 1;
		}
		else
		{
			front--;
		}

		arr[front] = val;
	}

	void push_back(int val)
	{
		if (IsFull())
		{
			cout << "Deque Is Full!!" << endl;
			return;
		}

		if (front == -1)
		{
			front = back = 0;
		}
		else
		{
			back = (back + 1) % MAX_SIZE;
		}

		arr[back] = val;
	}

	void pop_front()
	{
		if (IsEmpty())
		{
			cout << "Deque Is Empty!!" << endl;
			return;
		}

		arr[front] = 0;

		if (front == back)
		{
			front = back = -1;
		}
		else
		{
			front = (front + 1) % (MAX_SIZE);
		}
	}

	void pop_back()
	{
		if (IsEmpty())
		{
			cout << "Deque Is Empty!!" << endl;
			return;
		}

		arr[back] = 0;
		if (front == back)
		{
			front = back = -1;
		}
		else
		{
			if (back == 0)
				back = MAX_SIZE - 1;
			else
				back--;
		}
	}

};


int main()
{
	// #1. 배열을 통해 구현한 덱
	DequeArr* dqArr = new DequeArr();

	dqArr->push_front(5);
	dqArr->push_back(3);

	cout << dqArr->get_front() << '\n';
	cout << dqArr->get_back() << '\n';

	delete dqArr;

	return 0;
}

 

Details

 

• 덱(양방향 큐)을 구현하는 첫 번째 방법은 배열을 활용하는 방법입니다. 정확히 말해서, 배열을 통해 구현한 "원형 리스트"를 활용해 덱을 구현하는 방법입니다.

 

3. 구현 방법-2

#include <iostream>
using namespace std;

// #2. 연결 리스트
struct Node
{
public:
	int val;
	Node* prev;
	Node* next;

public:
	Node(int _val):val(_val),prev(nullptr), next(nullptr) {}
};

class DequeList
{
private:
	Node* front;
	Node* back;

public:
	DequeList():front(nullptr), back(nullptr) {}

public:
	bool IsEmpty()
	{
		return front == nullptr;
	}

	int get_front()
	{
		if (IsEmpty())
		{
			cout << "Deque Is Empty!!" << endl;
			return -1;
		}
		
		return front->val;
	}

	int get_back()
	{
		if (IsEmpty())
		{
			cout << "Deque Is Empty!!" << endl;
			return -1;
		}

		return back->val;
	}

	void push_front(int val)
	{
		Node* newNode = new Node(val);
		if (IsEmpty())
		{
			front = back = newNode;
		}
		else
		{
			newNode->next = front;
			front = newNode;
		}
	}

	void push_back(int val)
	{
		Node* newNode = new Node(val);
		if (IsEmpty())
		{
			front = back = newNode;
		}
		else
		{
			newNode->prev = back;
			back = newNode;
		}
	}

	void pop_front()
	{
		if (IsEmpty())
		{
			cout << "Deque Is Empty!!" << endl;
			return;
		}
		
		Node* frontNode = front;
		if (front == back)
		{
			front = back = nullptr;
		}
		else 
		{
			front = front->next;
			front->prev = nullptr;
		}

		delete frontNode;
	}

	void pop_back()
	{
		if (IsEmpty())
		{
			cout << "Deque Is Empty!!" << endl;
			return;
		}
		
		Node* backNode = back;
		if (front == back)
		{
			front = back = nullptr;
		}
		else
		{
			back = back->prev;
			back->next = nullptr;
		}

		delete backNode;
	}

};


int main()
{
	// #2. 연결 리스트를 통해 구현한 덱
	DequeList* dqList = new DequeList();

	dqList->push_front(7);
	dqList->push_back(10);

	cout << dqList->get_front() << '\n';
	cout << dqList->get_back() << '\n';

	delete dqList;

	return 0;
}

 

Details

 

• 덱(양방향 큐)를 구현하는 두 번째 방법은 연결 리스트를 활용하는 방법입니다.

 

#5. 배열

1. 배열?

• [정의] : 배열은 동일한 형식을 가진 여러 개의 요소가 메모리에 연속적으로 저장되는 선형 자료구조입니다. 
• [특징] : 배열은 그 크기가 컴파일 시점에 결정되어 기존에 할당받은 메모리 공간을 런 타임에 해제하는 것이 불가능합니다.
• [성능] : 배열의 각 항목은 인덱스를 통해 임의의 접근이 가능합니다. 따라서, 빠른 접근 성능을 보여줍니다.
• [주의할 점] : 배열은 선형 리스트와 같은 말입니다.

 

2. 접근

#include <iostream>

int main() {
    // 배열의 선언 및 초기화
    int arr[5] = { 1, 2, 3, 4, 5 };

    // 각 요소에 접근하여 출력
    for (int i = 0; i < 5; i++) {
        std::cout << "arr[" << i << "] = " << arr[i] << std::endl;
    }

    return 0;
}

 

Details

 

• operator []를 통해 특정 항목에 임의의 접근이 가능합니다.

 

#6. 벡터

1. 벡터(Vector)

[Basic C++] #33_Vector, 순차 컨테이너

 

• [정의] : C++에서 제공하는 vector는 지정된 형식의 요소를 가변 크기의 선형 리스트(배열)에 저장하는 순차 컨테이너입니다.
• [특징] : 배열과 같이 벡터 또한 모든 요소에 대한 임의의 접근을 빠른 성능으로(O(1)) 제공하며, 마지막 위치에서 수행하는 삽입 작업은 O(1) 그리고 중간 위치에서 수행하는 삽입/삭제 작업은 O(n)의 성능을 제공합니다.

 

2. 구현

#include <iostream>
using namespace std;

class Vector {
private:
    int size; // 벡터의 크기
    int capacity; // 벡터의 용량
    int* arr; // int형 배열 포인터

public:
    Vector() { // 생성자
        size = 0;
        capacity = 1; // 용량은 1로 초기화
        arr = new int[capacity]; // 동적 메모리 할당
    }

    void push_back(int value) { // 요소 추가
        if (size == capacity) { // 용량 초과 시
            int* temp = new int[2 * capacity]; // 2배 크기의 새로운 배열 할당
            for (int i = 0; i < capacity; i++) {
                temp[i] = arr[i]; // 요소 복사
            }
            delete[] arr; // 기존 배열 삭제
            arr = temp; // 새로운 배열로 대체
            capacity *= 2; // 용량 2배로 증가
        }
        arr[size++] = value; // 요소 추가
    }

    void pop_back() { // 요소 삭제
        if (size > 0) {
            size--; // 크기 감소
        }
    }

    int operator[](int index) { // 인덱스 연산자 오버로딩
        return arr[index];
    }

    int get_size() { // 크기 반환
        return size;
    }
};

int main() {
    Vector v; // Vector 객체 생성
    v.push_back(1); // 요소 추가
    v.push_back(2);
    v.push_back(3);
    cout << "Size: " << v.get_size() << endl; // 크기 출력

    v.pop_back(); // 요소 삭제
    cout << "Size: " << v.get_size() << endl; // 크기 출력

    for (int i = 0; i < v.get_size(); i++) { // 벡터의 모든 요소 출력
        cout << v[i] << " ";
    }
    cout << endl;

    return 0;
}

 

Details

 

• 벡터를 배열(선형 리스트)을 통해 구현한 코드입니다.
• 주요 포인트는 포화 상태의 배열에 새로운 항목을 삽입할 때, 새롭게 메모리 할당을 받아 기존에 배열에 저장되어 있던 항목들을 새롭게 할당받은 배열로 옮기는 작업입니다. 이처럼, vector는 가변 크기의 선형 리스트이며, 새로운 항목이 삽입될 때 새롭게 메모리 할당을 받는 작업을 수행합니다.

 

 

#7. 연결 리스트

1. 연결 리스트                   

[자료구조]#1_연결 리스트(Linked List)

 

Details

 

• [개념] : 연결 리스트는 노드 기반의 선형 자료구조로, 각 노드는 데이터 필드와 다음 노드를 가리키는 포인터로 구성되어 있습니다. 각 노드의 논리 저장 순서는 물리 저장 순서와 일치하지 않습니다.
• [특징] : 연결 리스트는 그 크기가 고정되어 있지 않아, 런 타임에 그 크기를 변경하는 것이 가능합니다.
• [접근] : 연결 리스트는 인덱스를 활용한 임의의 접근이 불가능합니다. 따라서, 특정 노드에 접근하기 위해선, 연결 리스트의 머리부터 순차적으로 탐색하는 방법이 있습니다.
• [삽입/제거] : 연결 리스트는 그 크기가 고정되어 있지 않아, 런 타임 중 언제든 새로운 노드를 삽입하고 삭제하는 작업이 가능합니다.

 

2. advance()를 활용한 인덱스 구현

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {1, 2, 3, 4, 5}; // 리스트 생성

    // 인덱스 위치에 요소 추가
    int index = 2;
    list<int>::iterator it = myList.begin(); // 첫 번째 요소를 가리키는 iterator
    advance(it, index); // it을 index만큼 앞으로 이동
    myList.insert(it, 10); // it이 가리키는 위치에 10 추가

    // 리스트 출력
    for (int n : myList) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

 

Details

 

• [임의의 접근] : 연결 리스트는 특저 항목에 임의의 접근하는 것이 불가능합니다.
• [advance()] : 이때, 반복자를 advance() 함수를 통해 반복자를 이동시켜 특정 항목에 접근 혹은 삽입/삭제 동작을 수행할 수 있습니다.

 

#8. 이중 연결 리스트

1. 이중 연결 리스트

[자료구조]#3_이중 연결 리스트(Double Linked List)

 

Details

 

• [정의] : 이중 연결 리스트는 각 노드가 전후 노드를 가리키는 두 개의 포인터를 갖는 연결 리스트입니다.