자료구조
LinkedList
LinkedList는 연결리스트라 부르는 자료구조이다.
연결리스트는 링크를 통해 리스트간 노드를 연결하는 리스트를 말한다.
public class ListNode {
Integer data;
ListNode next;
public ListNode() {
this.data = null;
this.next = null;
}
public ListNode(int data) {
this.data = data;
this.next = null;
}
public ListNode(int data, ListNode next) {
this.data = data;
this.next = next;
}
}public class LinkedList {
ListNode add(ListNode head, ListNode nodeToAdd, int position) {
ListNode node = head;
if (head == null) {
return nodeToAdd;
}
if (position == 0) {
nodeToAdd.next = head;
return nodeToAdd;
}
for (int i = 1; i <= position; i++) {
node = node.next;
}
nodeToAdd.next = node.next;
node.next = nodeToAdd;
return head;
}
ListNode remove(ListNode head, int positionToRemove) {
if (head == null) {
return null;
}
if (positionToRemove == 0) {
return head.next;
}
ListNode node = head;
for (int i = 1; i <= positionToRemove; i++) {
node = node.next;
}
node.next = node.next.next;
return head;
}
boolean contains(ListNode head, ListNode nodeToCheck) {
ListNode node = head;
while (node != null) {
if (head.data == nodeToCheck.data) {
return true;
}
node = node.next;
}
return false;
}
}Stack
-IntStack
public class IntStack {
private int max; //스택 용량
private int ptr; // 스택 포인터 : 스택에 쌓여있는 데이터 수를 나타내는 필드 즉, 배열 stk의 요솟수
private int[] stk; // 스택 본체 배열
//2-11 예외처리
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() {)
super("스택이 비어 있습니다.");
}
}
public class OverflowStackExpception extends RuntimeException {
public OverflowStackExpception() {
super("스택이 가득 찼습니다.");
}
}
//2-1) push : 스택에 데이터를 푸시하는 메서드
public void push(int data) {
if(IsFull())
throw new OverflowStackExpception();
stk[ptr++] = data;
}
//2-2) pop : 스탭의 꼭대기에서 데이터를 제거하고 그 값을 반환하는 메서드
public int pop() {
if(IsEmpty())
throw new EmptyIntStackException();
return stk[--ptr];
}
// 2-3) peek : 스택의 꼭데기에 있는 데이터를 몰래 엿보는 메서드
public int peek() {
if(IsEmpty())
throw new EmptyIntStackException();
return stk[ptr-1];
}
// 2-4) indexOf : 스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사하는 메서드
// 있을시 index 반환 없을시 -1 반환.
public int indexOf(int data) {
for(int i = 0; i < ptr; i++) {
if(stk[i] == data)
return i;
}
return -1;
}
// 2-5) clear : 스택에 쌓여있는 모든 데이터를 반환하는 메서드
public void clear() {
this.ptr = 0;
}
// 2-6) capacity : 스택의 용량을 반환하는 메서드
public int capacity() {
return max;
}
// 2-7) size : 현재 스택에 쌓여있는 데이터 수를 반환 하는 메서드
public int size(){
return ptr;
}
// 2-8) IsEmpty : 스택이 비어있는지 확인하는 메서드
public boolean IsEmpty() {
return ptr == 0;
}
// 2-9) IsFull : 스택이 가득 찼는지 검사하는 메서드
public boolean IsFull() {
return ptr == max;
}
// 2-10) dump : 스택 안에 모든 데이터를 표시하는 메서드
public void dump() {
System.out.println("스택 출력");
System.out.println("--------------");
for(int i = 0; i < ptr; i++) {
System.out.println(i+"번째 데이터: "+stk[i]);
}
System.out.println("---------------");
}
public IntStack(int capacity) {
ptr = 0;
max = capacity;
try {
stk = new int[max];
}
catch (OutOfMemoryError e) {
max = 0;
}
}
public static void main(String[] args) {
GStack stack = new GStack(10);
stack.dump();
for(int i = 1; i < 10; i++){
stack.push(i);
stack.dump();
}
System.out.println(stack.indexOf(2));
System.out.println(stack.indexOf(10));
for(int i=1; i < 10; i++) {
stack.pop();
stack.dump();
}
}
}-GStack
public class GStack<E> {
private int max; //스택 용량
private int ptr; // 스택 포인터 : 스택에 쌓여있는 데이터 수를 나타내는 필드 즉, 배열 stk의 요솟수
private E[] stk; // 스택 본체 배열
//2-1) push : 스택에 데이터를 푸시하는 메서드
public void push(E data) {
if(IsFull()) {
throw new OverflowStackException();
}
stk[ptr++] = data;
}
//2-2) pop : 스탭의 꼭대기에서 데이터를 제거하고 그 값을 반환하는 메서드
public E pop() {
if(IsEmpty())
throw new EmptyStackException();
return stk[--ptr];
}
// 2-3) peek : 스택의 꼭데기에 있는 데이터를 몰래 엿보는 메서드
public E peek() {
if(IsEmpty())
throw new EmptyStackException();
return stk[ptr-1];
}
// 2-4) indexOf : 스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사하는 메서드
// 있을시 index 반환 없을시 -1 반환.
public int indexOf(E data) {
for(int i = 0; i < ptr; i++) {
if(stk[i] == data)
return i;
}
return -1;
}
// 2-5) clear : 스택에 쌓여있는 모든 데이터를 반환하는 메서드
public void clear() {
this.ptr = 0;
}
// 2-6) capacity : 스택의 용량을 반환하는 메서드
public int capacity() {
return max;
}
// 2-7) size : 현재 스택에 쌓여있는 데이터 수를 반환 하는 메서드
public int size(){
return ptr;
}
// 2-8) IsEmpty : 스택이 비어있는지 확인하는 메서드
public boolean IsEmpty() {
return ptr == 0;
}
// 2-9) IsFull : 스택이 가득 찼는지 검사하는 메서드
public boolean IsFull() {
return ptr == max;
}
// 2-10) dump : 스택 안에 모든 데이터를 표시하는 메서드
public void dump() {
System.out.println("스택 출력");
System.out.println("--------------");
for(int i = 0; i < ptr; i++) {
System.out.println(i+"번째 데이터: "+stk[i]);
}
System.out.println("---------------");
}
public GStack(int capacity) {
ptr = 0;
max = capacity;
try {
stk = (E[]) new Object[max];
}
catch (OutOfMemoryError e) {
max = 0;
}
}
public void main(String[] args) {
GStack stack = new GStack<E>(10);
//O(N)
stack.dump();
for(int i = 1; i < 10; i++){
stack.push('a'+i);
stack.dump();
}
for(int i=1; i < 10; i++) {
stack.pop();
stack.dump();
}
}
}Stack(ListNode)
public class ListNodeStack {
private ListNode head;
public ListNodeStack() {
head = null;
}
public void push(int data) {
ListNode node = new ListNode(data);
ListNode now = head;
if (head == null) {
head = node;
} else {
while(now.next != null) {
now = now.next;
}
now.next = node;
}
}
public Integer pop() {
ListNode node = head;
if (node == null) {
return null;
} else if(node.next == null) {
head = null;
return node.data;
}
else {
while (node.next.next != null) {
node = node.next;
}
ListNode remove = node.next;
node.next = null;
return remove.data;
}
}Queue
-배열
public class IntQueue {
private int max; // 큐의 용량
private int front; // 첫 번째 요소 커서
private int rear; //마지막 요소 커서
private int num; // 현재 데이터 수
private int[] que; // 큐 본체
public class EmptyIntQueueException extends RuntimeException {
public EmptyIntQueueException() {
super("큐가 비었습니다.");
}
}
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {
super("큐가 가득찼습니다.");
}
}
public IntQueue(int capacity) {
num = front = rear = 0;
max = capacity;
try {
que = new int[max];
}
catch (OutOfMemoryError e) {
max = 0;
}
}
//4-1) peek
public int peek() {
if(IsEmpty())
throw new EmptyIntQueueException();
return que[rear-1];
}
//4-2) indexOf
//찾는 값이 있을시 인덱스 반환. 없을 시 -1 반환.
public int indexOf(int data) {
for(int i = front; i < rear; i++) {
if(data == que[i])
return i;
}
return -1;
}
//4-3) clear
public void clear() {
num = 0;
rear = 0;
front = 0;
}
//4-4) capacity
public int capacity() {
return max;
}
//4-5) size
public int size() {
return num;
}
//4-6) IsEmpty
public boolean IsEmpty() {
return rear == front;
}
//4-7) IsFull
public boolean IsFull() {
return rear == max;
}
//4-8) dump
public void dump() {
System.out.println("큐 출력");
System.out.println("--------------");
for(int i=front; i<rear; i++){
System.out.println(i-num+1+"번째 데이터 = "+que[i]);
}
System.out.println("---------------");
}
//4-9) enque
public void enque(int data) {
if(IsFull())
throw new OverflowIntQueueException();
que[rear++] = data;
num++;
}
//4-10) deque
public int deque() {
if(IsEmpty())
throw new EmptyIntQueueException();
num--;
return que[front++];
}
public static void main(String[] args) {
IntQueue queue = new IntQueue(10);
// queue.deque();
for(int i=0; i<10; i++){
queue.enque(i);
queue.dump();
}
for(int i=0; i<10; i++){
queue.deque();
queue.dump();
}
}
}-ListNode
public class ListNodeQueue {
ListNode head;
public ListNodeQueue() {
head = null;
}
public void push(int data) {
ListNode node = new ListNode(data);
ListNode now = head;
while(now.next != null) {
now = now.next;
}
now.next = node;
}
public int pop() {
int result = head.data;
head = head.next;
return result;
}
}