首页 > itarticle > stack과 queue, 그리고 deque의 차이점 Queue Deque

stack과 queue, 그리고 deque의 차이점 Queue Deque

admin 11月 13, 2020 0

Stack이란, 한쪽 끝에서만 데이터의 삽입, 삭제가 이루어지는 자료구조다.

  • 가장 마지막에 삽입된 항목이 맨 먼저 삭제된다. -> Last In First Out(LIFO)
    • push: Stack에 데이터를 넣는 연산
    • pop: Stack에 데이터를 꺼내는 연산
    • peek: Stack에 데이터를 들여다 보는 연산

Stack
출처: Stack

Stack 구현

1. class를 이용한 Stack 구현(ES6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
// ES6
class Stack {
  constructor() {
    this.count = 0;
    this.dataStore = [];
  }

  push(element) {
    this.dataStore[this.count] = element;
    this.count++;
  }

  pop() {
    if(this.count >= 1) {
      let val = this.dataStore[this.count - 1];
      this.count--;
      return val;
    }
    return null;
  }

  peek() {
    return this.dataStore[this.count - 1];
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.count === 0;
  }

  clear() {
    this.count = 0;
    this.dataStore = [];
  }
}

// for Test
const stack = new Stack();
console.log(stack); // { count: 0, dataStore: [] }
stack.push('ro1');
stack.push('ro2');
stack.push('ro3');
console.log(stack.peek()); // ro3
console.log(stack.pop()); // ro3
console.log(stack.pop()); // ro2
console.log(stack.size()); // 1
console.log(stack.isEmpty()); // false
console.log(stack.pop()); // ro1
console.log(stack.pop()); // null

2. 생성자 함수를 이용한 Stack 구현(ES5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
// ES5
function Stack() {
  var dataStore = [];
  var count = 0;

  this.push = function(element) {
    dataStore[count] = element;
    count++;
  };

  this.pop = function() {
    if(count >= 1) {
      let val = dataStore[count - 1];
      count--;
      return val;
    }
    return null;
  };

  this.peek = function() {
    return dataStore[count - 1];
  };

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

  this.isEmpty = function() {
    return count === 0;
  };
}

// for Test
var stack = new Stack();
console.log(stack); // { push: [Function], pop: [Function], peek: [Function], size: [Function], isEmpty: [Function] }
stack.push('ro1');
stack.push('ro2');
stack.push('ro3');
console.log(stack.peek()); // ro3
console.log(stack.pop()); // ro3
console.log(stack.pop()); // ro2
console.log(stack.size()); // 1
console.log(stack.isEmpty()); // false
console.log(stack.pop()); // ro1
console.log(stack.pop()); // null

Queue

Queue란, 데이터의 삽입이 한쪽 끝(뒤, rear)에서 이루어지고, 삭제는 다른 쪽(앞, front)에서 이루어지는 자료구조다.

  • 가장 처음 삽입된 항목이 맨 먼저 삭제된다. -> First In First Out(FIFO)
    • enqueue: Queue에 데이터를 넣는 연산
    • dequeue: Queue에 데이터를 꺼내는 연산

Queue
출처: Queue

Queue 구현(2개의 Stack으로 Queue 구현)

1. class를 이용한 Queue 구현(ES6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
// Stack
class Stack {
  constructor() {
    this.count = 0;
    this.dataStore = [];
  }

  push(element) {
    this.dataStore[this.count] = element;
    this.count++;
  }

  pop() {
    if(this.count >= 1) {
      let val = this.dataStore[this.count - 1];
      this.count--;
      return val;
    }
    return null;
  }

  peek() {
    return this.dataStore[this.count - 1];
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.count === 0;
  }

  clear() {
    this.count = 0;
    this.dataStore = [];
  }
}

// Queue
class Queue {
  constructor() {
    this.inbox = new Stack();
    this.outbox = new Stack();
    this.size = 0;
  }

  eneque(element) {
    this.inbox.push(element);
  }

  dequeue() {
    if(this.outbox.size() === 0) {
      while(this.inbox.size()) {
        this.outbox.push(this.inbox.pop());
      }
    }
    return this.outbox.pop();
  }

  size() {
    return this.inbox.size() + this.outbox.size();
  }
}

// for Test
const queue = new Queue();
console.log(queue); // { inbox: Stack { count: 0, dataStore: [] }, outbox: Stack { count: 0, dataStore: [] } size: 0 }
queue.eneque('a');
queue.eneque('b');
queue.eneque('c');
console.log(queue.dequeue()); // a
console.log(queue.dequeue()); // b
queue.eneque('d');
queue.eneque('e');
console.log(queue.dequeue()); // c
console.log(queue.dequeue()); // d

2. 생성자 함수를 이용한 Queue 구현(ES5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
// Stack
function Stack() {
  var dataStore = [];
  var count = 0;

  this.push = function(element) {
    dataStore[count] = element;
    count++;
  };

  this.pop = function() {
    if(count >= 1) {
      let val = dataStore[count - 1];
      count--;
      return val;
    }
    return null;
  };

  this.peek = function() {
    return dataStore[count - 1];
  };

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

  this.isEmpty = function() {
    return count === 0;
  };
}

// Queue
function Queue() {
  var inbox = new Stack();
  var outbox = new Stack();

  this.eneque = function(element) {
    inbox.push(element);
  };

  this.dequeue = function() {
      if (outbox.size() === 0) {
          while (inbox.size())
              outbox.push(inbox.pop());
      }
      return outbox.pop();
  };

  this.size = function(){
    return inbox.size() + outbox.size();
  };
}

// for Test
var queue = new Queue();
console.log(queue); // { eneque: [Function], dequeue: [Function], size: [Function] }
queue.eneque('a');
queue.eneque('b');
queue.eneque('c');
console.log(queue.dequeue()); // a
console.log(queue.dequeue()); // b
queue.eneque('d');
queue.eneque('e');
console.log(queue.dequeue()); // c
console.log(queue.dequeue()); // d

Deque

Deque란, 데이터의 삽입과 삭제를 앞, 뒤 양쪽에서 이루어지는 자료구조다.

Deque
출처: Deque

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能