algorithm 알고리즘 Data Structure 자료구조 Queue 큐 Stack 스택

[Algorithm] Data Structure - Queue and Stack

자료구조 큐/스택

Posted by lim.Chuck on September 12, 2024

참고 《 생활 코딩 Queue》

Queue 와 Stack 비교

특성 큐(Queue) 스택(Stack)
데이터 처리 방식 선입선출(FIFO) 후입선출(LIFO)
삽입 위치 뒤(Rear) 위(Top)
삭제 위치 앞(Front) 위(Top)
주요 연산 enqueue(삽입)
dequeue(삭제)		 push(삽입)
pop(삭제)
사용 사례 대기열 처리, 프린터 작업 순서 함수 호출 스택, 되돌리기(Undo)

Queue 와 Stack 사용 사례

  1. 큐(Queue)
    • 프로세스 관리: 운영체제에서 CPU 스케줄링을 할 때, 작업이나 프로세스를 순차적으로 처리하기 위해 큐를 사용합니다.
    • 네트워크 패킷 처리: 네트워크에서 패킷이 들어오는 순서대로 처리할 때 큐를 사용합니다.
    • 프린터 작업 관리: 여러 개의 인쇄 작업을 순차적으로 처리하기 위해 큐가 사용됩니다.
  2. 스택(Stack)
    • 함수 호출 스택: 프로그램에서 함수가 호출될 때 호출된 순서대로 반환하는 방식으로 사용됩니다.
    • 문서 편집기: 텍스트 편집기에서 되돌리기(Undo) 기능은 스택을 이용하여 최근 작업을 역순으로 되돌립니다.
    • 수식 계산: 컴퓨터에서 후위 표기법(Reverse Polish Notation)으로 수식을 계산할 때 스택이 사용됩니다.

Queue?

큐(Queue)는 선입선출(FIFO, First In First Out) 방식의 자료 구조로, 먼저 들어간 데이터가 먼저 나오는 구조입니다. 큐는 주로 줄을 서는 상황이나 작업 대기열을 처리할 때 유용하게 사용됩니다.

큐의 기본적인 동작은 아래와 같습니다:

  1. enqueue(삽입): 큐의 뒤쪽에 데이터를 추가하는 작업.
  2. dequeue(제거): 큐의 앞쪽에서 데이터를 제거하는 작업.
  3. peek/front: 큐의 앞쪽에 있는 데이터를 제거하지 않고 확인하는 작업.
  4. isEmpty: 큐가 비어 있는지 확인하는 작업.

javascript

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

class Queue {
  constructor() {
    this.items = [];
  }

  // 데이터 추가
  enqueue(element) {
    this.items.push(element);
  }

  // 데이터 제거
  dequeue() {
    if (this.isEmpty()) {
      return "큐가 비어있습니다.";
    }
    return this.items.shift(); // 첫 번째 요소 제거
  }

  // 큐의 앞쪽 요소 확인
  front() {
    if (this.isEmpty()) {
      return "큐가 비어있습니다.";
    }
    return this.items[0];
  }

  // 큐가 비었는지 확인
  isEmpty() {
    return this.items.length === 0;
  }

  // 큐의 크기 확인
  size() {
    return this.items.length;
  }
}

// 사용 예시
let queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.front()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.front()); // 20

Rust

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

struct Queue<T> {
    items: Vec<T>,  // 제네릭 타입을 이용한 벡터
}

impl<T> Queue<T> {
    // 큐 초기화
    fn new() -> Self {
        Queue { items: Vec::new() }
    }

    // 데이터 추가
    fn enqueue(&mut self, item: T) {
        self.items.push(item);
    }

    // 데이터 제거
    fn dequeue(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            Some(self.items.remove(0))  // 첫 번째 요소 제거
        }
    }

    // 큐의 앞쪽 요소 확인
    fn front(&self) -> Option<&T> {
        self.items.first()
    }

    // 큐가 비었는지 확인
    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    // 큐의 크기 확인
    fn size(&self) -> usize {
        self.items.len()
    }
}

fn main() {
    let mut queue = Queue::new();
    queue.enqueue(10);
    queue.enqueue(20);
    println!("{:?}", queue.front());  // Some(10)
    println!("{:?}", queue.dequeue());  // Some(10)
    println!("{:?}", queue.front());  // Some(20)
}

자바스크립트와 Rust에서 각각 큐를 구현하는 방법을 위와 같이 작성할 수 있습니다. 두 언어의 문법 차이에도 불구하고, 큐의 동작 원리는 동일합니다.

Stack?

스택(Stack)은 후입선출(LIFO, Last In First Out) 방식의 자료 구조입니다. 즉, 가장 마지막에 들어간 데이터가 가장 먼저 나오는 구조입니다. 스택은 쌓인 책이나 함수 호출 스택 등에서 많이 사용됩니다.

스택의 기본적인 동작은 아래와 같습니다:

  1. push(삽입): 스택의 맨 위에 데이터를 추가하는 작업.
  2. pop(제거): 스택의 맨 위에서 데이터를 제거하는 작업.
  3. peek/top: 스택의 맨 위에 있는 데이터를 제거하지 않고 확인하는 작업.
  4. isEmpty: 스택이 비어 있는지 확인하는 작업.

javascript

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

class Stack {
  constructor() {
    this.items = [];
  }

  // 데이터 추가
  push(element) {
    this.items.push(element);
  }

  // 데이터 제거
  pop() {
    if (this.isEmpty()) {
      return "스택이 비어있습니다.";
    }
    return this.items.pop(); // 마지막 요소 제거
  }

  // 스택의 맨 위 요소 확인
  peek() {
    if (this.isEmpty()) {
      return "스택이 비어있습니다.";
    }
    return this.items[this.items.length - 1];
  }

  // 스택이 비었는지 확인
  isEmpty() {
    return this.items.length === 0;
  }

  // 스택의 크기 확인
  size() {
    return this.items.length;
  }
}

// 사용 예시
let stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop()); // 20
console.log(stack.peek()); // 10

Rust

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

struct Stack<T> {
    items: Vec<T>,  // 제네릭 타입을 이용한 벡터
}

impl<T> Stack<T> {
    // 스택 초기화
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    // 데이터 추가
    fn push(&mut self, item: T) {
        self.items.push(item);
    }

    // 데이터 제거
    fn pop(&mut self) -> Option<T> {
        self.items.pop()  // 마지막 요소 제거
    }

    // 스택의 맨 위 요소 확인
    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    // 스택이 비었는지 확인
    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    // 스택의 크기 확인
    fn size(&self) -> usize {
        self.items.len()
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(10);
    stack.push(20);
    println!("{:?}", stack.peek());  // Some(20)
    println!("{:?}", stack.pop());  // Some(20)
    println!("{:?}", stack.peek());  // Some(10)
}

위 예제에서는 자바스크립트와 Rust에서 각각 스택을 구현하는 방법을 보여주었습니다. 두 언어 모두 벡터 또는 배열을 사용하여 스택의 LIFO 동작을 쉽게 구현할 수 있습니다.

Queue vs. Stack Comparison

Feature Queue (FIFO) Stack (LIFO)
Data Handling First In First Out (FIFO) Last In First Out (LIFO)
Insertion Point Rear Top
Removal Point Front Top
Main Operations enqueue(add)
dequeue(remove)		 push(add)
pop(remove)
Use Cases Queue processing, print job ordering Function call stack, undo

Queue and Stack Use Cases

  1. Queue
    • Process Management: In operating systems, queues are used to handle processes or tasks sequentially, such as in CPU scheduling.
    • Network Packet Processing: Queues are used to process network packets in the order they arrive.
    • Printer Job Management: Queues are used to handle multiple print jobs in sequential order.
  2. Stack
    • Function Call Stack: When a function is called in a program, a stack is used to return the functions in reverse order.
    • Text Editor: The undo feature in text editors uses a stack to reverse recent actions in order.
    • Expression Evaluation: Stacks are used to calculate expressions in Reverse Polish Notation (RPN).

Queue?

A Queue is a data structure that follows the First In First Out (FIFO) principle, meaning that the first data entered is the first to be removed. Queues are useful for handling tasks like waiting lines or job queues.

The basic operations of a queue are as follows:

  1. enqueue(add): Adds data to the rear of the queue.
  2. dequeue(remove): Removes data from the front of the queue.
  3. peek/front: Checks the data at the front of the queue without removing it.
  4. isEmpty: Checks whether the queue is empty.

JavaScript

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

class Queue {
  constructor() {
    this.items = [];
  }

  // Add data
  enqueue(element) {
    this.items.push(element);
  }

  // Remove data
  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty.";
    }
    return this.items.shift(); // Remove the first element
  }

  // Check the front element of the queue
  front() {
    if (this.isEmpty()) {
      return "Queue is empty.";
    }
    return this.items[0];
  }

  // Check if the queue is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // Check the size of the queue
  size() {
    return this.items.length;
  }
}

// Example usage
let queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.front()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.front()); // 20

Rust

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

struct Queue<T> {
    items: Vec<T>,  // Vector using a generic type
}

impl<T> Queue<T> {
    // Initialize queue
    fn new() -> Self {
        Queue { items: Vec::new() }
    }

    // Add data
    fn enqueue(&mut self, item: T) {
        self.items.push(item);
    }

    // Remove data
    fn dequeue(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            Some(self.items.remove(0))  // Remove the first element
        }
    }

    // Check the front element of the queue
    fn front(&self) -> Option<&T> {
        self.items.first()
    }

    // Check if the queue is empty
    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    // Check the size of the queue
    fn size(&self) -> usize {
        self.items.len()
    }
}

fn main() {
    let mut queue = Queue::new();
    queue.enqueue(10);
    queue.enqueue(20);
    println!("{:?}", queue.front());  // Some(10)
    println!("{:?}", queue.dequeue());  // Some(10)
    println!("{:?}", queue.front());  // Some(20)
}

The examples above show how to implement a queue in both JavaScript and Rust. Despite the syntactical differences, the underlying behavior of the queue remains the same.

Stack?

A Stack is a data structure that follows the Last In First Out (LIFO) principle, meaning that the last data entered is the first to be removed. Stacks are often used in scenarios like piles of books or function call stacks.

The basic operations of a stack are as follows:

  1. push(add): Adds data to the top of the stack.
  2. pop(remove): Removes data from the top of the stack.
  3. peek/top: Checks the data at the top of the stack without removing it.
  4. isEmpty: Checks whether the stack is empty.

JavaScript

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

class Stack {
  constructor() {
    this.items = [];
  }

  // Add data
  push(element) {
    this.items.push(element);
  }

  // Remove data
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty.";
    }
    return this.items.pop(); // Remove the last element
  }

  // Check the top element of the stack
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty.";
    }
    return this.items[this.items.length - 1];
  }

  // Check if the stack is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // Check the size of the stack
  size() {
    return this.items.length;
  }
}

// Example usage
let stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop()); // 20
console.log(stack.peek()); // 10

Rust

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

struct Stack<T> {
    items: Vec<T>,  // Vector using a generic type
}

impl<T> Stack<T> {
    // Initialize stack
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    // Add data
    fn push(&mut self, item: T) {
        self.items.push(item);
    }

    // Remove data
    fn pop(&mut self) -> Option<T> {
        self.items.pop()  // Remove the last element
    }

    // Check the top element of the stack
    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    // Check if the stack is empty
    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    // Check the size of the stack
    fn size(&self) -> usize {
        self.items.len()
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(10);
    stack.push(20);
    println!("{:?}", stack.peek());  // Some(20)
    println!("{:?}", stack.pop());  // Some(20)
    println!("{:?}", stack.peek());  // Some(10)
}

In this example, both JavaScript and Rust implementations of the stack are shown. Both languages use arrays or vectors to easily implement the LIFO behavior of a stack.

FEATURED TAGS
git 알고리즘 algorithm js 기초 js 기초 문법 js 문법 자료구조 Data Structure Graphs React 그래프 러스트 rust 집합 Sets front 수학 정렬 Math Sorting 간단예제 문자열 Strings github AWS 이벤트 버블링 이벤트 캡처링 탐색 LLM MCP Searches 컴파일러 트리 AI Cloud Front Cursor MCP 사용법 bubbling capturing s3 개발자도구 광고 구글 자동색인 깃허브 광고 라이브러리 러스트 설치 리엑트 버킷 비교 사이트맵 아마존 예제 웹 접근성 이미지 업로드 최장 공통 부분수열 캐시 텍스트 프레임워크 AI통합 API Adsense Claude Compiler SQL SWC Speedy Web Compiler Trees js 변수 js 생성자함수 npm nuxt pipeline project management robots rust 구축 rust setting rust setup text utterances
FRIENDS