스택과 큐

스택

데이터를 일시적으로 저장하기 위해 사용하는 자료구조

입력과 출력 순서는 후입선출

• push : 데이터를 넣음
• pop : 데이터를 꺼냄
• top : 푸시와 팝을 하는 위치
• bottom : 스택의 가장 아랫부분

import java.io.IOException;


public class Main {
	private static int max; //스택 용량
	private static int ptr; //스택 포인터
	private static int[] stk; //스택 본체
	public static void main(String[] args) throws IOException{
		
	}
	static int push(int x) {
		return stk[ptr++] = x;
	}
	static int pop() {
		if (ptr <= 0)
			return -1;
		return stk[--ptr];
	}
	static int peek() {
		if (ptr <= 0)
			return -1;
		return stk[ptr - 1];
	}
	static int size() {
		return ptr;
	}
	static boolean isEmpty() {
		return ptr <= 0;
	}
}

push : 전달받은 데이터 x를 배열 요소 stk[ptr]에 저장하고, 스택 포인터를 증가시킨다.

pop : 스택 포인터 ptr의 값을 감소시키고 그때 stk[ptr]에 저장되어 있는 값을 반환시킨다.

peek : 스택이 비어 있지 않으면 꼭대기의 요소 stk[ptr - 1]을 반환한다. 데이터의 입력과 출입이 없으므로 스택 포인터는 변화하지 않는다.

size : 현재 스택에 쌓여 있는 데이터 수

isEmpty : 스택이 비어 있으면 true , 그렇지 않으면 false

 

스택 사용법

Stack<T> stackname = new Stack<>();

---

큐

데이터를 일시적으로 쌓아 놓은 자료구조

가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출

• enque : 큐에 데이터를 넣는 작업
• deque : 큐에서 데이터를 꺼내는 작업
• front : 데이터를 꺼내는 쪽
• rear : 데이터를 넣는 쪽

링 버퍼로 큐 만들기

배열의 처음이 끝과 연결되어있는 자료구조

오래된 데이터를 버리는 용도

import java.io.IOException;


public class Main {
	private static int max;
	private static int front;
	private static int rear;
	private static int num;
	private static int[] que;
	public static void main(String[] args) throws IOException{
		
	}
	static int enque(int x) {
		que[rear++] = x;
		num++;
		if(rear == max)
			rear = 0;
		return x;
	}
	static int deque() {
		if(num <= 0)
			return -1;
		int x = que[front++];
		num--;
		if(front == max)
			front = 0;
		return x;
	}
	static int peek() {
		if (num <= 0)
			return -1;
		return que[front];
	}
	static int indexOf(int x) {
		for (int i=0; i<num; i++) {
			int idx = (i + front)  % max;
			if(que[idx] == x)
				return idx;
		}
		return -1;
	}
	static int size() {
		return max;
	}
	static boolean isEmpty() {
		return num <= 0;
	}
	static 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();
		}
	}
}

enque : rear 값이 max와 같아지면 rear를 배열의 처음인 0으로 변경

deque : front값이 max와 같아지면 front값을 배열의 처음인 0으로 변경

 

객체형 데이터를 쌓아 놓을 수 있는 제너릭 큐 클래스

class Gqueue<E> {
	private int max;
	private int front;
	private int rear;
	private int num;
	private E[] que;
	
	public Gqueue(int capacity) { //생성자
		num = front = rear = 0;
		max = capacity;
		try {
			que = (E[]) new Object[max]; //큐 본체용 배열 생성
		} catch (OutOfMemoryError e) { //생성할 수 없습니다
			max = 0;
		}
	}
	public E enque(E x) {
		que[rear++] = x;
		num++;
		if(rear == max)
			rear = 0;
		return x;
	}
	public E deque() {
		E x = que[front++];
		num--;
		return x;
	}
}

큐 사용법

Queue<T> queuename = new LinkedList<>();

---

덱

 

import java.io.IOException;



public class Main {
	private static int max;
	private static int front;
	private static int rear;
	private static int num;
	private static int[] deque;
	public static void main(String[] args) throws IOException{
	
	}
	static int enqueFront(int x) { //머리쪽에서 인큐
		num++;
		if (--front < 0)
			front = max - 1;
		deque[front] = x;
		return x;
	}
	static int enqueRear(int x) { //꼬리쪽에서 인큐
		deque[rear++] = x;
		num++;
		if(rear == max)
			rear = 0;
		return x;
	}
	static int dequeFront() {
		int x = deque[front++];
		num--;
		if(front == max)
			front = 0;
		return 0;
	}
	static int dequeRear() {
		num--;
		if(--rear < 0)
			rear = max - 1;
		return deque[rear];
	}
}

덱 사용법

Deque<T> dequename = new ArrayDeque<>();