자료구조 연결 스택, 연결 큐

 

연결 스택 Linked Stack

• 리스트를 이용해 스택을 구현할 수 있다
• 스택의 원소: 리스트의 노드
  • 스택 내의 순서는 리스트의 링크를 통해 연결됨
    • Push: 리스트의 마지막에 노드 삽입
    • Pop: 리스트의 마지막 노드 반환/삭제
• 변수 top
  • 리스트의 마지막 노드를 가리키는 변수
  • 초기 상태: top = null

리스트를 이용해 Push와 Pop 연산 구현

1. null 값을 가지는 노드를 만들어 스택 초기화
2. 원소 A 삽입 push(A)
3. 원소 B 삽입 push(B)
4. 원소 C 삽입 push(C)
5. 원소 반환 pop

Push/Pop

push(i) { // 원소 i를 스택에 push
    temp = createNode();
    temp.data = i;
    temp.link = top;
    top = temp;
}

pop() {
    temp = top;
    if (top==null) return 0;
    else {
        item = temp.data;
        top = temp.link; // top이 가리키는 노드 변경
        free(temp);
        return item;
    }
}

연결 큐 Linked Queue

---

연결 큐의 구조

단순 연결 리스트 (Linked List)를 이용한 큐

• 큐의 원소: 단순 연결 리스트의 노드
• 큐의 원소 순서: 노드의 연결 순서, 링크로 연결되어 있음
• front: 첫 번째 노드를 가리키는 링크
• rear: 마지막 노드를 가리키는 링크

상태 표현

• 초기 상태: front = rear = null
• 공백 상태: front = rear = null

연결 큐의 연산 과정

1) 공백 큐 생성: createLinkedQueue();

2) 원소 A 삽입: enQueue(A);

3) 원소 B 삽입: enQueue(B);

4) 원소 삭제: deQueue();

5) 원소 C 삽입: enQueue(C);