데이터 구조 검토 요약 3장 스택 및 큐

3장 스택과 큐

스택

스택의 정의와 기본 동작

스택은 한쪽 끝으로만 제한됩니다. 삽입 및 삭제 작업의 선형 테이블은 후입선출 테이블(LIFO 테이블)이라고도 합니다. 삽입 및 삭제 끝을 스택의 맨 위라고 하고 다른 쪽 끝을 맨 아래라고 합니다. 스택. 테이블에 요소가 없으며 이를 빈 스택이라고 합니다. 기본 작업은 다음과 같습니다.

) initstack(s) 빈 스택을 구성합니다. p> ) stackempty(s)는 스택이 비어 있는지 확인합니다.

　 ) stackfull(s)은 스택이 가득 찼음을 확인합니다.

) push(s x) 스택에 푸시합니다.

) pop(들) 스택에서 팝

) stacktop(s) 스택의 최상위 요소 가져오기

시퀀스 스택

스택의 순차 저장 구조를 순차 스택이라고 합니다. 순차 스택의 유형은

　#define stacksize

typedef char datatype; p> typedef struct{

datatype data[stacksize];

int top;

}seqstack; full 작업은 필연적으로 오버플로라고 하는 공간 오버플로를 생성합니다. 스택이 비어 있으면 팝업 작업은 필연적으로 언더플로라고 하는 공간 오버플로를 생성하므로 피해야 합니다. 프로그램 제어 전송을 위한 조건으로 자주 사용됩니다.

순서대로 스택의 기본 작업

) 스택 비우기

Void initstack(seqstack *s)

{

s >top= ;

　}

　) 스택이 비어 있는지 확인

int stackempty(seqstack * s)

>top== ;

}

) 스택이 가득 찼는지 확인

int stackfull(seqstack *s)

{

Return s >top==stacksize;

}

) 스택에 푸시

Void push( seqstack *s 데이터 유형 x)

　{

　if(stackfull(s))

　error( 스택 오버플로 )

　s > data[++s >top]=x;

　}

　 ) 스택 팝

　데이터 유형 pop(seqstack *s)

　{

　if(stackempty (s))

error( 스택 언더플로우 )

return S >data[s >top ];

}

) 스택의 최상위 요소 가져오기

Dtatatype stacktop(seqstack *s)

{

if( stackempty(s))

오류(스택 언더플로우)

return S >data[s >top]

}

체인 스택

스택의 체인 저장 구조 체인 스택의 최상위 포인터는 연결 목록의 헤드 포인터라고 합니다. 체인 스택의 유형 정의

typedef struct stacknode{

데이터 유형

struct stacknode *next

typedef struct{

stacknode *top;

}linkstack;

링크 스택의 기본 작업

) 스택 구축

Void initstack( linkstack *s)

　{

　s >top=NULL

　}

　 ) 스택이 비어 있는지 확인

Int stackempty (linkstack *s)

{

return s >top==NULL

}

) 스택에 푸시

Void push(linkstack *s 데이터 유형 x)

{

stacknode *p=(stacknode *)malloc(sizeof(stacknode))

p >data=x;

p >next=s >top;

s >top=p;

　 ) 팝

　데이터 유형 pop(linksatck *s)

　{

　데이터 유형 x

　stacknode *p=s > 상단;

if(stackempty(s))

error(스택 언더플로우)

x=p >data; >top=p >next;

free(p);

return x;

}

) 스택

데이터 유형 stacktop(linkstack *s)

{

if(stackempty(s))

error( 스택이 비어 있음 );

return s >top >data;

}

대기열

대기열의 기본 정의 및 계산

큐 제한된 작업을 수행하는 선형 테이블입니다. 삭제가 허용되는 끝을 큐의 헤드라고 하며, 삽입이 허용되는 끝을 큐의 꼬리라고 합니다. , FIFO 테이블

대기열의 기본 작업

　 ) initqueue(q)는 대기열을 비워 둡니다.

) queueempty(q) 대기열이 비어 있다고 판단합니다.

　 ) queuefull(q) 대기열이 가득 찼다고 판단합니다.

) enqueue(q p>

대기열의 순차적 저장 구조를 호출합니다. 순차 큐의 앞 포인터와 뒤 포인터는 벡터 공간에서 큐의 헤드 및 테일 요소의 위치를 ​​나타냅니다. 순차 큐에서는 인큐 및 디큐 작업이 헤드 및 테일 포인터만 만들기 때문에 잘못된 오버플로 현상이 발생합니다. 공간이 증가하지만 감소하지 않으면 삭제된 요소의 공간을 사용할 수 없습니다. tail 포인터가 벡터 공간의 상한을 초과하여 큐에 추가할 수 없습니다.

거짓 오버플로 현상을 극복하기 위해 , 벡터 공간을 끝과 끝이 연결된 루프로 상상해 보세요.

링 벡터가 저장된 큐를 순환 큐라고 합니다. i=(i+)%queuesize

front==rear를 사용하여 큐가 비어 있는지 또는 꽉 찼는지 확인할 수 없으므로 경계 조건 처리 순환 대기열의 문제는

p>

로 해결됩니다. ) 빈 대기열과 가득 찬 대기열을 구별하기 위해 또 다른 부울 변수를 설정합니다.

) 뒤쪽 플러스 여부를 테스트하려면 요소를 하나 적게 사용합니다. 루프 의미에서 front는 큐에 추가하기 전의 front와 같습니다.

) 카운터를 사용하여 총 요소 수를 기록합니다.

순환 큐의 유형 정의

#define queuesize

typedef char 데이터 유형

typedef struct{

int front

int Rear; >

int count;

datatype data[queuesize];

}cirqueue;

) Void initqueue(cirqueue *q)

{

q > front=q >rear= ;

q >count=

}

) 비어 있음

Int queueempty(cirqueue * q)

　{

return q >count==

　}

　 ) 팀이 꽉 찼습니다

Int queuefull(cirqueue *q)

{

return q >count==queuesize