순차 리스트 ( 배열 / 행렬 / 레코드 / 스택 / 큐 / 데크 )

자료 구조의 종류

순차 리스트

 : 각 자료가 메모리 중에서 서로 이웃해 있는 구조

 : 선형 구조라고도 함

 : 메모리에 연속되어 저장

 : 배열 / 행렬 / 레코드 / 스택 / 큐 / 데크

 

배열

 : 원소들의 크기와 자료형 같음

 : 배열의 원소는 메모리 내에서 연속적으로 순서대로 저장

 : 각 배열의 원소는 인덱스로 구별

 

레코드

 : 서로 다른 데이터 형태와 크기로 구성되어 있는 데이터 구조 (이질적 구조)

 : ex) 어떤 사람에 관한 자료들인 이름, 주민등록번호, 주소 등과 같이 서로 관계있는 여러 필드를 하나로 묶어서 구성

 : 배열은 데이터 원소의 크기와 데이터 형태 동일하지만, 레코드는 데이터 원소의 크기와 데이터 형태 서로 다름

 

스택 (stack)

 : 쌓아 올린 더미를 의미

 : 선형 리스트 구조의 특별한 형태

 : 리스트 내의 데이터 삽입과 삭제가 Top이라고 하는 한 쪽 끝에서만 일어나는 데이터 구조

 : 데이터 구조에서의 스택이란, 기억 장치에 데이터를 일시적으로 쌓아 두었다가 필요할 때 꺼내서 사용할 수 있는 주기억장치(메모리)나 레지스터의 일부를 할당하여 사용하는 임시적인 기억을 의미

 : 가장 마지막에 삽입한 데이터를 제일 먼저 삭제

 : 후입선출 (LIFO : Last-In First Out) 리스트라고도 불림

 

Top

 : 스택에 대한 삽입과 삭제가 이루어지는 위치

 : 가장 최근에 입력된 항목의 위치를 가리키는 포인터

 : 출력 우선 순위가 가장 높은 원소를 가리키는 포인터

 : 초기에 TOP은 0부터 시작

 : 배열로 스택 구현 시, 배열 첨자가 0부터 시작하므로 Top을 -1로 초기화

 

Bottom

 : Top의 반대쪽

 : 노드의 입출력 불가

 

PUSH

: 삽입 연산

 : 스택에 새로운 노드 입력

 : Top = Top + 1

 

Pop

 : 삭제 연산

 : 스택에서 노드 삭제

 : Top = Top - 1

 

오버플로우 (Overflow)

 : 스택이 가득차 있을 때 (TOP == n) 새로운 노드 삽입 시, 스택에 더 이상 삽입을 할 수 없는 경우

 : Top > n이 되는 경우

 : 스택에 노드 삽입 전에 오버플로우가 발생하는지 확인해야 함 (isFull())

 

언더플로우(Underflow)

 : 스택이 비어있을 때 (TOP == 0) 노드의 삭제 시, 더 이상 삭제를 할 수 없는 경우

 : TOP < 0이 되는 경우

 : 스택에서 노드 삭제 전에 언더플로우가 발생하는지 확인해야 함 (isEmpty())

 

 스택의 이용

 : 서브 프로그램의 복귀 주소( return address) 보관

 : 산술식 표현 : a + b

 : Java 프로그램에서 메서드 호출 및 실행 시 스택 사용

 

스택 구현 방법

(1) 배열 사용

package dataStructure;

public class MyStack {
	private int stackSize;
	private int top;
	private char[] stackArr;
	
	// 생성자 : 스택 초기화
	// 배열 인덱스는 0부터 시작하므로 top -1로 초기화
	public MyStack (int stackSize) {
		top = -1;
		this.stackSize = stackSize;
		stackArr = new char[this.stackSize];
	}
	
	// 스택이 비었는지 확인하는 메서드
	public boolean isEmpty() {
		return top==-1; //top이 -1이면 true 아니면 false
	}
	
	// 스택이 가득 차있는지 확인한느 메서드
	public boolean isFull() {
		return top==stackSize-1; // 스택이 가득 차있으면 true 아니면 false
	}
	
	// 스택에 데이터 삽입하는 메서드
	// 삽입 전 오버플로우 발생하는지 확인 -> full이 아니면 top을 하나 증가한 위치에 값 삽입
	public void push(char item) {
		if (isFull()) System.out.println("Stack is Full. Overflow");
		else stackArr[++top] = item;
	}
	
	// 삭제 전 언더플로우 발생하는지 확인
	public char pop() {
		if (isEmpty()) {
			System.out.println("Stack is emptry. Underflow");
			return 'E'; //형식적으로 반환
		}
		else return stackArr[top--];
	}
	
	public char peek() {
		if(isEmpty()) {
			System.out.println("Stack Empty");
			return 'E';
		}
		else return stackArr[top];
	}
	
	// 스택 내용을 비우는 clear()
	public void clear() {
		top = -1;
	}
	
	// 스택의 전체 데이터를 출력하는 showStack()
	// 출력만 하고 반환값 없음
	// 출력 전 스택 비었는지 왁인
	// 스택에 있는 모든 요소의 값 출력
	public void showStack() {
		if(isEmpty()) System.out.println("Stack Empty");
		else {
			System.out.print("Stack items : ");
			for (int i=0; i<=top; i++) {
				System.out.print(i + ":" + stackArr[i] + " ");
			}
			System.out.println("\ntop : " + top);
		}
	}
}

(2) java.util.Stack 클래스 이용

import java.util.Stack;

Stack<String> stk = new Stack<String>();

 

큐 (queue)

 : 선형 리스트 구조의 특별한 형태

 : 기억장소의 한쪽 끝에서는 데이터의 입력이, 다른 한쪽에서는 데이터의 삭제가 이루어지는 구조

 : 먼저 삽입한 데이터가 먼저 삭제 -> 선입선출 (FIFO : First-In First-Out) 구조

 : 전위 포인터 (front) - 데이터가 삭제되는 끝을 가리키는 포인터

 : 후위 포인터 (rear) - 데이터가 삽입되는 끝을 가리키는 포인터

 

큐에서의 오버플로우 해결 방법

 : 후위 포인터 rear의 값이 n과 같을 때 새로운 데이터를 삽입하면 오버플로우 발생

 

(1) 이동 큐 (moving queue)

 : 앞 부분이 비어 있는 경우 큐의 데이터를 앞 부분으로 이동

 : 데이터 이동에 따른 시간적 부담 문제

 

(2) 원형 큐 (circular queue)

 : 선형 큐의 앞(front)과 뒤(rear)를 이어 놓은 형태의 큐

 : 새로운 항목을 삽입하기 위하여 rear를 시계방향으로 증가

 

큐의 응용

-      작업 도착 순서에 의한 스케줄링

-      대표적인 예 : 프린터

-      작업 순서

-      front=0 작업 A > 작업 B -> 작업  C -> 작업 D rear=4

 

큐 예제

(1) 앞이 비었는데도 오버플로우 발생 : 이동 없음

public class MyQueue {
	// 멤버 변수
	private int queueSize; 		// 큐의 용량
	private int front; 			// 전위 포인터. 첫 번째 요소 앞
	private int rear;			// 후위 포인터. 마지막 요소 값과 동일
	private int num;			//현재 데이터 수
	private char[] queue;       // 큐 본체 (변수 선언만. 아직 할당 못 받았음)
	
	// 생성자에서 초기화
	public MyQueue(int queueSize) {
		// 배열 사용하므로 초기값 -1로 설정
		front = rear = -1;				// 큐가 비어 있는 상태 
		num = 0; 						// 데이터 수
		this.queueSize = queueSize;		// 큐 크기 설정
		queue = new char[queueSize];	// 큐 생성
	}
	
	// 큐가 비어있는 상태 확인하는 isEmpty()
	// true/false
	public boolean isEmpty() {
		// front와 rear 포인터가 같으면 큐가 비어있는 상태
		// 데이터가 없으므로 포인터를 모두 -1로 초기화
		// 배열 사용하므로 첫 번째가 0, 첫 번째 이전이 -1
		if(front == rear) {
			front = rear = -1;
		}
		// front와 rear 포인터가 같은 경우 true, 아니면 false return
		return front == rear;
	}
	
	// 큐가 가득 차있는 상태 확인하는 isFull()
	public boolean isFull() {
		// rear 포인터가 큐의 마지막 인덱스와 동일하면 full 상태
		return rear == queueSize - 1; 
	}
	
	// 큐에 데이터 삽입하는 enqueue()
	// (1) Full인지 확인
	// (2) 데이터 삽입
	public void enqueue(char item) {
		if(isFull()) {
			System.out.println("Queue Full!");
		} else {
			queue[++rear] = item; // rear 다음 위치에 데이터 삽입
			num++;  			  // 데이터 수 증가
		}
	}
	
	
	// 큐에서 데이터 삭제하는 dequeue()
	// (1) Empty인지 확인
	// (2) 데이터 삭제 (삭제한 데이터 반환)
	public  char dequeue() {
		if(isEmpty()) {
			return 'E';
		} else {
			num--;    // 데이터 수 감소
			front++;  // front 증가 (front 다음 위치 값 삭제)
			return queue[front];
		}
	}	
	
	
	// 큐의 첫 번째 데이터 추출하는 peek()
	// 추출해서 반환
	public char peek() {
		if(isEmpty()) {
			System.out.println("peek 실패. Empty");
			return 'E';
		} else {
			// front 다음 데이터 추출해서 반환
			return queue[front + 1];
		}
	}
	
	// 큐 초기화하는 clear()
	public void clear() {
		front = rear = -1;
		System.out.println("clear!");
	}
	
	
	// 큐에 들어있는 모든 데이터를 출력하는 showQueue()
	// (1) 큐가 비었는지 확인
	// (2) 큐에 있는 모든 데이터 출력
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("Queue Empty");
		} else {
			System.out.print("Queue items : ");
			//front + 1 위치부터 rear까지 출력
			for(int i=front+1; i<=rear; i++) {
				System.out.print(i + ":" + queue[i] + " ");
			}
		}
	}
		
	// 데이터 개수를 반환하는 numOfData()
	public int numOfData() {
		return num;
	}
}

(2) 큐 이동해서 오버플로우 해결

public class MyQueueMove {
	// 멤버 변수
	private int queueSize; 		// 큐의 용량
	private int front; 			// 전위 포인터. 첫 번째 요소 앞
	private int rear;			// 후위 포인터. 마지막 요소 값과 동일
	private int num;			//현재 데이터 수
	private char[] queue;       // 큐 본체 (변수 선언만. 아직 할당 못 받았음)
	
	// 생성자에서 초기화
	public MyQueueMove(int queueSize) {
		// 배열 사용하므로 초기값 -1로 설정
		front = rear = -1;				// 큐가 비어 있는 상태 
		num = 0; 						// 데이터 수
		this.queueSize = queueSize;		// 큐 크기 설정
		queue = new char[queueSize];	// 큐 생성
	}
	
	// 큐가 비어있는 상태 확인하는 isEmpty()
	// true/false
	public boolean isEmpty() {
		// front와 rear 포인터가 같으면 큐가 비어있는 상태
		// 데이터가 없으므로 포인터를 모두 -1로 초기화
		// 배열 사용하므로 첫 번째가 0, 첫 번째 이전이 -1
		if(front == rear) {
			front = rear = -1;
		}
		// front와 rear 포인터가 같은 경우 true, 아니면 false return
		return front == rear;
	}
	
	// 큐가 가득 차있는 상태 확인하는 isFull()
	public boolean isFull() {
		// rear 포인터가 큐의 마지막 인덱스와 동일하고
		// 데이터 수가 queueSize와 동일하면 full 상태
		return (rear == queueSize -1 && num == queueSize);
	}
	
	// 큐에 데이터 삽입하는 enqueue()
	// (1) Full인지 확인
	// (2) 데이터 삽입
	public void enqueue(char item) {
		if(isFull()) {
			System.out.println("Queue Full!");
		} else if(num != 0 && rear == queueSize -1){
			// rear가 마지막 인덱스와 동일하지만
			// 데이터가 1개라도 들어 있는 경우 
			// queue 이동 : 현재 queue를 복사해서 
			// 시작 인덱스 0으로 덮어 씀
			//System.arraycopy(소스, 시작인덱스, 대상, 시작인덱스, 길이);
			System.arraycopy(queue, front+1, queue, 0, queue.length - 1);
			System.out.println("큐 이동 발생");
			rear--;
			front = -1;
			
			queue[++rear] = item; // rear 다음 위치에 데이터 삽입
			num++;		
		}else {
			queue[++rear] = item; // rear 다음 위치에 데이터 삽입
			num++;  			  // 데이터 수 증가
		}
	}
	
	
	// 큐에서 데이터 삭제하는 dequeue()
	// (1) Empty인지 확인
	// (2) 데이터 삭제 (삭제한 데이터 반환)
	public  char dequeue() {
		if(isEmpty()) {
			return 'E';
		} else {
			num--;    // 데이터 수 감소
			front++;  // front 증가 (front 다음 위치 값 삭제)
			return queue[front];
		}
	}	
	
	
	// 큐의 첫 번째 데이터 추출하는 peek()
	// 추출해서 반환
	public char peek() {
		if(isEmpty()) {
			System.out.println("peek 실패. Empty");
			return 'E';
		} else {
			// front 다음 데이터 추출해서 반환
			return queue[front + 1];
		}
	}
	
	// 큐 초기화하는 clear()
	public void clear() {
		front = rear = -1;
		System.out.println("clear!");
	}
	
	
	// 큐에 들어있는 모든 데이터를 출력하는 showQueue()
	// (1) 큐가 비었는지 확인
	// (2) 큐에 있는 모든 데이터 출력
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("Queue Empty");
		} else {
			System.out.print("Queue items : ");
			//front + 1 위치부터 rear까지 출력
			for(int i=front+1; i<=rear; i++) {
				System.out.print(i + ":" + queue[i] + " ");
			}
		}
	}
		
	// 데이터 개수를 반환하는 numOfData()
	public int numOfData() {
		return num;
	}
}

(3) java.util.Queue 인터페이스를 LinkedList로 구현 (ArrayList로 구현할 경우 추가/삭제 시 데이터 이동이 필요)

import java.util.LinkedList;
import java.util.Queue;

Queue<String> q = new LinkedList<String>();

 

데크 (deque : double ended queue)

 : 삽입과 삭제가 양끝에서 이루어지는 구조

 : 스택과 큐를 하나의 선형 리스크 구조에 복합시킨 형태

 : end1과 end2 포인터 사용

 : 양쪽 끝에서의 오버플로우의 가능성을 줄이기 위해 데크 내의 중심 근처에부터 저장 가능

 

데크 구현

java.util.Deque 인터페이스를 ArrayDeque로 구현

import java.util.ArrayDeque;
import java.util.Deque;

Deque<String> dq = new ArrayDeque<String>();