스택(Stack)과 큐(Queue)

스택(Stack) 이란?

메모리안의 데이터들을 효율적으로 관리하게 도와주는 자료 참조 방식

FILO(First in Last out) : 처음에 오는 데이터가 제일 마지막에 나간다.

LIFO(Last in First out) : 제일 마지막에 들어온 데이터가 제일 처음에 나간다.

스택 구현 방법

1. 1차원 배열

- 구현이 상대적으로 쉬우나 인풋 사이즈를 미리 알아야 함.

2. 리스트

- 구현이 상대적으로 어려우나 제한된 사이즈로부터 자유로움.

스택 주요 기능

1. Push

스택에 데이터를 추가하는 기능

2. Pop

스택의 최상위 데이터를 빼내어서 가져오는 기능

3. Top / Peek 

제일 최근에 들어간 데이터, 최근의 데이터

public class Stack { private int MAX_SIZE; private int[] stack; private int top; public Stack() { MAX_SIZE = 5; stack = new int[MAX_SIZE]; top = -1; } private boolean isEmpty() { return top == -1 ? true : false; } private boolean isFull() { return (top + 1 == MAX_SIZE) ? true : false; } public void push(int data) { if (!isFull()) stack[++top] = data; } public int pop() { if (!isEmpty()) return stack[top--]; return -1; } public void display() { System.out.print("top : " + top + "\nstack : "); for (int idx = 0; idx <= top; idx++) System.out.print(stack[idx] + " "); System.out.println(); } }

큐(Queue) 란?

스택과 마찬가지로 메모리안의 데이터들을 효율적으로 관리하게 도와주는 자료 참조 방식

FIFO(First in First out) : 처음에 오는 데이터가 제일 처음에 나간다.

큐의 대표적인 사용 사례

- 프로세스 스케줄링

- 대부분의 입출력

- 프린트 대기열

큐의 구현 방법

1. 정적배열 (Fixed Array)

-구현이 상대적으로 쉬우나 인풋 사이즈를 미리 알아야 함.

2. 동적배열 (Linked List)

- 구현이 상대적으로 어려우나 제한된 사이즈로부터 자유로움.

큐의 주요 기능

1. Enqueue

큐에 값을 집어넣는 함수 

2. Dequeue

큐에 값을 빼내는 함수

3. Size 

큐의 크기를 확인한다.

4. Empty

큐가 비었는지 확인한다.

var Queue = (function() {   function Queue() {     this.count = 0;     this.head = null;     this.rear = null;   }   function Node(data) {     this.data = data;     this.next = null;   }   Queue.prototype.enqueue = function(data) {     var node = new Node(data);     if (!this.head) {       this.head = node;     } else {       this.rear.next = node;     }     this.rear = node;     return ++this.count;   };   Queue.prototype.dequeue = function() {     if (!this.head) { // stack underflow 방지       return false;     }     var data = this.head.data;     this.head = this.head.next;     // this.head 메모리 클린     —this.count;     return data;   };   Queue.prototype.front = function() {     return this.head && this.head.data;   };   return Queue; })();

면접 예상 질문

Q. 스택으로 큐를 구현할 수 있을까?

A. 두개의 스택을 활용하여 가능합니다.

하나의 스택은 push 를 담당하고, 다른 하나의 스택은 pop 을 담당한다.

stack1 의 item 을 pop하여 stack2 에 담고, stack2 의 item 을 pop 하면 큐를 구현할 수 있다.

public class Queue<E> {     private Stack<E> inbox = new Stack<E>();     private Stack<E> outbox = new Stack<E>();     public void queue(E item) {         inbox.push(item);     }     public E dequeue() {         if (outbox.isEmpty()) {             while (!inbox.isEmpty()) {                outbox.push(inbox.pop());             }         }         return outbox.pop();     } }