[자료구조] 스택(Stack)과 큐(Queue)(1)

1. 스택(Stack)

1-1. 스택(Stack)이란?

1-1-1) 스택의 기본 개념

• 스택이란 선형적 자료구조로 한쪽끝은 top, 다른쪽 끝은 bottom이라 부르며 추가적인 삽입과 삭제는 top에서만 가능한 자료구조 이다.
• 스택은 또한 LIFO(Last In First Out) 구조로, 가장 나중에 들어간 데이터가 제일 먼저 나가는 구조이다.
  

1-1-2) 시스템 스택(System Stack)

• 시스템 스택(system stack)은 운영체제가 사용하는 스택이다.

• 함수의 실행이 끝나면 자신을 호출한 함수로 되돌아가야 하는데 이 때 복귀할 주소를 기억하는 데 스택이 사용된다.(함수는 호출된 역순으로 되돌아가야 하기 때문)
  

  • 함수가 호출될 때마다 프로그램은 활성화 레코드 또는 스택 프레임이라고 하는 구조를 만들고 시스템 스택의 맨 위에 놓는다. 프레임 포인터(fp)는 현재 스택 프레임에 대한 포인터이며 시스템은 또한 스택 포인터(sp)를 별도로 유지 관리한다.

1-2. 코드로 보는 스택

1-2-1) C에서의 스택

• ADT로 보는 스택
  
• C에서 스택 생성은 1D 배열(1차원 배열)을 사용하여 스택을 나타내며 스택 요소는 스택[0]에서 스택[top]까지 저장된다.

스택 생성 함수 CreateS()
push() 함수
pop() 함수
stackFull() 함수
--	--

1-2-2) 동적 할당 배열을 사용하는 스택

CreateS() IsEmpty() IsFull()
pop() *안 바뀌고그대로
stackFull()

2. 큐(Queue)

2-1. 큐(Queue)란?

• 큐(Queue)는 선형 자료구조로 한쪽 끝은 front, 다른쪽 끝은 rear 라고 부르며 삽입은 오직 rear쪽에서만 가능하고 삭제는 front에서만 가능한 자료구조이다.
• 큐는 FIFO(First In First Out) 자료구조로 먼저 들어간 데이터가 먼저 나오는 순입순차의 구조를 갖고 있다.
  

2-2. 코드로 보는 큐

2-2-1) C에서의 큐

• ADT로 보는 큐
  
• 순차 표현은 스택과 마찬가지로 1D 배열을 사용하지만, 큐는 원형 표현(원형 큐)또한 가능한데 이때도 똑같이 1D 배열을 사용한다. 원형큐는 선형큐에 비해 효율성이 향상된다고 말할 수 있다.
  

큐 생성 함수 CreateQ()
addq() 함수
deleteq() 함수
addq(), deleteq() 예시

• 예시) OS의 Job Scheduling
  
• queueFull
  • array shifting : time-consuming, Worst case time complexity, O(MAX_QUEUE_SIZE)
    

2-2-2) 원형 큐

• 원형 큐(Circular Queue)는 1D 배열을 사용하는 큐로 원형 구조의 1D 배열을 사용한다.

일반적인 선형 큐(Linear Queue)	원형 큐(Circular Queue)

• front와 rear에는 정수 타입 변수를 사용한다.

  • front는 첫 번째 요소에서 시계 반대 방향으로 한 위치이다.
  • rear는 마지막 요소의 위치를 제공한다.
    

• 원형큐에 요소를 삽입할 때는 rear를 시계방향으로 한 번 이동 시키고 queue[rear]에 집어 넣는다.

• 원형큐에 요소를 삭제할 때는 front를 시계방향으로 한 번 이동 시키고 queue[rear]에서 제거한다.

*추가적으로 동적할당 스택, 큐 & array doubling 시간복잡도 재정리 필요

참조)

• https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95
• 자료구조, data structure, Horowitz, Shani, & Anderson-Freed, ªFundamentals of data structures in Cª, (2nd edition) Silicon-press. 강의자료 ppt