0330_단일 연결 리스트로 큐 구현하기

 

노드 생성,

+  Node 형식의 head, tail 생성

 

인큐 1단계 일단 넣어보기

인큐 2단계 예외 넣으면서 만들기

--

 

디큐 1단계 일단 빼보기

 

디큐 2단계 예외 넣으면서 빼기

 

 

Linked 리스트를 활용한 큐

큐에 새 데이타를 추가하기 위해서 연결리스트의 마지막에 새 노드를 추가, 
데이타를 꺼내오기 위해서는 연결 리스트의 첫 노드(head)를 읽어오면 된다.
단일 연결리스트를 구현하면서 head와 tail를 갖고하게
Tail를 통해 Enqueue 하고, Head를 통해 Dequeue하면 기능을 간단히 구현할 수있다. 

먼저 단일 연결리스트를 만들어준다.
노드 생성, 

 

 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace study17
{
    public class Node { //노드생성
        public string data;
        public Node next;
        public Node(string data) {
            this.data = data;
        }
    }
    public class QueueLinkedList
    {
        //head
        private Node head;
        private Node tail;
        //tail
        public QueueLinkedList()
        {

        }
        public void Enqueue(string data)
        {
            if (this.head == null)
            {  // 헤드가 비어 있을 경우는, data를 헤드로 만들어 줘야함
                this.head = new Node(data);
                this.tail = this.head; // 테일이 헤드가 되야한다. // 1칸 짜리 노드니깐
            }
            else {
                //헤드가 널이 아니니깐 만들어준다.
                this.tail.next = new Node(data);
                // 위 대로하면 테일이 계속 헤드로 지정되어 있어서  인큐하면 1번째 노드 뒤에만 생김
                //그래서 tail 를 넥스트 테일(새로운 노드)로 지정해줘야한다.
                this.tail = this.tail.next;
            }

        }
        public string Dequeue() //빼는 기능
        {   //head 꺼냄
            string result = this.head.data;
            //큐가 비어있는 경우
            if (this.head == null) {
                throw new ApplicationException("큐가 비어있습니다.");
            }
            //하나만 있을 경우 // 헤드가 테일
            if (this.head == this.tail)
            {
                //초기화
                this.head = null;
                this.tail = null;
            }
            else {
                //head를 빼고난 다음에 다음 노드를 헤드로 설정해는것
                this.head = this.head.next;
            }
            return result;

        }
    }
}