3:56

1. perror / strerror

1) perror

<stdio.h>
void perror(const char *s);

- 입력받은 문자열과 errno에 대한 오류 메시지 결합하여 출력

- 오류가 발생하면 해당 오류 코드가 errno에 저장되는데 이를 가져와서 출력하는 것임

2) strerror

<string.h>
char *strerror(int errnum);

- 오류 코드를 매개변수로 받아 해당 오류코드에 대한 오류 메시지를 반환

- 문자열을 반환하므로  printf 함수와 함께 사용해야 함

2. access

#include <unistd.h>
int access(const char *path, int mod);

- 파일이나 디렉토리에 대한 접근 권한을 확인하는 데 사용

- 접근 권한 확인 후 성공하면 0, 실패하면 -1을 반환

- F_OK : 파일의 존재 여부 확인 / R_OK : 읽기 권한 확인 / W_OK : 쓰기 권한 확인 / X_OK : 실행 권한 확인

3. dup / dup2

int dup(int oldfd);

- oldfd로 지정된 파일 디스크립터를 복제하여 새로운 파일 디스크립터를 생성

- 성공시 새로운 파일 디스크립터를 반환하며, 실패시 -1을 반환

#include <unistd.h>
int dup2(int oldfd, int newfd);

- oldfd로 지정된 파일 디스크립터를 newfd로 지정된 파일 디스크립터로 복제

- newfd가 이미 열려 있는 경우, new_fd를 닫고 oldfd를 복제하여 newfd로 사용

- 위 경우 표준 출력의 내용이 output.txt에 기록

4. execve

#include <unistd.h>
int execve(const char * pathname, char *const argv[], char *const envp[]);

- 지정된 경로 (pathname)의 프로그램 파일을 실행하고, 실행 중인 프로세스의 이미지를 해당 프로그램으로 교체 한 뒤 argv와 envp의 내용을 새로운 프로그램에 전달

5. fork

#include <unistd.h>
pid_t fork(void);

- 기존 프로세스에서 새로운 자식 프로세스를 생성 (각 프로세스는 동일한 코드와 상태를 가지지만, 서로 다른 프로세스 ID(PID)를 가짐

- 자식 프로세스인 경우 0을 반환하며, 부모 프로세스인 경우 현재 프로세스가 복제되어 자식 프로세스가 생성

6. pipe

- 파이프는 두 개의 파일 디스크립터로 이루어진 단방향 통신 채널로, 한 쪽에서 쓰여진 데이터를 다른 쪽에서 읽을 수 있게 해 줌

#include <unistd.h>
int pipe(int pipefd[2]);

-pipe() 함수는 프로세스 간 통신을 위해 사용되며, 파이프를 통해 데이터를 안전하게 전송

- pipefd[0]은 읽기용 파일 디스크립터를 저장,  pipefd[1]은 쓰기용 파일 디스크립터를 저장

-pipe() 함수를 호출하면 파이프가 생성되고, 연결된 파일 디스크립터를 pipefd 배열에 저장

- 파이프는 프로세스간 통신 방법 중 하나로, 파이프는 읽기를 위한 파일 디스크립터와 쓰기를 위한 파일 디스크립터, 총 2개로 이루어짐

- 한 프로세스가 파이프의 쓰기용 파일 디스크립터를 통해 데이터를 파이프에 쓰면 다른 프로세스가 읽기용 파일 디스크립터를 통해 읽음

- fork() 함수가 호출되면 부모프로세스와 거의 동일한 자식 프로세스가 생성.

- fork()를 호출한 후에는 두 프로세스(부모와 자식)이 있으므로, 한 프로세스에서는 else if 블록이 실행되고, 다르 프로세스에서는 else 블록이 실행]

- 따라서 위의 코드를 실행하면 부모 프로세스가 "Hello, child!"라는 메시지를 자식 프로세스로 전달하고, 자식 프로세스는 해당 메시지를 받아 출력

7. unlink

- 파일 시스템에서 파일을 삭제하는데 사용되는 함수로, 해당 파이르이 디렉토리 엔트리를 제거하여 파일을 삭제

- 삭제 성공하면 0, 실패하면 -1.

#include <unistd.h>
int unlink(const char *pathname);

- 상대경로, 절대경로 둘 다 사용할 수 있음

8. wait / waitpid

1) wait

-부모 프로세스가 자식 프로세스가 종료될 때까지 기다리도록 하는 역할

#include <sys/types.h>
pid_t wait(int *status);

- status 매개변수를 통해 어떤 방식으로 자식 프로세스가 종료 되었는지를 부모 프로세스가 알 수 있음

- 종료한 자식 프로세스의 프로세스 pid를 반환

* 넘겨주었던 status를 아래와 같은 매크로에 넣어 종료 상태를 확인할 수 있음.

#include <sys/wait.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
    pid_t pid = fork();
    
    if (pid == -1) {
        perror("fork failed");
        return 1;
    } else if (pid == 0) {
        // This is the child process.
        printf("I'm the child process.\n");
        exit(7);
    } else {
        // This is the parent process.
        printf("I'm the parent process.\n");
        
        int status;
        pid_t child_pid = wait(&status);
        
        if (WIFEXITED(status)) {
            printf("Child %d ended normally. Exit status: %d\n", child_pid, WEXITSTATUS(status));
        } else {
            printf("Child %d ended abnormally.\n", child_pid);
        }
    }
    
    return 0;
}

2) waitpid

- 자식 프로세스의 상태 변화를 기다리는데 사용되며, wait() 함수보다 더 풍부한 기능을 제공

pid_t waitpid(pid_t pid, int *status, int options);

1.  가상머신이란?

1) 정의 및 작동 방식

가상머신 : 물리적 컴퓨터와 동일한 기능을 제공하는 소프트웨어 컴퓨터

- 기본적으로 컴퓨터는 하드웨어 위에 운영체제가 올라가있고, 그 위에서 응용 프로그램이 작동하는 방식으로 동작. 이 때 메모리에 상주하는 운영체제의 핵심 부분을 커널이라고 한다.

- 가상머신은 하나의 물리적인 컴퓨터에서 여러개의 독립적인 가상환경을 생성하여 동작시키는 기술

-  하이퍼바이저는 가상머신의 생성, 자원 할당, 네트워킹, 저장장치 관리, 보안 등을 처리하며, 가상머신들 간의 리소스 분할과 격리를 관리하여 각각의 가상머신이 독립적으로 동작 할 수 있도록 한다.

- 도커는 컨테이너 기술을 사용하여 호스트 시스템의 운영체제를 공유하기 때문에 더 가볍고 효율적인 리소스 사용이 가능

2) 목적

- 하나의 컴퓨터로 동시에 서로 다른 2개 이상의 운영체제를 실행하고 싶을 때

- 하나의 컴퓨터의 자원을 여러 명에게 나누어주고자 하는데 각 사용자 간 상호 간섭을 없애고 싶을 때

- 컴퓨터의 다른 영역에 영향을 주지 않는 독립적인 환경을 만들고 싶을 때

- 각 가상머신은 다른 가상머신과 격리되어 있으며, 서로의 운영체제와 애플리케이션에 영향을 주지 않는다. 또한 물리적인 하드웨어와 독립적이므로 다른 호스트 컴퓨터로 이동하거나 클라우드 환경에서 실행될 수 있다.

2. 파티션과 LVM(Logical Volume Manager)

파티션 : 물리적인 디스크를 여러 논리적인 섹션으로 분할하는 것. 일반적으로 운영체제, 응용 프로그램, 데이터 등을 구별하기 위해 사용

LVM : 물리적인 디스크를 논리적인 단위로 관리하는 프레임워크. 논리적인 디스크 공간을 필요에 따라 동적으로 변경하거나 재분배 할 수 있다.

파티션이 디스크를 분할하는데 초점을 맞춘 기법이라면, LVM은 디스크를 분할하고 합치고 크기를 동적으로 조정하는 등 더욱 유연한 디스크 관리를 가능하게 한다.

리눅스 시스템에서는 하나의 하드디스크에 최대 4개의 기본 파티션을 생성할 수 있으며, 필요에 따라 더 많은 파티션을 생성하고 싶을 때 확장 파티션을 생성한다. 즉, 4개 이상의 파티션이 필요하면 하나의 파티션을 확장 파티션으로 잡고 확장 파티션 내에서 다시 논리 파티션을 구분하는 방식으로 우회하는 것이다. 

위 사진은 가상머신에서 리눅스 파일 시스템 계층 구조를 간략하게 구현한 것이다.

3.Sudo

- 'super user do'의 약자로, 각종 명령어 앞에 sudo를 붙이면 최고 관리자 권한으로 실행된다.

- etc/sudoer 설정 파일에 명시된 사용자만 사용 가능하다.

- Deafult env_reset : sudo를 사용할 때 사용자가 시스템의 환경변수만 사용되게 하도록 제한. 환경변수가 예기치 않게 변경되어 의도하지 않은 동작을 유발 하지 않도록 함.

- mail_badpass : 비밀번호를 잘못 입력한 경우, 이 설정에 따라 알림 이메일이 관리자에게 전송.

- secure_path : sudo를 사용하여 실행할 수 있는 명령어의 경로를 제한. 이를 통해 sudo를 사용하는 사용자가 임의의 명령어를 실행하는 것을 방지.

- authfail_message : 비밀번호 인증에 실패한 경우에 표시되는 메시지를 지정. %d는 실패한 비밀번호 시도 횟수를 나타내는 특수한 플레이스 홀더.

- badpass_message : 잘못된 비밀번호를 입력했을 때 나타나는 오류 메시지.

- log input/log output : sudo를 사용하여 실행한 명령어의 입력과 출력을 로그 파일에 기록

- requiretty : sudo를 사용하여 실행되는 명령이 tty(터미널)가 필요로 하는지를 지정

- iolog_dir : sudo 사용 로그파일의 디렉터리 경로를 지정

- passwd_tries : 사용자가 비밀번호를 재시도 할 수 있는 최대 횟수를 지정

해당 항목은 사용자별로 sudo를 사용할 수 있는 특권을 지정하는 부분으로, 각 줄의 구조는 "사용자명 호스트 = (실행할 사용자 : 실행할 그룹) 실행할 명령"을 의미한다.

따라서 위의 경우 모든 호스트(컴퓨터)에서 모든 사용자/모든 그룹으로 어떤 명령이든 실행 할 수 있도록 권한을 부여한 것이다.

특정 사용자에게 sudo 권한을 부여하려면 '/etc/sudoers' 파일에서 권한 부여를 해주고, sudo group에 추가까지 마쳐야 한다.'

4. UFW (Uncomplicated Fire Wall)

- iptable 기반의 간단하고 사용하기 쉬운 방화벽 설정 도구

- 특정 포트, IP 주소 또는 서비스에 대한 접근을 허용하거나 거부하는 규칙을 설정할 수 있음

- 허용되거나 거부된 트래픽에 대한 로그를 기록

- 포트는 컴퓨터와 외부 네트워크간의 통신을 위한 창구로 작동하므로, 특정 포트만 허용함으로써 악의적인 사용자들이 해당 포트를 통해 시스템에 엑세스하거나 공격하는 것을 방지 할 수 있음.

- 트래픽 제어 가능 (예컨대 웹 서버를 운영하는 경우 80번 포트만 허용하여 웹 트래픽을 처리하고, 다른 포트는 차단함으로써 비웹 트래픽을 제한).

5. SSH (Secure Shell)

- 네트워크상에서 안전한 원격 접속을 제공하는 프로토콜

- ssh는 데이터 통신을 암호화해서 보호하며, 무결성을 위해 암호화화 함께 메시지 무결성 체크를 사용, 공개키 기반 인증을 사용.

- ssh 나오기 전 사용하기 전 사용하던 telnet의 경우 평문으로 통신하며 무결성 체크를 지원하지 않고, 패스워드 인증을 사용.

- ssh 포트를 22번에서 4242번으로 변경 : 많은 공격자들이 기본적으로 사용되는 22번 포트를 대상으로 공격을 시도하므로, 포트 번호를 변경함으로써 보안을 강화

- ssh를 통해 root 권한으로 직접 접속하지 못하게 제한 : root는 시스템에서 최고 관리자 권한을 가지고 있으므로 일반 사용자에 대한 공격보다 훨씬 위험하기 때문에 root로의 직접적인 ssh 접속을 차단

6. 비밀번호 정책설정

- 암호는 30일마다 만료

- 비밀번호를 수정하기 전에 허용되는 최소 일 수는 2

- 암호가 만료되기 7일 전에 경고 메시지를 전송

- 최대 시도 횟수 : 3회

- 최소 길이 : 10

- 기존 암호와 달라야 하는 문자의 개수 : 7

- 대문자 1개 이상 포함, 소문자 1개 이상 포함, 숫자 1개 이상 포함

- 비밀번호에 유저명이 포함되어서는 안 됨

- 루트 계정에도 해당 규칙 적용

- 같은 문자가 3번 이상 반복되면 안 됨

* pam_pwquality

- pam(Pluggable Authentication Modules) : Linux 시스템에서 인증과 관련된 작업을 처리하는데 사용되는 프레임워크

- libpam -pwquality :  PAM을 확장하여 패스워드의 품질과 보안을 강화하는데 사용되는 모듈

pam을 사용하기 이전 리눅스 시스템에서는 각 응용 프로그램이 사용자 인증을 위해 자체적으로 로직을 구현하여 사용했기 때문에, 사용자 정보가 담긴 주요 시스템 파일인 '/etc/passwd'에 대한 접근 권한을 가지고 있어야 했다. 그러나 응용 프로그램이 사용자 정보가 담긴 주요 시스템 파일에 대한 직접적인 접근 권한을 가지고 있을 경우 보안과 관련한 위협이 있기 떄문에 pam이 등장하게 되었다.  pam을 사용하면 인증이 필요한 응용 프로그램은 더 이상 passwd 파일을 열람하지 않고 pam 모듈에 사용자 인증을 요청하며, pam은 요청한 사용자의 정보를 가지고 결과를 도출하여 응용 프로그램에 전달한다.

7. CRON

Unix 및 Unix 기반 시스템에서 주기적인 작업을 예약하기 위해 사용되는 시간 기반 작업 스케줄러. 'crontab' 파일을 사용하여 작업을 정의하며, 정의된 작업은 지정된 시간 간격에 따라 실행 된다.

- crontab -e 명령어는 crontab 파일을 편집하기 위해 사용되는 명령어.

- crontab -e 는 현재 사용자의 개인적인 crontab 파일을 편집하며, /etc/crontab 파일은 시스템 전체의 cron 작업을 관리.

- 위 경우 10분마다 /home 디렉토리의 monitoring.sh 파일을 출력.

1. Heap이란?

• 힙은 우선순위 큐의 대표적인 자료구조이다.
• 우선순위큐란 원소에 우선순위가 가장 큰 원소부터 접근이 가능한 자료구조이다.
• 힙의 대표적인 종류로는 최대힙, 최소힙이 있으며 최대힙은 키값이 큰 원소가 높은 우선순위를, 최소힙은 키값이 작은 원소가 높은 우선순위를 가진다.
• 최대힙 - 부모 노드의 원소가 자식 노드의 원소보다 크거나 같은 완전 이진트리
• 최소힙 - 부모 노드의 원소가 자식 노드의 원소보다 작거나 같은 완전 이진트리
• 힙에서 삽입 및 삭제의 시간 복잡도는 O(log2n)이다.

2. (최대)Heap 구현하기

구현할 내용은 아래와 같다.

• heapifyUp(int i) - i번째 인덱스의 값을 부모 노드와 비교하여, 부모 노드의 값이 더 작으면 자리를 교환한다.
• heapifyDwon(int i) - i번째 인덱스의 값을 자식 노드 두 개와 비교하여, 둘 중 큰 자식노드보다 i번째 인덱스 값이 더 작으면 자리를 교환한다.
• insert(E x) - 힙의 적절한 자리에 입력받은 값 x를 입력한다.
• delete() - 루트 노드에 있는 값을 삭제한다.
• max() - 루트 노드에 있는 값을 리턴한다.
• isEmpty() - 힙이 비어있으면 true, 그렇지 않으면 false를 리턴한다.
• clear() - 힙의 모든 내용물을 비운다.
• printAll() - 힙의 모든 내용물을 출력한다.

** 원래 힙에서는 맨 앞의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.

1) 인터페이스

public interface heapInterface<E> {
	
	public void insert (E x);
	
	public void delete();
	
	public E max();
	
	public boolean isEmpty();
	
	public void clear();
	
	public void printAll();
	
}

2) 클래스

- 필드 영역

    //필드 영역
	private E[] item;
	private int size;

• item[] - 원소를 저장한다.
• size - 배열에 저장된 원소의 개수를 저장한다.

- 생성자 영역

	//생성자 영역
	public heap(int arraySize) {
		item = (E[]) new Comparable [arraySize];
		size=0;
	}

• 배열의 크기를 입력받아 해당 크기의 배열을 생성한다. size변수는 0으로 초기화한다.

- 메서드 영역

<heapifyUp 메서드 구현>

	private void heapifyUp(int i) {
		
		if (i<0 || i>=item.length) {
			throw new IllegalArgumentException();
		} else {
		int parent = (i-1)/2;
		
		if (((Comparable) item[parent]).compareTo(item[i])<0) {
			E tmp = item[i];
			item[i] = item[parent];
			item[parent] = tmp;
			
		heapifyUp(parent);
			}
		}
	}

• parent 변수에 입력받은 인덱스 노드의 부모 인덱스를 저장한다.
• 만약 입력받은 인덱스 노드의 값보다 부모 노드의 값이 작으면 값을 바꾼다.
• 부모 노드와 인덱스 노드의 값이 같거나, 부모 노드 값이 더 클 때까지 부모 노드에 대하여 해당 과정을 반복한다.
• 만약 입력 받은 인덱스가 범위를 벗어났다면 에러를 리턴한다.

<heapifyDown 메서드 구현>

	private void heapifyDown(int i) {
		
		int left = 2*i+1;
		int right = 2*i+2;
		int max = i;
		if (i<0 || i>item.length) {
			throw new IllegalArgumentException();
		} else {
			if (left <=size-1) {
		if (((Comparable) item[max]).compareTo(item[left])<0) {
			max = left;
		} 
		if (((Comparable) item[max]).compareTo(item[right])<0) {
			max = right;
		}
		
		if (max!=i) {
			E tmp = item[i];
			item[i] = item[max];
			item[max] = tmp;
			
			heapifyDown(max); }
			}
		}
	}

• left 변수에 입력받은 인덱스 노드의 왼쪽 자식 노드 인덱스, right 변수에 오른쪽 자식 노드 인덱스를 저장한다.
• max 변수에 입력받은 인덱스를 저장한다.
• left 변수가 범위를 벗어나지 않는 동안 아래 과정을 반복한다.
• max 인덱스의 값과 left, right 인덱스 값을 비교하여 max 인덱스에 가장 큰 값의 인덱스가 들어오게 한다.
• max의 값이 입력받은 값과 다르면(자식 노드중에 더 큰 값이 있다면) 입력 받은 인덱스 노드와 max 인덱스 노드의 자리를 바꾼다.
• 입력받은 인덱스가 범위를 벗어났다면 에러를 리턴한다.

<insert 메서드 구현>

	@Override
	public void insert(E x) {
		if (size==item.length) {
			throw new IllegalArgumentException();
		} else {
		item[size]=x;
		heapifyUp(size);
		size++;
		}
	}

• 힙의 끝에 입력받은 값을 추가한다.
• heapifyUp을 통해 해당 노드가 적절한 자리를 찾게 한다.
• size 변수를 1 증가시킨다. 
• 만약 힙에 빈 자리가 없었다면 에러를 리턴한다.

<delete 메서드 구현>

	@Override
	public void delete() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		item[0]=item[size-1];
		size--;
		heapifyDown(0);
		}
	}

• 힙의 맨 끝자리에 있던 노드를 루트 노드 자리로 옮긴다.
• size 변수를 1 감소시킨다.
• heapifyDown을 통해 루트 노드 자리의 노드가 적절한 자리를 찾게 한다.
• 만약 힙이 비어 있었다면 에러를 리턴한다.

<max 메서드 구현>

	@Override
	public E max() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		return item[0];
			}
		}

• 힙이 비어 있다면 에러를 리턴하고, 그렇지 않다면 루트 노드의 값을 리턴한다.

<isEmpty 메서드 구현>

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

• size 변수가 0인지 여부를 리턴한다.

<clear 메서드 구현>

	@Override
	public void clear() {
		item = (E[]) new Comparable [size];
		size=0;
	}

• item 배열과 size 변수를 초기화한다.

<printAll 메서드 구현>

	@Override
	public void printAll() {
		for (int i=0; i<size; i++) {
			System.out.print(item[i]+" ");
		}

• 인덱스 0부터 배열 끝까지 순회하며 해당 인덱스의 값을 출력한다.

-전체 코드

public class heap<E> implements heapInterface<E> {
	
	//필드 영역
	private E[] item;
	private int size;
	
	//생성자 영역
	public heap(int arraySize) {
		item = (E[]) new Comparable [arraySize];
		size=0;
	}
	
	//메서드 영역
	
	private void heapifyUp(int i) {
		
		if (i<0 || i>=item.length) {
			throw new IllegalArgumentException();
		} else {
		int parent = (i-1)/2;
		
		if (((Comparable) item[parent]).compareTo(item[i])<0) {
			E tmp = item[i];
			item[i] = item[parent];
			item[parent] = tmp;
			
		heapifyUp(parent);
			}
		}
	}
	
	private void heapifyDown(int i) {
		
		int left = 2*i+1;
		int right = 2*i+2;
		int max = i;
		if (i<0 || i>item.length) {
			throw new IllegalArgumentException();
		} else {
			if (left <=size-1) {
		if (((Comparable) item[max]).compareTo(item[left])<0) {
			max = left;
		} 
		if (((Comparable) item[max]).compareTo(item[right])<0) {
			max = right;
		}
		
		if (max!=i) {
			E tmp = item[i];
			item[i] = item[max];
			item[max] = tmp;
			
			heapifyDown(max); }
			}
		}
	}
	
	@Override
	public void insert(E x) {
		if (size==item.length) {
			throw new IllegalArgumentException();
		} else {
		item[size]=x;
		heapifyUp(size);
		size++;
		}
	}

	@Override
	public void delete() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		item[0]=item[size-1];
		size--;
		heapifyDown(0);
		}
	}

	@Override
	public E max() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		return item[0];
			}
		}

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

	@Override
	public void clear() {
		item = (E[]) new Comparable [size];
		size=0;
	}

	@Override
	public void printAll() {
		for (int i=0; i<size; i++) {
			System.out.print(item[i]+" ");
		}
		
	}

}

3) 결과 확인하기

- 코드

public class Test {
	public static void main(String[] args) {
	
		heap<Integer> lst = new heap<>(64);
		
		lst.insert(100);
		
		lst.insert(300);
		
		lst.insert(400);
		
		lst.insert(200);
		
		lst.printAll();
		
		System.out.println();
		
		//100,200,300,400을 차례로 입력하고 출력합니다.
		
		lst.delete();
		
		lst.printAll();
		
		System.out.println();
		
		lst.delete();
		
		lst.printAll();
		
		System.out.println();
		
		//루트에 해당하는 값을 삭제하고 출력합니다.
		
		System.out.println(lst.isEmpty());
		
		System.out.println(lst.max());
		
		//lst가 비었는지 여부와 현재 루트에 있는 값을 출력합니다.
		
		
	}
}

- 결과

1. Queue란?

• 먼저 들어온 데이터가 먼저 나간다. 즉, 선입선출(FIFO) 방식이다.
• 맨 앞의 원소에만 접근이 가능하다. 

cf) 연결리스트로 큐 구현하기

연결 리스트로 큐를 구현할 때는 tail에 큐의 마지막 노드를 저장하고 tail이 next로 큐의 첫 번째 값을 참조하게 한다.

2. Queue 구현하기

구현할 내용은 아래와 같다.

• enqueue(E x) - 원소 x를 큐의 끝에 추가한다.
• dequeue() - 큐의 가장 앞에 있는 원소를 삭제한다.
• front() - 큐의 가장 앞에 있는 원소를  리턴한다.
• isEmpty() - 큐가 비어있으면 true, 그렇지 않으면 false를 리턴한다.
• dequeueAll() - 큐에 있는 모든 원소를 삭제한다.
• printAll() - 큐의 모든 원소를 순서대로 출력한다.

** 원래 큐에서는 맨 앞의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.

1) 노드 클래스

public class Node<E> {

	public E item;
	public Node<E> next;
	
	public Node (E newItem) {
		item = newItem;
		next = null;
	}
	
	public Node (E newItem, Node<E> nextNode) {
		item = newItem;
		next = nextNode;
	}
}

• item 변수에 데이터를 저장한다.
• next 변수에 다음 노드를 저장한다. next는 다음 노드의 위치를 가리키는 포인터가 된다.
• 첫 번째 생성자는 데이터를 입력받아 데이터를 item에 저장하고, 포인터 값은 null로 저장한다.
• 두 번째 생성자는 데이터와 다음 노드를 입력받아 데이터를 item에 저장하고, 포인터 값에 다음 노드를 저장한다.

2) 인터페이스

public interface QueueInterface<E> {

	public void enqueue(E x);
	
	public void dequeue();
	
	public E front();
	
	public boolean isEmpty();
	
	public void dequeueAll();
	
	public void printAll();
	
}

3) LinkedQueue 클래스

- 필드 & 생성자 영역

	//필드 영역
	private Node<E> tail;
	int size=0;
	
	//생성자 영역
	public LinkedQueue() {
		tail=null;
	}

• tail - 큐의 가장 끝 노드를 저장한다. (최근에 들어온 값)
• size - 큐 원소의 개수를 저장한다.
• 생성자 - tail에 null 값을 할당한다.

** 사실 위 메서드 중 printAll을 구현하지 않는다면 size는 필요하지 않다.

- 메서드 영역

<enqueue 메서드 구현>

	@Override
	public void enqueue(E x) {
		Node<E> newNode = new Node<>(x);
		if (isEmpty()) {
			tail = newNode;
			tail.next=tail;
		} else {
			newNode.next=tail.next;
			tail.next=newNode;
			tail=newNode;
		}
		size++;
	}

• 입력 받은 값 x를 가지는 새 노드를 생성한다.
• 만약 첫 노드라면 tail에 newNode를 입력하고 tail이 next로 스스로를 참조하게 한다.
• 그렇지 않다면 새 노드가 front를 참조하고, tail이 새 노드를 참조하게 한다.
• tail 값에 newNode를 입력한다.

<dequeue 메서드 구현>

	@Override
	public void dequeue() {
		if (isEmpty()) {
			System.out.println("ERROR");
		} else {
			if (tail.next==tail) {
				tail = null; 
			} else {
				tail.next=tail.next.next;
			}
		}
		size--;
	}

• 만약 큐가 비어 있다면 에러를 출력한다.
• 만약 큐에 원소가 한 개라면 tail 값에 null을 입력한다.
• 큐에 원소가 여러 개라면 tail이 next로 기존 front값을 생략하고 그 다음 노드를 참조하게 한다.

<front 메서드 구현>

	@Override
	public E front() {
		if (isEmpty()) {
			return null;
		} else {
		return tail.next.item;
		}
	}

• 만약 큐가 비어 있다면 null을 리턴한다.
• 그렇지 않다면 front의 item값을 출력한다.

<isEmpty 메서드 구현>

	@Override
	public boolean isEmpty() {
		return (tail==null);
	}

• tail==null 이면 true, 아니면 false를 리턴한다.

<dequeueAll 메서드 구현>

	@Override
	public void dequeueAll() {
		tail=null;
		size=0;
	}

• tail과 size를 초기화한다.

<printAll 메서드 구현>

	@Override
	public void printAll() {
		Node<E> currNode=tail;
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			System.out.print(currNode.item+" ");
		}
	}

• front부터 size만큼 큐를 순회하며 해당 노드의 item값을 출력한다.

- 전체 코드

public class LinkedQueue<E> implements QueueInterface<E> {

	//필드 영역
	private Node<E> tail;
	int size=0;
	
	//생성자 영역
	public LinkedQueue() {
		tail=null;
	}
	
	//메서드 영역
	
	@Override
	public void enqueue(E x) {
		Node<E> newNode = new Node<>(x);
		if (isEmpty()) {
			tail = newNode;
			tail.next=tail;
		} else {
			newNode.next=tail.next;
			tail.next=newNode;
			tail=newNode;
		}
		size++;
	}

	@Override
	public void dequeue() {
		if (isEmpty()) {
			System.out.println("ERROR");
		} else {
			if (tail.next==tail) {
				tail = null; 
			} else {
				tail.next=tail.next.next;
			}
		}
		size--;
	}

	@Override
	public E front() {
		if (isEmpty()) {
			return null;
		} else {
		return tail.next.item;
		}
	}

	@Override
	public boolean isEmpty() {
		return (tail==null);
	}

	@Override
	public void dequeueAll() {
		tail=null;
		size=0;
		
	}
	
	@Override
	public void printAll() {
		Node<E> currNode=tail;
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			System.out.print(currNode.item+" ");
		}
	}

}

3) 결과 확인하기

<코드>

public class Test {
	public static void main(String[] args) {
		
	
	LinkedQueue<Integer> lst = new LinkedQueue<>();
	
	lst.enqueue(100);
	
	lst.enqueue(200);
	
	lst.enqueue(300);
	
	lst.enqueue(400);

	lst.printAll();
	System.out.println();

	//LinkedQueue에 100,200,300,400을 순서대로 입력 후 현재 ArrayQueue 상태를 출력
	
	System.out.println(lst.front());
	
	//LinkedQueue의 가장 앞에 있는 값을 출력
	
	lst.dequeue();
	
	lst.printAll();
	
	System.out.println();
	
	//LinkedQueue에 100,200,300,400을 순서대로 입력 후 현재 ArrayQueue 상태를 출력
	
	System.out.println(lst.isEmpty());
	
	//LinkedQueue가 비었는지 출력
	
	
	}
}

<결과>

1.Queue란?

• 먼저 들어온 데이터가 먼저 나간다. 즉, 선입선출(FIFO) 방식이다.
• 맨 앞의 원소에만 접근이 가능하다. 

2. Queue 구현하기

구현할 내용은 아래와 같다.

• enqueue(E x) - 원소 x를 큐의 끝에 추가한다.
• dequeue() - 큐의 가장 앞에 있는 원소를 삭제한다.
• front() - 큐의 가장 앞에 있는 원소를  리턴한다.
• isEmpty() - 큐가 비어있으면 true, 그렇지 않으면 false를 리턴한다.
• dequeueAll() - 큐에 있는 모든 원소를 삭제한다.
• printAll() - 큐의 모든 원소를 순서대로 출력한다.

** 원래 큐에서는 맨 앞의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.

1) 인터페이스

public interface QueueInterface<E> {

	public void enqueue(E x);
	
	public void dequeue();
	
	public E front();
	
	public boolean isEmpty();
	
	public void dequeueAll();
	
	public void printAll();
	
}

2) 클래스

- 필드 영역

private E queue[];
private int front, tail, size;
private static final int DEFAULT_CAPACITY = 64;

• queue[] - ArrayQueue의 원소를 받을 배열 리스트이다.
• front, tail - ArrayQueue의 맨 첫 원소, 마지막 원소를 표시할 포인터이다.
• size -  ArrayQueue의 원소 개수를 저장할 변수이다.
• DEFAULT_CAPACITY - ArrayQueue 생성시 크기를 정해주지 않으면 해당 크기로 생성한다.

- 생성자 영역

	public ArrayQueue() {
		queue = (E[]) new Object[DEFAULT_CAPACITY];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}
	
	public ArrayQueue(int n) {
		queue = (E[]) new Object[n];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}

• 입력 값으로 정수를 받으면 해당 정수 크기의 큐를, 그렇지 않으면 DEFAULT_CAPACITY 크기의 큐를 생성한다.

- 메서드 영역

<is Full 메서드 구현>

public boolean isFull() {
		return (size==queue.length);
	}

• 인터페이스의 메서드를 오버라이딩 한 것은 아니다.
• 현재 size 변수(원소의 개수)와 생성시 배정한 queue의 크기가 같으면 true, 아니면 false를 리턴한다.

<enqueue 메서드 구현>

	@Override
	public void enqueue(E x) {
		if (isFull()) {
			System.out.println("ERROR");
		} else {
			tail = (tail+1)%queue.length;
			queue[tail]=x;
			size++;
		}
	}

• 만약 큐에 빈 공간이 없으면 에러를 출력한다.
• 그렇지 않다면 tail에 1을 더해주고 해당 위치에 입력받은 값을 입력한다.
• queue.length로 나눠주는 이유는 tail 포인터가 큐의 끝까지 도달했을 때 맨 앞 위치로 돌려놓기 위해서이다.
• size 변수를 1 증가시킨다.

<dequeue 메서드 구현>

	@Override
	public void dequeue() {
		if (isEmpty()) {
			System.out.println("ERROR");
		}
		queue[front]=null;
		front=(front+1)%queue.length;
		size--;
	}

• 만약 큐가 비어 있으면 에러를 출력한다.
• 그렇지 않다면 현재 front가 가리키는 위치의 값을 null로 비워준다.
• front에 1을 더해 포인터를 뒤로 이동시킨다.
• queue.length로 나눠주는 이유는 front 포인터가 큐의 끝까지 도달했을 때 맨 앞 위치로 돌려놓기 위해서이다.

<front 메서드 구현>

	@Override
	public E front() {
		if (isEmpty()) {
			return null;
		} else {
		return queue[front];
		}
	}

• 만약 큐가 비어 있으면 null값을 리턴한다.
• 그렇지 않다면 현재 front가 가리키는 위치의 값을 리턴한다.

<isEmpty 메서드 구현>

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

• 원소의 개수가 0이면 true, 아니면 false를 리턴한다.

<dequeueAll 메서드 구현>

	@Override
	public void dequeueAll() {
		queue = (E[]) new Object[queue.length];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}

• queue, front, tail, size값을 초기화한다.

<printAll 메서드 구현>

	@Override
	public void printAll() {
		for (int i=tail; i>=front; i--) {
			System.out.print(queue[i]+" ");
		}
	}

• tail부터 front까지 순회하며 큐 원소 값을 출력한다.

- 전체 코드

public class ArrayQueue<E> implements QueueInterface<E> {

	
	//필드 영역
	private E queue[];
	
	private int front, tail, size;
	
	private static final int DEFAULT_CAPACITY = 64;
	
	//생성자 영역
	public ArrayQueue() {
		queue = (E[]) new Object[DEFAULT_CAPACITY];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}
	
	public ArrayQueue(int n) {
		queue = (E[]) new Object[n];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}
	
	//메서드
	
	public boolean isFull() {
		return (size==queue.length);
		
	}

	@Override
	public void enqueue(E x) {
		if (isFull()) {
			System.out.println("ERROR");
		} else {
			tail = (tail+1)%queue.length;
			queue[tail]=x;
			size++;
		}
	}

	@Override
	public void dequeue() {
		if (isEmpty()) {
			System.out.println("ERROR");
		} else {
		queue[front]=null;
		front=(front+1)%queue.length;
		size--;
		}
	}

	@Override
	public E front() {
		if (isEmpty()) {
			return null;
		} else {
		return queue[front];
		}
	}

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

	@Override
	public void dequeueAll() {
		queue = (E[]) new Object[queue.length];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}

	@Override
	public void printAll() {
		for (int i=tail; i>=front; i--) {
			System.out.print(queue[i]+" ");
		}
	}
}

3) 결과 확인하기

- 코드

public class Test {
	public static void main(String[] args) {
		
	
	ArrayQueue<Integer> lst = new ArrayQueue<>();
	
	lst.enqueue(100);
	
	lst.enqueue(200);
	
	lst.enqueue(300);
	
	lst.enqueue(400);
	
	lst.printAll();
	System.out.println();
	
	//ArrayQueue에 100,200,300,400을 순서대로 입력 후 현재 ArrayQueue 상태를 출력
	
	System.out.println(lst.front());
	
	//ArrayQueue의 가장 앞에 있는 값을 출력
	
	lst.dequeue();
	
	lst.printAll();
	
	System.out.println();
	
	//ArrayQueue의 가장 앞에 있는 값을 삭제하고 출력
	
	System.out.println(lst.isEmpty());
	
	//ArrayQueue가 비었는지 출력
	
	
	}
}

- 결과