Algorithm - Stack & Queue
2022. 9. 13. 14:50ㆍAlgorithm
Stack
후입선출 Last In Frist Out 순서를 가진 자료구조
자세한 내용은 https://dusen0528.tistory.com/43 이 게시글을 참고하자
public class Stack1{
private int[] stk; //스택용 배열 정수
private int capacity; //스택 용량
private int ptr; //스택 포인터
public class EmptyIntStackException extends RuntimeException{
//실행 시 예외 : 스택이 비어있음
public EmptyIntStackException(){
}
}
public class OverflowIntStackException extends RuntimeException{
public OverflowIntStackException(){
}
}
public Stack1(int maxlen){ //스택용 배열 본체를 생성하는 준비작업 생성자
ptr = 0; //생성시 스택은 비어있으므로 스택 포인터 값은 0
capacity = maxlen; //매개변수로 받은 maxlen(최대 길이)를 스택 용량으로 capacity에 대입
try{
stk = new int[capacity];
} catch(OutOfMemoryError e){ //배열 본체 생성에 실패한 경우 capacity 값을 0으로 설정
//이렇게 하면 다른 메소드가 존재하지 않는 배열 stk에 잘못 접근하는 것을 막을 수 있음.
capacity = 0;
}
}
public int push(int x) throws OverflowIntStackException{ //데이터 삽입
if(ptr>=capacity) throw new OverflowIntStackException();
return stk[ptr++] = x;
}
public int pop() throws EmptyIntStackException{ //맨 위의 데이터 제거 후 반환
if(ptr<=0) throw new EmptyIntStackException();
return stk[--ptr];
}
public int peek() throws EmptyIntStackException{ //맨 위의 데이터 확인
if(ptr<=0) throw new EmptyIntStackException();
return stk[ptr-1];
}
public void clear(){ //스택 비움
ptr = 0;
}
public int indexOf(int x){
//검색 메소드
//꼭대기에서 검색을 시작하는 이유는 가장 먼저 pop될 데이터를 찾기 위함
for(int i=ptr-1; i>=0; i--){
if(stk[i]==x)
return i; //검색성공
}
return -1; //검색실패
}
public int getCapacity(){ //스택 용량 반환
return capacity;
}
public int size(){ //스택에 쌓여있는 데이터 개수 반환
return ptr;
}
public boolean isEmpty(){ //스택 비어 있는지
return ptr<=0;
}
public boolean isFull(){ //스택 가득 차있는지
return ptr<=0;
}
public void dump(){ //스택 안의 모든 데이터를 바닥->꼭대기 순으로 출력
if(ptr<=0){
System.out.println("스택이 비어있습니다");
}
else{
for(int i=0; i<ptr; i++){
System.out.print(stk[i]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
}
}스택을 Java로 구현한 코드이다. 이를 활용하면
import java.util.Scanner;
public class Stack1{
private int[] stk; //스택용 배열 정수
private int capacity; //스택 용량
private int ptr; //스택 포인터
public class EmptyIntStackException extends RuntimeException{
//실행 시 예외 : 스택이 비어있음
public EmptyIntStackException(){
}
}
public class OverflowIntStackException extends RuntimeException{
public OverflowIntStackException(){
}
}
public Stack1(int maxlen){ //스택용 배열 본체를 생성하는 준비작업 생성자
ptr = 0; //생성시 스택은 비어있으므로 스택 포인터 값은 0
capacity = maxlen; //매개변수로 받은 maxlen(최대 길이)를 스택 용량으로 capacity에 대입
try{
stk = new int[capacity];
} catch(OutOfMemoryError e){ //배열 본체 생성에 실패한 경우 capacity 값을 0으로 설정
//이렇게 하면 다른 메소드가 존재하지 않는 배열 stk에 잘못 접근하는 것을 막을 수 있음.
capacity = 0;
}
}
public int push(int x) throws OverflowIntStackException{ //데이터 삽입
if(ptr>=capacity) throw new OverflowIntStackException();
return stk[ptr++] = x;
}
public int pop() throws EmptyIntStackException{ //맨 위의 데이터 제거 후 반환
if(ptr<=0) throw new EmptyIntStackException();
return stk[--ptr];
}
public int peek() throws EmptyIntStackException{ //맨 위의 데이터 확인
if(ptr<=0) throw new EmptyIntStackException();
return stk[ptr-1];
}
public void clear(){ //스택 비움
ptr = 0;
}
public int indexOf(int x){
//검색 메소드
//꼭대기에서 검색을 시작하는 이유는 가장 먼저 pop될 데이터를 찾기 위함
for(int i=ptr-1; i>=0; i--){
if(stk[i]==x)
return i; //검색성공
}
return -1; //검색실패
}
public int getCapacity(){ //스택 용량 반환
return capacity;
}
public int size(){ //스택에 쌓여있는 데이터 개수 반환
return ptr;
}
public boolean isEmpty(){ //스택 비어 있는지
return ptr<=0;
}
public boolean isFull(){ //스택 가득 차있는지
return ptr<=0;
}
public void dump(){ //스택 안의 모든 데이터를 바닥->꼭대기 순으로 출력
if(ptr<=0){
System.out.println("스택이 비어있습니다");
}
else{
for(int i=0; i<ptr; i++){
System.out.print(stk[i]+" ");
}
System.out.println();
}
}
class IntStackTest{
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
Stack1 s = new Stack1(64);
while(true){
System.out.println();
System.out.printf("현재 데이터 개수 : %d / %d\n", s.size(), s.getCapacity());
System.out.print("(1)푸시 (2)팝 (3)피크 (4)덤프 (0)종료");
int menu = stdIn.nextInt();
if(menu==0) {
System.out.println("종료합니다..");
break;
}
int x;
switch(menu){
case 1: //푸쉬
System.out.print("데이터: ");
x = stdIn.nextInt();
try{
s.push(x);
} catch(IntStack.OverflowIntStackException e){
System.out.println("스택이 가득 찼습니다");
}
break;
case 2:
try{
x = s.pop();
System.out.println("팝한 데이터는 " + x + "입니다");
} catch(IntStack.EmptyIntStackException e){
System.out.println("스택이 비어있습니다");
}
break;
case 3:
try{
x = s.peek();
System.out.println("피크한 데이터는 " + x + "입니다");
} catch(IntStack.EmptyIntStackException e){
System.out.println("스택이 비어있습니다.");
}
break;
case 4:
s.dump();
break;
}
}
stdIn.close();
}
}
}
Queue
선입선출 First in First Out 순서를 가진 자료구조
자세한 내용은 https://dusen0528.tistory.com/61 이 게시글을 참고하자
public class IntQueue{
private int[] que; //큐용 배열
private int capacity; //큐 용량
private int num; //현재 데이터 개수
private int front; //맨 앞의 요소 커서
private int rear; //맨 뒤의 요소 커서
public class EmptyIntQueueException extends RuntimeException{
//실행시 예외 : 큐가 비어있음
public EmptyIntQueueException(){
}
}
public class OverflowIntQueueException extends RuntimeException{
//실행시 예외 : 큐가 가득 참
public OverflowIntQueueException(){
}
}
public IntQueue(int maxlen){
num = front = rear = 0;
capacity = maxlen;
try{
que = new int[capacity];
} catch(OutOfMemoryError e){
capacity = 0;
}
}
public int enque(int x) throws OverflowIntQueueException{
if(num>=capacity)
throw new OverflowIntQueueException();
que[rear++] = x; //선입선출 구조이기에 큐의 가장 뒷자리에 삽입
num++; //요소 개수 +
if(rear==capacity) rear = 0; //만약 rear와 큐의 총 용량이 같아질 경우 rear를 가장 처음 0으로 초기화
return x;
}
public int deque() throws EmptyIntQueueException{
if(num<=0) throw new EmptyIntQueueException();
int x = que[front++]; //선입선출 구조이기에 큐의 가장 앞자리에 요소를 제거
num--; //요소 개수 -
if(front == capacity) front=0; //만약 front와 큐의 총 용량이 같아질 경우 배열의 맨 앞인 0번 인덱스로 변경
return x;
}
public int peek() throws EmptyIntQueueException{ //큐에서 데이터를 피크
if(num<=0) throw new EmptyIntQueueException();
return que[front];
}
public void clear(){
num = front = rear = 0;
}
public int indexOf(int x){
for(int i=0; i<num; i++){
int idx = (i+front) % capacity;
if(que[idx]==x) return idx;
}
return -1;
}
public int getCapacity(){ //큐의 총 용량을 반환
return capacity;
}
public int size(){ //큐에 쌓여있는 데이터 개수를 반환
return num;
}
public boolean isEmpty(){ //큐가 비어있는지
return num<=0;
}
public boolean isFull(){ //큐가 가득 차있는지
return num>=capacity;
}
public void dump(){ //큐 안의 모든 데이터를 front->rear 순으로 출력
if(num<=0) System.out.println("큐가 비어있습니다");
else{
for(int i=0;i<num;i++){
System.out.print(que[(i+front)%capacity]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
}
}큐를 Java로 구현한 코드이다. 이를 활용하면
import java.util.Scanner;
public class IntQueue{
private int[] que; //큐용 배열
private int capacity; //큐 용량
private int num; //현재 데이터 개수
private int front; //맨 앞의 요소 커서
private int rear; //맨 뒤의 요소 커서
public class EmptyIntQueueException extends RuntimeException{
//실행시 예외 : 큐가 비어있음
public EmptyIntQueueException(){
}
}
public class OverflowIntQueueException extends RuntimeException{
//실행시 예외 : 큐가 가득 참
public OverflowIntQueueException(){
}
}
public IntQueue(int maxlen){
num = front = rear = 0;
capacity = maxlen;
try{
que = new int[capacity];
} catch(OutOfMemoryError e){
capacity = 0;
}
}
public int enque(int x) throws OverflowIntQueueException{
if(num>=capacity)
throw new OverflowIntQueueException();
que[rear++] = x; //선입선출 구조이기에 큐의 가장 뒷자리에 삽입
num++; //요소 개수 +
if(rear==capacity) rear = 0; //만약 rear와 큐의 총 용량이 같아질 경우 rear를 가장 처음 0으로 초기화
return x;
}
public int deque() throws EmptyIntQueueException{
if(num<=0) throw new EmptyIntQueueException();
int x = que[front++]; //선입선출 구조이기에 큐의 가장 앞자리에 요소를 제거
num--; //요소 개수 -
if(front == capacity) front=0; //만약 front와 큐의 총 용량이 같아질 경우 배열의 맨 앞인 0번 인덱스로 변경
return x;
}
public int peek() throws EmptyIntQueueException{ //큐에서 데이터를 피크
if(num<=0) throw new EmptyIntQueueException();
return que[front];
}
public void clear(){
num = front = rear = 0;
}
public int indexOf(int x){
for(int i=0; i<num; i++){
int idx = (i+front) % capacity;
if(que[idx]==x) return idx;
}
return -1;
}
public int getCapacity(){ //큐의 총 용량을 반환
return capacity;
}
public int size(){ //큐에 쌓여있는 데이터 개수를 반환
return num;
}
public boolean isEmpty(){ //큐가 비어있는지
return num<=0;
}
public boolean isFull(){ //큐가 가득 차있는지
return num>=capacity;
}
public void dump(){ //큐 안의 모든 데이터를 front->rear 순으로 출력
if(num<=0) System.out.println("큐가 비어있습니다");
else{
for(int i=0;i<num;i++){
System.out.print(que[(i+front)%capacity]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
IntQueue s = new IntQueue(64);
while(true){
System.out.println();
System.out.printf("현재 데이터 개수: %d / %d\n", s.size(), s.getCapacity());
System.out.print("(1)인큐 (2)디큐 (3)피크 (4)덤프 (0)종료: ");
int menu = stdIn.nextInt();
if(menu==0) break;
int x;
switch(menu){
case 1:
System.out.print("데이터: ");
x = stdIn.nextInt();
try{
s.enque(x);
}catch(IntQueue.OverflowIntQueueException e){
System.out.println("큐가 가득 찼습니다");
}
break;
case 2:
try{
x = s.deque();
System.out.println("디큐한 데이터는 "+x+"입니다");
}catch(IntQueue.EmptyIntQueueException e){
System.out.println("큐가 비어있습니다");
}
break;
case 3:
try{
x = s.peek();
System.out.println("피크한 데이터는 "+ x + "입니다");
}catch(IntQueue.EmptyIntQueueException e){
System.out.println("큐가 비어있습니다.");
}
break;
case 4:
s.dump();
break;
}
}
stdIn.close();
}
}
* 큐와 스택에서의 peek 함수 특징은 다음 디큐할 때 꺼낼 데이터를 들여다보는 메소드이다.. 그렇기에 데이터를 꺼내지 않으므로 front, rear, ptr, num 등의 값은 변화하지 않는다는 점을 명심하자
'Algorithm' 카테고리의 다른 글
| 시간복잡도에 관한 구체적이고 쉬운 이야기 (1) | 2022.09.30 |
|---|---|
| Algorithm - 정렬 알고리즘 (0) | 2022.09.16 |
| Algorithm - 8퀸 문제 (0) | 2022.09.14 |
| Algorithm - 재귀(recursive) (0) | 2022.09.13 |
| Algorithm - 검색 알고리즘 (0) | 2022.09.08 |