3,4주차 -stack queue

수강일시 : 2020.09~ 2020.12

출처:  고려대학교 정연돈 교수님 자료구조 강의

 

stack이란 아래서부터 쌓고 마지막으로 쌓은것부터 꺼내는 방식의 자료구조.

Stack 의 ADT

작동예시

push(green)

push(blue)

Pop()

push(red)

 

array 를 이용하여 stack 을 구현한다면

초기에 stack의 최대 갯수를 stacksize로 정의하고

int stack[stacksize]; 로 선언한다.

int top=-1;으로 초기화하고

 

void push(int arr[],int data,int top)

{

 arr[++top]=data;

}

 

int pop(int arr[])

{

 return arr[top--];

}

 

등과 같은 방법으로 구현한다.

 

하지만 여기서 단점은 stack의 size가 정해지므로 정해진 stacksize를 초과하는 데이터를 저장할 수 없고 array를 선언할 때 generic하게 선언할 수 없다는것이 단점이 된다. 따라서 링크드리스트를 이용해 작성한다면 이러한 단점을 극복할 수 있다.

 

 

 

 

Queue는 stack과 다르게 먼저 들어온 자료가 먼저 나가는 방식이다.

 

Queue의 ADT는 다음과 같다.

queue또한 stack과 마찬가지로 array와 list를 이용하여 구현할 수 있다.

 

array로 구현하는 queue의 단점도 stack에서와 마찬가지로 정해진 값을 초과할 수 없고 generic한 queue를 만들 수 없다는것이다.

 

거기에 더해 queue의 경우 데이터를 삽입 삭제(enqueue dequeue)하다보면 계속 이동하게 되므로 front가 rear와 가까이 이동해서 사용하면 할수록 점점 가용범위가 줄어드는 추가적인 단점이 발생한다.

 

이러한 단점을 queue에서는 circular queue를 만듦으로서 해소할 수 있다.

 

 

따라서 stack과 queue모두 일반적인 쓰임새에서는 list를 통해 구현해야 하지만

1.자료형이 정해져있고

2.사용환경이 제한적이어서 stack 과 queue의 갯수가 정해져있는경우

두가지를 모두 충족하는 경우 array를 통해 구현할 수 있다.