[자료구조][JS] 스택, 큐 - push(), pop(), shift()

기본적인 자료구조인 스택, 큐에 대해서 JS로 정리해보려 한다.

push()

push() 메서드는 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환한다.

arr.push(element1[, ...[, elementN]])

 

elementN: 배열의 끝에 추가할 요소.

 

const animals = ['pigs', 'goats', 'sheep'];

const count=animals.push('cows');
console.log(count); // expected output: 4
console.log(animals); // expected output: Array ["pigs", "goats", "sheep", "cows"]

animals.push('cats', 'dogs');
console.log(animals);
// expected output: Array ["pigs", "goats", "sheep", "cows", "cats", "dogs"]

// 두 개의 배열 합칠 때
Array.prototype.push.apply(animals, news);
console.log(animals);
// expected output: Array ["pigs", "goats", "sheep", "cows", "cats", "dogs", "rabbits", "horses"]

pop()

pop() 메서드는 배열에서 마지막 요소를 제거하고 그 요소를 반환한다.

arr.pop()

 

반환값: 배열에서 제거한 요소. 빈 배열의 경우 undefined를 반환.

 

var myFish = ['angel', 'clown', 'mandarin', 'sturgeon'];

var popped = myFish.pop();

console.log(myFish); // ['angel', 'clown', 'mandarin' ]

console.log(popped); // 'sturgeon'

shift()

shift() 메서드는 배열에서 첫 번째 요소(0번째 위치의 요소)를 제거하고 연이은 나머지 값들의 위치를 한 칸 씩 앞으로 당기고, 제거된 요소를 반환한다. 

arr.shift()

 

반환값: 배열에서 제거한 요소. 빈 배열의 경우 undefined를 반환.

 

var myFish = ['angel', 'clown', 'mandarin', 'surgeon'];

var shifted = myFish.shift();

console.log('myFish after: ' + myFish);
// "myFish after: clown, mandarin, surgeon"

console.log('Removed this element: ' + shifted);
// "Removed this element: angel"

 

 

---

스택(Stack)

• 데이터를 집어넣을 수 있는 선형(linear) 자료형.
• 나중에 들어간 데이터가 먼저 나온다. -> LIFO(Last In First Out).
• 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 넣은 데이터를 확인하는 peek 등의 작업을 할 수 있다.

보통 아래와 같은 그림으로 많이 표현한다.

JS에서는 간단히 배열로 선언해서 push(), pop()을 이용해서 스택을 구현할 수 있다.

 

let stack=[];

stack.push(2); //2
stack.push(3); //2, 3
stack.push(4); //2, 3, 4

stack.pop(); //4
stack.pop(); //3
stack.pop(); //2

 

좀 더 제대로 구현하면 아래와 같이도 만들 수 있겠다.

 

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}

const stack = new Stack();

stack.push(1); //1
stack.push(2); //1, 2
stack.push(3); //1, 2, 3

stack.pop(); // 3

 

큐(Queue)

• 데이터를 집어넣을 수 있는 선형 자료형.
• 먼저 집어넣은 데이터가 먼저 나온다. -> FIFO(First In First Out)
• 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있다.

 

 

push()와 shift()를 이용해서 queue를 간단히 구현할 수 있다.

 

let queue=[];

queue.push(1); //1
queue.push(2); //1, 2
queue.push(3); //1, 2, 3

//앞에서부터 삭제
queue.shift(); //1
queue.shift(); //2
queue.shift(); //3

 

다른 버전

 

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
}

const queue = new Queue();

queue.enqueue(1); //1
queue.enqueue(2); //1, 2
queue.enqueue(3); //1, 2, 3

queue.dequeue(); // 1