๐Ÿ‘‰Queue(ํ)

Queue์€ ์„ ์ž…์„ ์ถœ(First In First Out: LIFO)์˜ ์ž๋ฃŒ๊ตฌ์กฐ

๋จผ์ € ์ž…๋ ฅ๋œ ๊ฐ’์ด ์ œ์ผ ๋จผ์ € ์ถœ๋ ฅ์ด ๊ฐ€๋Šฅํ•œ ์ž๋ฃŒ๊ตฌ์กฐ

Stack๊ณผ ๋‹ค๋ฅด๊ฒŒ ์ค‘์š”ํ•œ Keyword๋Š” #Front์™€ #Rear ์ด๋‹ค.

๊ทธ๋ฆฌ๊ณ  Stack์—์„œ๋Š” ๋ฐ์ดํ„ฐ ์ž…๋ ฅ๊ณผ ์ถœ๋ ฅ์ด Push/Pop์ด์˜€์ง€๋งŒ,

Queue์—์„œ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ์–ด์ฃผ๋Š” ๊ธฐ๋Šฅ์€ #Enqueue, ๋ฐ์ดํ„ฐ๋ฅผ ๋‚ด๋ณด๋‚ด๋Š” ๊ธฐ๋Šฅ์€ #Dequeue

queue.PNG

Queue(ํ)๊ฐ€ ์‹คํ–‰๋  ๋•Œ ์ถ”์ƒ์  ์ด๋ฏธ์ง€

Queue์˜ ๊ฒฝ์šฐ

๋ฐ์ดํ„ฐ๋ฅผ ์Œ“๋Š” ๊ฒƒ์€ ๋ฐฐ์—ด ๋ฉ”์„œ๋“œ๋Š” Push / ๋นผ๋‚ด๋Š” ๊ฒƒ์€ Shift

Rear - Queue์˜ ๋’ท๋ถ€๋ถ„์„ ๋œปํ•œ๋‹ค.

๋ฐ์ดํ„ฐ๊ฐ€ ์‚ฝ์ž…๋  ์‹œ Rear๋Š” ํ•œ์นธ์”ฉ ๋’ค๋กœ ์œ„์น˜ํ•œ๋‹ค.

q1.PNG

< ์ด๋ฏธ์ง€ ์ถœ์ฒ˜ : https://kingpodo.tistory.com/24?category=805745 >

Front - Queue์˜ ์•ž๋ถ€๋ถ„์„ ๋œปํ•œ๋‹ค.

๋ฐ์ด๊ฑฐ ์‚ญ์ œ๋˜๋ฉด Front๊ฐ€ ํ•œ์นธ์”ฉ ๋’ค๋กœ ์œ„์น˜ํ•œ๋‹ค.

q2.PNG

< ์ด๋ฏธ์ง€ ์ถœ์ฒ˜ : https://kingpodo.tistory.com/24?category=805745 >

> ๐Ÿฑโ€๐Ÿ์‚ฌ์šฉ ์‚ฌ๋ก€

๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS, Breadth-First Search) ๊ตฌํ˜„ (์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€ ํ•„์š”)
  • ์ฒ˜๋ฆฌํ•ด์•ผ ํ•  ๋…ธ๋“œ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ €์žฅํ•˜๋Š” ์šฉ๋„๋กœ ํ(Queue)๋ฅผ ์‚ฌ์šฉ
  • ๋…ธ๋“œ๋ฅผ ํ•˜๋‚˜ ์ฒ˜๋ฆฌํ•  ๋•Œ๋งˆ๋‹ค ํ•ด๋‹น ๋…ธ๋“œ์™€ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋“ค์„ ํ์— ๋‹ค์‹œ ์ €์žฅ
  • ๋…ธ๋“œ๋ฅผ ์ ‘๊ทผํ•œ ์ˆœ์„œ๋Œ€๋กœ ์ฒ˜๋ฆฌ
์บ์‹œ(Cache) ๊ตฌํ˜„

์žฅ์ : ๋ฐ์ดํ„ฐ๋ฅผ ์ž…๋ ฅ๋œ ์ˆœ์„œ๋Œ€๋กœ ์ฒ˜๋ฆฌํ•ด์•ผ ํ•  ์ƒํ™ฉ์— ์œ ๋ฆฌ(ex. ์€ํ–‰ ์ˆœ์„œ ๋‹จ๋ง๊ธฐ)

๋‹จ์  : ํฌ๊ธฐ๊ฐ€ ์ œํ•œ์ , ํ์˜ ์•ž๋ถ€๋ถ„์ด ๋น„์—ฌ๋„ ๋ฐ์ดํ„ฐ๋ฅผ ์‚ฝ์ž… ๋ถˆ๊ฐ€๋Šฅ

๐Ÿ‘‰Queue(Pseudo Code)

var QueueArr = [];            // ๋นˆ๋ฐฐ์—ด ์ƒ์„ฑ
QueueArr.push(element1);      // enqueue ๊ตฌํ˜„ (element1)์š”์†Œ ์ถ”๊ฐ€
QueueArr.push(element2);      // enqueue ๊ตฌํ˜„ (element2)์š”์†Œ ์ถ”๊ฐ€
QueueArr.shift();             // dequeue ๊ตฌํ˜„ (์•ž์š”์†Œ) ์ œ๊ฑฐ
console.log(QueueArr);        // [element2]; ์ถœ๋ ฅ
QueueArr.length;              // ํ์˜ size 

๐Ÿ‘‰Queue(functional)

const Queue = function() {
  const someInstance = {};

  let front = 0;
  let rear = 0;
  let count = 0;

  // Use an object with numeric keys to store values

  const storage = {};

  // Implement the methods below

  someInstance.enqueue = function(value) {
    storage[rear] = value;
    rear++;
    count++;
  };

  someInstance.dequeue = function() {
    if (count > 0) {
      var deValue = storage[front];
      delete storage[front];
      front++;
      count--;
      return deValue;
    }
  };

  //storage ๋ชฉ๋ก ํ™•์ธ
  /*
  someInstance.view = function () {
    console.log(storage);
  }
  */

  someInstance.size = function() {
    return count;
  };

  return someInstance;
};