[코딩인터뷰완전분석] 스택과 큐

스택과 큐

스택

• 데이터를 쌓아 올리는 자료구조
• LIFO(Last In First Out)
• 맨 마지막에서 원소를 꺼내거나 추가하는 연산을 상수 시간에 할 수 있다.
• i번째 원소에 상수 시간에 접근할 수 없다.

큐

• FIFO(First In First Out)
• 선착순과 같은 느낌
• 맨 처음 원소를 꺼내거나 맨 마지막에 원소를 추가한다.

---

노드

package stackNqueue;

public class myNode {
	int value;
	int min;
	myNode next;
	String type;

	public myNode(int v) {
		this.value = v;
		this.type = null;
		this.next = null;
	}

	public myNode(int v, int m) {
		this.value = v;
		this.min = m;
		this.type = null;
		this.next = null;
	}

	public myNode(int v, String t) {
		this.value = v;
		this.type = t;
		this.next = null;
	}

	public String toString() {
		if (this.type == null) {
			return String.valueOf(value);
		}
		return "id : " + String.valueOf(value) + " type : " + type;
	}
}

---

스택

package stackNqueue;

public class myStack {
	private myNode top;
	private myNode next;
	private int size;


	public myStack() {
		this.size = 0;
		this.top = null;
	}

	public void push(int v) {
		if (this.size == 0) {
			this.top = new myNode(v);
			this.top.next = null;
		} else {
			if (v < this.min) {
				this.min = v;
			}
			myNode a = new myNode(v);
			a.next = this.top;
			this.top = a;
		}
		this.size++;
	}

	public int pop() {
		if (this.isEmpty()) {
			return -99999999;
		}
		int answer = top.value;
		this.top = top.next;
		this.size--;
		return answer;
	}

	public int peek() {
		if (this.isEmpty()) {
			return -99999999;
		}
		return this.top.value;
	}

	public boolean isEmpty() {
		if (this.size == 0) {
			return true;
		} else {
			return false;
		}
	}

	public int size() {
		return this.size;
	}

}

---

큐

package stackNqueue;

public class myQueue {

	private myNode first;
	private myNode last;

	private int size;

	public myQueue() {
		this.size = 0;
		this.first = null;
		this.last = null;
	}

	public void add(int v) {
		if (this.isEmpty()) {
			this.first = new myNode(v);
			this.last = this.first;
		} else {
			myNode a = new myNode(v);
			this.last.next = a;
			this.last = a;
		}
		this.size++;
	}

	public void add(int v, String t) {
		if (this.isEmpty()) {
			this.first = new myNode(v, t);
			this.last = this.first;
		} else {
			myNode a = new myNode(v, t);
			this.last.next = a;
			this.last = a;
		}
		this.size++;
	}

	public myNode remove() {
		if (this.isEmpty()) {
			return null;
		}
		myNode ans = first;
		this.first = this.first.next;
		this.size--;
		return ans;
	}

	public myNode peek() {
		if (this.isEmpty()) {
			return null;
		}
		myNode ans = first;
		return ans;
	}

	public boolean isEmpty() {
		if (this.size == 0) {
			return true;
		} else {
			return false;
		}
	}

	public int size() {
		return this.size;
	}

}

---

<한 개로 세 개 >

배열 한 개로 세 개의 스택을 만들어라.

내가 짠 코드(고정 길이)

class Array2Stack {
	int size;
	int[] stack, index;

	public Array2Stack(int n) {
		this.stack = new int[n];
		init();
		this.index = new int[3];
		for (int i = 0; i < 3; i++) {
			this.index[i] = i * n / 3;
		}

		this.size = n;
	}

	public void init() {
		for (int i = 0; i < this.size; i++) {
			stack[i] = Integer.MIN_VALUE;
		}
	}

	public void push(int idx, int v) throws Exception {
		if (this.isFull(idx)) {
			throw new Exception();
		}
		this.stack[this.index[idx]] = v;
		this.index[idx]++;
	}

	public int pop(int idx) throws Exception {
		if (this.isEmpty(idx)) {
			throw new Exception();
		}
		int ans = this.stack[index[idx] - 1];
		this.stack[index[idx] - 1] = Integer.MIN_VALUE;
		this.index[idx]--;
		return ans;
	}

	public int peek(int idx) throws Exception {
		if (this.isEmpty(idx)) {
			throw new Exception();
		}
		return this.stack[this.index[idx] - 1];
	}

	public boolean isFull(int idx) {
		if (index[idx] == (idx + 1) * this.size / 3) {
			return true;
		}
		return false;
	}

	public boolean isEmpty(int idx) {
		if (this.index[idx] == idx * this.size / 3) {
			return true;
		}
		return false;
	}

}

---

해답

1. 고정 크기 할당
   • 하나의 배열을 3개로 나눠서 각각 스택으로 동작하게 만든다.
   • 다른 스택은 비어있는데 한 스택에만 값이 몰려있을 수 있다. -> 메모리 낭비
2. 유연한 공간 분할
   • 각 스택에 할당되는 공간 크기가 유연하게 변하는 방법

---

<스택에서 min 값을 구하여라.>

어려워서 해답을 봤다.

코드

myNode 클래스에 생성자 추가

	public myNode(int v, int m) {
		this.value = v;
		this.min = m;
		this.type = null;
		this.next = null;
	}

myStack 클래스 add 메소드 코드 변경

	public void push(int v) {
		if (this.size == 0) {
			this.top = new myNode(v, v);
			this.min = v;
			this.top.next = null;
		} else {
			if (v < this.min) {
				this.min = v;
			}
			myNode a = new myNode(v, this.min);
			a.next = this.top;
			this.top = a;
		}
		this.size++;
	}

노드가 추가될 때의 min 값을 노드에 저장해둔다.

---

해답

1. 노드에 min 값을 저장해둔다. -> 스택의 크기가 커질수록 각 노드마다 min값을 기록하느라 공간이 낭비된다.
2. min 값을 저장하는 스택을 하나 더 사용한다. (위의 방법보다 조금 더 낫다.)

---

<접시 무더기>

스택이 하나인 경우와 동일하게 동작하는 여러 개의 스택을 만들어라.

내가 짠 코드

package stackNqueue;

import java.util.ArrayList;

public class SetOfStacks {
	ArrayList<myStack> sos;
	int size;
	int count;
	int limit;

	public SetOfStacks(int k) {
		this.limit = k;
		this.sos = null;
		this.size = 0;
		this.count = 0;
	}

	public void push(int v) {
		if (this.size == 0) {
			this.sos = new ArrayList<>();
			this.sos.add(new myStack());
			this.sos.get(0).push(v);
			this.size++;
		} else {
			if (this.sos.get(this.size - 1).size() == this.limit) {
				this.sos.add(new myStack());
				this.sos.get(this.size).push(v);
				this.size++;
			} else {
				this.sos.get(this.size - 1).push(v);
			}
		}
		this.count++;

	}

	public int pop() {
		if (this.isEmpty()) {
			return Integer.MIN_VALUE;
		}
		if (this.sos.get(this.size - 1).size() == 1) {
			int temp = this.sos.get(this.size - 1).pop();
			this.sos.remove(this.size - 1);
			this.size--;
			this.count--;
			return temp;
		}
		this.count--;
		return this.sos.get(this.size - 1).pop();
	}

	public int peek() {
		if (this.isEmpty()) {
			return Integer.MIN_VALUE;
		}
		return this.sos.get(this.size - 1).peek();
	}

	public boolean isEmpty() {
		if (this.size == 0) {
			return true;
		}
		return false;
	}

	public int stack_cnt() {
		return this.size;
	}

	public int number_cnt() {
		return this.count;
	}

}

---

해답

스택이 꽉 찼을 경우 새로운 스택을 만들어준다.

---

<스택으로 큐>

스택 2개로 큐 하나를 구현하여라.

어려워서 해답을 봤다.

---

코드

package stackNqueue;

public class StackQueue {
	private myStack newest, oldest;

	public StackQueue() {
		this.newest = new myStack();
		this.oldest = new myStack();
	}

	public void add(int v) {
		newest.push(v);
	}

	public int peek() throws Exception {
		if (this.isEmpty()) {
			throw new Exception();
		}
		this.shiftStacks();
		return this.oldest.peek();
	}

	public int pop() throws Exception {
		if (this.isEmpty()) {
			throw new Exception();
		}
		this.shiftStacks();
		return this.oldest.pop();
	}

	public void shiftStacks() {
		if (oldest.isEmpty()) {
			while (!newest.isEmpty()) {
				oldest.push(newest.pop());
			}
		}
	}

	public boolean isEmpty() {
		int temp = newest.size() + oldest.size();
		if (temp == 0) {
			return true;
		}
		return false;
	}
	
	public int size() {
		return newest.size() + oldest.size();
		
	}

}

---

해답

새로 들어오는 원소가 top인 스택 newest와 이전에 들어온 원소가 top인 스택 oldest를 사용하여 해결할 수 있다.

원소를 넣을 때는 newest에만 넣는다.

원소를 빼거나 top의 값을 볼 때는 oldest에서 하는데, 이때 oldest가 비어있다면 newest에 있는 원소를 모두 oldest로 옮겨준다.

oldest에 들어갈 때는 순서가 뒤집어져서 newest에 마지막에 들어온 원소부터 들어가기 때문에 oldest에서 빼낼 때는 가장 오래된 원소부터 나온다.

---

<스택 정렬>

가장 작은 값이 위로 오도록 스택을 정렬하여라.

어려워서 해답을 봤다.

---

코드

package stackNqueue;

public class StackSort {
	public static void main(String[] args) throws Exception {
		myStack stack = new myStack();
		myStack sorted = new myStack();

		int[] number = { 8, 12, 3, 10, 7};
		for(int i = 0; i < number.length; i++) {
			stack.push(number[i]);
		}
		while(!stack.isEmpty()) {
			if(sorted.isEmpty()) {
				sorted.push(stack.pop());
				continue;
			}
			int temp = stack.pop();
			while(!sorted.isEmpty()) {
				if(temp < sorted.peek()) {
					stack.push(sorted.pop());
				}else {
					break;
				}
			}
			sorted.push(temp);
		}
		while(!sorted.isEmpty()) {
			System.out.println(sorted.pop());
		}

	}

}

---

해답

stack에 있는 원소를 정렬하여 sorted에 넣는다.

stack의 top에 있는 원소를 꺼낸다. 해당 원소가 sorted의 top보다 크거나 같을 때까지 꺼내서 다시 stack에 넣는다. stack의 top에 있던 원소는 sorted에 넣는다.

---

스택 정렬 프로세스

초기 stack과 sorted 스택

스택 정렬

---

<동물 보호소>

먼저 들어온 동물이 먼저 나가는 동물 보호소가 있다. 이 보호소에는 개와 고양이만 있고 사람들은 보호소에 가장 오래 있던 동물부터 입양할 수 있다. enqueue, dequeueAny, dequeueCat, dequeueDog를 구현하여라.

내가 짠 코드

package stackNqueue;

public class AnimalShelter {
	int chkCat, chkDog, cat_size, dog_size;
	myQueue cat, dog, any;

	public AnimalShelter() {
		this.chkCat = 0;
		this.chkDog = 0;
		this.cat_size = 0;
		this.dog_size = 0;
		this.cat = new myQueue();
		this.dog = new myQueue();
		this.any = new myQueue();

	}

	public void enqueue(int v, String t) {
		this.any.add(v, t);
		if (t.equals("Cat")) {
			this.cat.add(v, t);
			this.cat_size++;
		}
		if (t.equals("Dog")) {
			this.dog.add(v, t);
			this.dog_size++;
		}
	}

	public String dequeueCat() {
		if (this.isCatEmpty()) {
			return "None";
		}
		this.chkCat++;
		this.cat_size--;
		return cat.remove().toString();
	}

	public String dequeueDog() {
		if (this.isDogEmpty()) {
			return "None";
		}
		this.chkDog++;
		this.dog_size--;
		return dog.remove().toString();
	}

	public String dequeueAny() {
		if (this.isEmpty()) {
			return "None";
		}
		myNode temp = any.remove();
		while (true) {
			if (temp.type.equals("Cat")) {
				if (this.chkCat == 0) {
					cat.remove();
					return temp.toString();
				}
				this.chkCat--;
				temp = any.remove();
			} else if (temp.type.equals("Dog")) {
				if (this.chkDog == 0) {
					dog.remove();
					return temp.toString();
				}
				this.chkDog--;
				temp = any.remove();
			}
		}
	}

	public boolean isCatEmpty() {
		if (this.cat_size == 0) {
			return true;
		}
		return false;
	}

	public boolean isDogEmpty() {
		if (this.dog_size == 0) {
			return true;
		}
		return false;
	}

	public boolean isEmpty() {
		if (this.isCatEmpty() && this.isDogEmpty()) {
			return true;
		}
		return false;
	}
}

---

해답

고양이를 저장하는 cat 큐와 개를 저장하는 dog 큐를 만든다. dequeueAny는 cat의 top과 dog의 top 중 먼저 들어온 동물을 꺼내게 한다. 이를 위해 들어온 날짜를 저장할 필요가 있다.

---

동물 보호소 문제의 해답은 따라쳐보기!!