Stack, Queue, Linked List

1. stack

Stack 지료구조

 

1. 데이터를 한쪽 끝에서만 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 선형 자료형이다.
2. 스택의 연산 
   
   • pop() : 스택 가장 위의 항목 제거 
   • push(item) : item 하나를 스택의 가장 윗부분에 추가한다.
   • peek() : 스택의 가장 위에 있는 항목을 반환한다.
3. 스택의 특징
   • 배열과 달리 스택은 상수 시간에 i 번째에 접근할 수 없다.
   • 데이터 추가 삭제 연산에서는 상수 시간에 접근이 가능하다.
4. Pseudo Code
   1. Stack 함수를 생성 
   2. 데이터를 담을 배열을 생성 
   3. 배열 마지막에 값을 추가하는 함수를 만든다. (push)
   4. 배열 마지막에 값을 제거하는 함수를 만든다. (pop)
   5. 배열 마지막 값을 반환하는 함수를 만든다. (peek)

2. Queue      

1. 앞부분부터 삭제가 되고 끝 부분부터 데이터가 입력되는 선입선출 FIFO (Firest In First Out) 구조이다.
2. tree의 깊이 우선 탐색이나 sliding window 등 주로 순서 처리의 시스템에 쓰인다.
3. 큐의 연산
   • enqueue() : 큐에 요소를 추가(끝 부분 / push)
   • dequeue() : 큐에서 요소를 삭제 (첫 부분 / shift)
   • front() : 큐의 앞부분에 저장된 요소 반환
   • back() : 큐의 끝 부분에 저장된 요소 반환 
4. Psuedo Code
   1. Queue 함수를 생성
   2. 배열을 생성 
   3. 배열의 끝부분에 요소를 추가하는 함수를 만든다. (push)
   4. 배열의 첫 부분을 제거하는 요소를 만든다. (shift)
   5. 배열의 첫 부분에 저장된 요소 반환 하는 함수를 만든다.(front)

 

3. Linked List

Node 는 마디, 거점이란 뜻이고 Vertex는 정점, 꼭짓점이라고 하는데  둘 다 연결이란 의미를 가지고 있다고 말할 수 있다.

즉 사각현으로 묶여진 부분이 하나의 노드라고 할 수 있고 위의 그림에선 4개의 노드가 존재하고 있다. 

 

노드 안에는 2개의 필드(변수)가 있다.

1. Data field : 저장되는 실제 값
2. Linked field : 다음 구성 요소(노드)를 가지고 있다.

Linked list는 순서가 있는 데이터 조합으로 이것을 이용하기 위해서는 첫 번째 노드가 무엇인가를 알 수 있어야 한다. 왜냐하면 첫 번째 노드를 찾아서 링크필드를 이용하여 다음 코드들을 찾아갈수 있기 때문이다. 즉 첫번째 노드가 무엇인지를 의미하는 정보를 HEAD 필드에 적는다 이 필드도 변수이고 첫번째 값이 무엇인가를 가리키고 있다. 

 

Linked list 특징

• 인풋사이즈를 모를 때 메모리 할당 효율이 좋다.
• 데이터 하나당 추가적으로 소모되는 메모리 양이 (Array List)보다 많다.
• 중간 데이터 추가,삭제의 효율성이 좋다.

Pseudo Code

현재 자신의 값과 다음 노드(변수)의 값을 가지고 있는 노드(변수)를 생성하는 생성자 함수를 만든다.

 

노드를 앞에 추가하는 함수 

1. 생성자 함수로 추가할 값을 가진 노드를 만든다.
2. 생성된 노드의 linked filed에 head 값을 할당 해준다.
3. head 값에 생성된 노드를 할당 해준다.

노드의 중간에 값을 추가하는 함수

1. 헤드 즉 첫번째 값을 담을 변수를 만들고 첫번째 값을 변수에 할당한다.
2. 추가하려고 하는 자리값을 빼주어서 0이 아닐때 까지 돌아가는 while문을 만든다.
3. 와일문이 돌아 갈때마다 첫번째 값을 담은 변수에 다음 노드값을 할당 해준다.
4. 와일문이 종료된 뒤 첫번째 값을 담은 변수의 다음 노드값을 참조 하는 새로운 변수를 만들어 준다.
5. 새로운 값이 들어갈 변수를 만들어 준다.
6. 헤드값의 linked filed에 새로운 값이 들어간 변수를 할당해준다.
7. 새로운 값이 들어간 변수의 linked filed에 헤드값의 다음 노드값을 참조하는 변수를 할당해 준다.

노드의 값을 삭제하는 함수

1. 헤드값을 가진 변수 curr을 만든다.
2. 삭제하려는 자리값을 빼주어서 0이 아닐때 까지 돌아가는 while문을 만든다.
3. 와일문이 종료될 때 까지 curr에 헤드값 다음의 변수를 할당해준다.
4. curr의 linked filed 값(즉 curr의 다음 노드 값)을 가진 delete를 만든다.
5. curr의 linked filed에 curr의 다음다음 값을 할당 해준다.
6. delete를 삭제한다.