교수님이 7~10 스택큐 11~... 리스트 이런식으로 올려두시고 리스트가 더 먼저오는 대단원이었는데 리스트에서 스택큐 관련 언급을 하셔서 리스트를 하다가 스택큐를 먼저 하려고 넘어왔다! 리스트 내용은 추후 다시 추가할 것
2021/06/16 자료구조
Stack - stack-queue intro
Stack
데이터 나열되어 있는데 데이터를 삭제하거나, 삽입하는데에 top이라고 불리는 한 곳에서만 발생하는 것이 특징.
박스 안에 물건을 넣듯, 제일 첫번째 것 (0번째)가 가장 아래에 위치함.
맨 위에 있는 애 (n-1번째)가 top에 위치
후입선출(lifo)
ADT stack
Empty 스택 혹은 그 이상의 유한한 개수의 아이템들이 들어온 순서대로 저장
중요 operations
push
아이템을 집어 넣는 것
컴퓨터 메모리 한계가 있기 때문에 할당한 이상의 메모리를 집어넣을 순 없다. 여유가 있다면 top에 해당하게 메모리가 들어간다. top이라는 변수는 초기화할 때 왜 그 값으로 초기화 했는지에 대한 이유가 명확해야할 것. 
-> top값이 증가
pop
아이템을 빼내는 것
empty-> return, 하나 이상의 element가 존재하면 top에 있는 아이템을 빼낸다.
-> top값 감소
-> 표로 나타낸 출력 결과
Queue
데이터가 추가되는 위치와 빠져나가는 위치가 다르기 때문에 두 개의 변수, rear와 front.
가장 먼저 온 게 먼저 빠지고, 가장 나중에 온 게 마지막에 빠짐. 순서대로, 음식점에서 줄 서는 것. 선입 선출(fifo)
stack과 마찬가지로 데이터 구조는 저장하고자 하는 아이템들의 array라는 점이 같음.
데이터가 저장되는 모양은 같으나 응용에 따라
최근에 있는 것들을 먼저 뽑아야한다면 top이라는 변수를 사용하여 가장 최근에 저장된 데이터의 위치를 가리키게 하는 변수로만 작동시키는 것(stack 알고리즘)이고, 먼저 온 데이터가 먼저 나가야 하고, 나중에 들어온 데이터가 나중에 나가야되는 서비스라면 rear와 front라는 변수를 사용하여 관리를 함.(queue 알고리즘)
중요 operations
addQ (inQ)
rear: 가장 마지막에 저장된 데이터의 위치를 가리키고 있는지 알려주는 변수
rear값만 바뀜, 하나씩 뒤에 저장되기 때문.
-> rear 값 증가
deleteQ (dQ)
delete 일 때는 front와 rear가 같은 지를 비교함
왜? = 아이템이 있는데 rear는 맨 마지막 인덱스를 가리키고 있다고 가정했고, front 그보다 그 앞것을 가리키고 있고, 하나씩 빼낼 때마다 front 값은 뒤로 오게 됨. 결국 front와 rear가 같은 값을 가리키게 됨.
front 값만 바뀜.
-> front값 증가
-> 표로 나타낸 출력결과 
-> 원리 정리
앞에 공간이 남아있음에도 불구하고 새로운 아이템 추가 불가 - 현재 코드의 한계
circular queue
(현재 코드의 한계 보완 코드)
if (rear == MAX_QUEUE_SIZE-1)
rear = 0;
else
rear++;or
rear = (rear + 1) % MAX_QUEUE_SIZE -insert 연산 후 rear의 값
rear = (*rear +1) % MAX_QUEUE_SIZE ;
-delete 연산 후 front의 값
front = (front +1) % MAX_QUEUE_SIZE ;
-> rear가 배열의 끝까지 모두 찼다면 rear를 초기화 하여 비어있는 앞부분에 추가
rear == front는? Error
