자료구조 기초 스텍 & 큐

자료구조를 왜 배울까?

---

자료구조란? 자료구조는 자료(데이터)를 다루는 구조 그 자체를 뜻한다. 즉 자료를 어떤 순서로 다룰 것인지에 대한 설계도라고 이해하면 쉽다.

 

목적: 원하는 데이터를 쉽게 찾기 위해서 만약 [1,2,3,4,....10000]중에서 원하는 데이터를 찾아 처리를 해야 한다고 한다면?? 당신은 어떤 방식을 쓰겠는가? 에 대한 물음이라는 생각.

 

 

 

스택(first in last out)

---

스택의 사전적 의미는 쌓다. 쌓았기 때문에 처음에 들어가기는 쉽지만 나오기 위해서는 마지막으로 나가야 함.

ex) 1차선에 차들이 들어섰을 때 첫번째 차량은 먼저 들어갈 수 있지만 나가고 싶을 때는 마지막으로 나가는 구조.

 

생각해보기 
1. 데이터가 만들어진다 객체에 순서를 만들어준다. 
2. 그에 따라 속성이 하나씩 증가하여 데이터의 위치를 알려준다.
3. 마지막 top 속성에 -1 를 하면 속성의 key를 찾을 수 있다.

 

 

 

 

//강의 목적 스택의 이해 : 원리 데이터가 처음 저장되면 첫 번째 공간에 저장되고 빠져나갈 때는 최신게 빠져나간다. 
//예시로는 앞으로 가기 뒤로 가기

// 스택의 구성은 다음과 같다.

// 1.class 변수의 선언
	// 객체의 형태로 선언
	// 속성은 숫자로 표현될 예정 그럼 어떤 데이터 속성인지 찾기 위해서는 그거를 가리키는 point 변수가 필요
class Stack{

	// 1.class 변수의 선언
	constructor(){
		// 객체의 형태로 선언

		this.storage={}
		// 속성은 숫자로 표현될 예정 그럼 어떤 데이터 속성인지 찾기 위해서는 그거를 가리키는 point 변수가 필요
		this.top = 0
	}
	// 맨 뒤쪽을 빼야하는 push() 함수 선언
    push(el){
			// 속성에는 포인터를 가리키는 point 변수를 넣어주고 속성값에는 넣고싶은 데이터 el 를 넣어준다.
			this.storage[this.top]=el
			this.top++
	   		// 그리고나서 point의 수 즉 속성 값이 달라져야 한다.
	}

   /*
   {o, '가',             top =  1    ===> push 함수가 발생할 때마다 두 가지 사건이 발생 객체 속성의 생성, top 변수의 값이 1 증가.
    1,  '나',            top  = 2
    2,  '다',            top  = 3

	}
    => 객체의 속성과 top은 1씩 차이가 남.
	*/
	


    //맨 뒤쪽부터 빼야하는 pop() 함수 선언
	pop(){
		// 만약에 객체가 비었다면 함수 종료. 
		if(Object.keys(this.storage).length===0){
			return //단순 함수의 종료 
		}
	  // 그렇지 않다면 top-1 번째 객체 삭제.
	    else{
			//그렇지 않으면
			// 마지막 속성의 값을 추출하여 return
			let result=this.storage[this.top-1]
			
			// top-1 번째 객체 삭제.
			delete this.storage[this.top-1]
			 //  top 의 변수를 마이너스 하기.
			return result

			}
	  //  top 의 변수를 마이너스 하기.



	}

	// stack의 사이즈 구하기 

	size(){


		return this.top
	}



}

const result_stack=new Stack()

for(let i=0; i<10; i++){

	result_stack.push(i)
}

console.log(result_stack.size())
console.log(result_stack.pop())

 

 

큐(first in first out)

---

큐의 사전적 의미 줄을 서서 기다리다 대기 행렬이라는 의미로 처음에 들어온 차량은 당연히 제일 먼저 나갈 수 있다. 

ex) 사람이 프린트 이벤트를 발생했을 때 프린트 출력장치를 처리하려면 처음 페이지부터 해석이 되고 출력이 되어야함. 

 

 

생각해보기

why? 큐라는 데이터 구조가 필요할까? cpu는 다른 장치에 비해 규칙적이고 일정한 처리속도를 가지고 있기 때문에 cpu가 데이터를 처리한 후 que로 데이터를 저장한다. 그리고 이를 저장장치들이 받아서 처리하는 구조.

Why? 왜 변수가 front rear로 두개가 필요할까?  rear 로 속성의 번호는 늘어나지만 이걸로는 que의 pop의 행동을 취할 때 첫 번째 포인터가 아니라 마지막 포인터이기 때문에 두 개가 필요하다 

 

엑셀로 이해하기 

---

	빈객체	front	rear	데이터의 길이
	{}	0	0	0
데이터를 넣기	{1:”가”}	0	1	1
데이터를 넣기	{1:”가”, 2:”가”}	0	2	2
데이터 빼기	{1:”가”}	1	2	1
데이터 빼기	{}	2	2	0

코드

---

class Queue{

	//변수를 선언해준다. 
	  // 기본 객체
	  // front 
	  // rear

	constructor(){

		this.storage={}
		this.rear=0
		this.front=0
	}

	//size check

	size(){

		return this.rear-this.front
	}



	//push
    push(el){
		//빈 객체에 rear번째 속성에 el를 넣어준다
		// 그리고 rear 에 1을 더한다

		this.storage[this.rear]=el
		this.rear++

	}


	//pop

	pop(){
		//만약 빈 데이터의 길이가 0이면(빈 객체) undefiend return 
          if(this.rear-this.front===0){
			  return
		  }else{
				// 그렇지 않으면
						//새로운 변수에 front번째 속성값을 담고 
               const result= this.storage[this.front]     
			           //front 번째 제거
			   delete this.storage[this.front]    
			   
						//front에 1을 더하여 새로운 첫 번째를 맞이할 준비를 하자
			   this.front++

			   return result
		  }
       

	}









}



const queue = new Queue

for(let i=1; i<=10; i++){
	queue.push(i)
}

console.log(queue.size())
console.log(queue.pop())



//