Chapter3 Stacks and Queues

How to Approach?

 기본적인 Stack, Queue를 구현하는 방법에 대해 확실히 알고있어야 합니다. 인터뷰전 Stack과 Queue는 확실하게 구현할 수 있도록 합시다. Stack과 Queue는 List의 하위 자료구조로 들어온 데이터의 순서와 나가는 데이터의 순서가 다릅니다. Stack같은 경우는 불공평하다고 생각하지만 먼저 들어온 데이터가 가장 나중에 나가고 Queue는 공평하게 줄서있는것처럼 먼저들어온 데이터가 먼저 나가게 됩니다. 이때 내부적으로는 배열이나 연결리스트를 사용하여 데이터를 저장할 수 있는데 각각의 장단점은 배열과 연결리스트의 장단점과 같습니다.(배열의 경우는 인덱스를 통한 접근을 통해 탐색이 O(1)로 무척 빠르며 삽입/삭제시에는 shift 과정이 필요하여 O(N)의 복잡도를 가집니다. 반면 연결리스트는 탐색을 할때 하나하나 다 살펴보아야 하므로 O(N)의 시간복잡도를 가지고 삽입/삭제시에는 해당 노드의 앞뒤 연결부만 관리해주면 되므로 상수시간의 복잡도를 가집니다.) 

 

Implementing Stack

Implementing Queue

Interview Questions

3.1~3.2 배열을 사용하여 스택을 구현하라. 

3.3 스택을 배열로 구현시 일정 임계치를 지나면 더이상 데이터를 저장할 수 없다. 때문에 스택안의 배열의 길이가 임계치에 다달았을때 2배로 늘리는 스택을 구현하고, 특정 index의 데이터를 pop할수있는 popAt(index) 메서드를 작성하라.

배열을 이용하여 구현한 스택입니다. 임계치에 다다르면 배열의 크기를 2배로 늘리는 방식입니다. 특정 index의 엘리먼트를 추출하는 popAt(index) 연산시에는 index 이후의 엘리먼트들이 모두 왼쪽으로 한칸씩 shift하는 연산이 필요합니다.

3.4 하노이 타워

3.5 Stack 2개를 이용하여 Queue를 구현하시오.

class Queue{
	private Stack inqueueStack;
	private Stack dequeueStack;
	
	public Queue() {
		inqueueStack = new Stack<>();
		dequeueStack = new Stack<>();
	}
	
	public void enqueue(int data) {
		inqueueStack.push(data);
	}
	
	public int dequeue() {
		if(dequeueStack.isEmpty()) {
			while(!inqueueStack.isEmpty()) {
				dequeueStack.push(inqueueStack.pop());
			}
		}
		return dequeueStack.pop();
	}
}

3.6 Stack을 오름차순으로 정렬하는 프로그램을 작성하시오. 단 다음과 같은 함수만 사용하여야 한다. (push | pop | peek | isEmpty)

public static Stack sortAsc(Stack stack){
		Stack orderedStack = new Stack();
		while(!stack.isEmpty()) {
			int tmp = stack.pop();
			while(!orderedStack.isEmpty() && orderedStack.peek() > tmp) {
				stack.push(orderedStack.pop());
			}
			orderedStack.push(tmp);
		}
		return orderedStack;
	}
}