스택(Stack) , 큐(Queue)

1. 스택(Stack)

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)입니다.

스택에 데이터를 넣는 작업을 푸시(push)라 하고 데이터를 꺼내는 작업을 팝(pop)이라 합니다.

스택 구조에 푸시와 팝을 하는 위치를 꼭대기(top)이라 하고 스택의 가장 아랫부분을 바닥(bottom)이라고 합니다.

스택의 푸시와 팝

Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용합니다.

 

메서드 호출과 스택

 

스택 구현(Java)

import java.util.Scanner;

public class StackMain {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("스택 크기 입력");
		Stack st = new Stack(sc.nextInt());

		all: while (true) {
			System.out.println("STACK \n1)push 2)pop 3)peek 4)print 5)exit (선택)");
			int num = sc.nextInt();
			switch (num) {
			case 1:
				System.out.println("푸쉬할 값 입력");
				st.push(sc.nextInt());
				break;
			case 2:
				st.pop();
				break;
			case 3:
				st.peek();
				break;
			case 4:
				st.printStack();
				break;
			case 5:
				System.out.println("종료되었습니다.");
				break all;
			}
		}
		sc.close();

	}
}

public class Stack {
	int size;
	int stack[];
	int top;

	public Stack(int size) {
		top = -1;
		stack = new int[size];
		this.size = size;
	}

	public void peek() {
		if (top == -1) {
			System.out.println("stack 비어있음.");
		} else {
			System.out.println("Peek! " + stack[top]);
		}
	}

	public void push(int value) {
		if (top == size) {
			System.out.println("스택 꽉참 실패");
		} else {
			stack[++top] = value;
			System.out.println(stack[top] + "push!");
		}
	}

	public int pop() {
		if (top == -1) {
			System.out.println("pop 실패 비어있음");
			return 0;
		} else {
			System.out.println(stack[top] + "pop");
			return stack[top--];
		}
	}

	public void printStack() {
		System.out.println("Stack list");
		for (int i = top; i >= 0; i--) {
			System.out.println(stack[i]);
		}
		System.out.println("end list");
	}

}

 

2. 큐(Queue)

큐는 스택과 마찬가지로 데이터를 임시적으로 쌓아 놓는 자료구조 입니다.

하지만 가장 먼저 넣은 데이터를 먼저 꺼내는 선입선출(FIFO; First In First Out)인 점이 스택과의 차이점 입니다.

생활에서 볼 수 있는 큐의 예는 은행 창구의 대기열등으로 볼 수 있습니다.

 

큐에서 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 합니다.

또 데이터를 꺼내는 쪽을 프론트(Front)라 하고, 데이터를 넣는 쪽을 (rear)라고 합니다.

 

큐 디큐와 인큐 과정

큐 구현(Java)

package Exam;
// int형 큐

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() { }
	}

	// 실행 시 예외：큐가 가득 참
	public class OverflowIntQueueException extends RuntimeException {
		public OverflowIntQueueException() { }
	}

	// 생성자
	public IntQueue(int capacity) {
		num = front = rear = 0;
		max = capacity;
		try {
			que = new int[max];				// 큐 본체용 배열을  생성
		} catch (OutOfMemoryError e) {		// 생성할 수 없음
			max = 0;
		}
	}

	// 큐에 데이터를 인큐
	public int enque(int x) throws OverflowIntQueueException {
		if (num >= max)
			throw new OverflowIntQueueException();			// 큐가 가득 참
		que[rear++] = x;
		num++;
		if (rear == max)
			rear = 0;
		return x;
	}

	// 큐에서 데이터를 디큐
	public int deque() throws EmptyIntQueueException {
		if (num <= 0)
			throw new EmptyIntQueueException();				// 큐가 비어 있음
		int x = que[front++];
		num--;
		if (front == max)
			front = 0;
		return x;
	}

	// 큐에서 데이터를 피크 (프런트 데이터를 들여다봄)
	public int peek() throws EmptyIntQueueException {
		if (num <= 0)
			throw new EmptyIntQueueException();				// 큐가 비어 있음
		return que[front];
	}

	// 큐에서 x를 검색하여 인덱스(찾지 못하면 –1)를 반환
	public int indexOf(int x) {
		for (int i = 0; i < num; i++) {
			int idx = (i + front) % max;
			if (que[idx] == x)								// 검색 성공
				return idx;
		}
		return -1;											// 검색 실패
	}

	// 큐를 비움
	public void clear() {
		num = front = rear = 0;
	}

	// 큐의 용량을 반환
	public int capacity() {
		return max;
	}

	// 큐에 쌓여 있는 데이터 수를 반환
	public int size() {
		return num;
	}

	// 큐가 비어 있나요?
	public boolean isEmpty() {
		return num <= 0;
	}

	// 큐가 가득 찼나요?
	public boolean isFull() {
		return num >= max;
	}

	// 큐 안의 모든 데이터를 프런트 → 리어 순으로 출력
	public void dump() {
		if (num <= 0)
			System.out.println("큐가 비어 있습니다.");
		else {
			for (int i = 0; i < num; i++)
				System.out.print(que[(i + front) % max] + " ");
			System.out.println();
		}
	}
}

package Exam;
import java.util.Scanner;
// int형 큐의 사용 예

class IntQueueTester {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		IntQueue s = new IntQueue(64);	// 최대 64개를 인큐할 수 있는 큐

		while (true) {
			System.out.println("현재 데이터 수：" + s.size() + " / "
															  + s.capacity());
			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;
			}
		}
	}
}

 

 

참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바편 (도서)