[자료구조] 선형 자료구조

1. 배열

행 우선(Row-major order): a[0][0], a[0][1], a[0][2], ...
열 우선(Column-major order): a[0][0], a[1][0], a[2][0], ...

1-1) 1차원 배열

원소의 주소 = 배열의 시작 주소 + 첨자
ex) int a[n]; 일 때 &a[i] == α + i*sizeof(int)

1-2) 2차원 배열

① 행 우선
	int a[u0][u1]; 일 때
	&a[i][j] == α + (i*u1 + j) * sizeof(int)
② 열 우선
	&a[i][j] == α + (i + j*u1) * sizeof(int)

1-3) 3차원 배열

① 행 우선
	int a[u0][u1][u2]; 일 때
	&a[i][j][k] == α + (i*u1*u2 + j*u2 + k) * sizeof(int)
② 열 우선
	&a[i][j][k] == α + (i*u1*u2 + j + k*u1) * sizeof(int)

2. 스택

삽입(push)과 삭제(pop)가 top에서만 일어나는 LIFO 구조

class Stack {
	final int STACK_SIZE = 100;
	int top = -1;
	int[] stack = new int[STACK_SIZE];
	
	void push(int item) {
		if(top >= STACK_SIZE - 1)
			System.out.println("stack full...");
		else
			stack[++top] = item;
	}
	
	int pop() {
		if(top < 0) {
			System.out.println("stack empty...");
			return -99;
		}
		return stack[top--];
	}
}

실행 예시

Stack stk = new Stack();
stk.push(3);			// 3(t)
stk.push(5);			// 3 5(t)
stk.push(7);			// 3 5 7(t)
int item = stk.pop();	// 3 5(t) 7(pop)
System.out.println(item);	// 7 출력

3. 큐

rear에서 삽입이 일어나고, front에서 삭제가 일어나는 FIFO 구조

class Queue {
	final int QUEUE_SIZE = 100;
	int rear = -1;
	int front = -1;
	int[] queue = new int[QUEUE_SIZE];
	
	void add(int item) {
		if(rear == QUEUE_SIZE-1) 
			System.out.println("Queue is full...");
		else
			queue[++rear] = item;
	}
	
	int delete() {
		if(front == rear) {
			System.out.println("Queue is empty...");
			return -999;
		}
		return queue[++front];
	}
}

실행 예시

Queue q = new Queue();
q.add(3);				// 3(r)
q.add(5);				// 3 5(r)
int item = q.delete(); // 3(f) 5(r)
System.out.println(item);	// 3 출력