'데이터 구조 (스 택 과 대기 열 편) 를 쉽게 해결 합 니 다.

데이터 구조 (스 택 과 대기 열)

데이터 구조 (스 택 과 대기 열)

창고

순차 스 택

체인 스 택 (머리 결산 점 을 대표 하지 않 음)

순서 스 택 과 체인 스 택 의 비교

대열

순서 대기 열 - 순환 대기 열

순서 대기 열 - 비 순환 대기 열

체인 대기 열 - 비 순환 대기 열

응용

재 귀 와 서브루틴 호출 문제

표현 식 값 구하 기

이 진 트 리 의 옮 겨 다 니 기 (재 귀 비 재 귀 전환)

창고.
순서 창고

//  
typedef struct  SeqStack{
    int stack[MAXSIZE];
    int top;
}SeqStack;
//      
void initStack(SeqStack &seq){
    seq.top =-1;
}
//     
void clearStack(SeqStack &seq){
    seq.top = -1;
}
//  
void push(SeqStack &seq,int data){
    if (seq.top < MAXSIZE-1) {
        seq.stack[++seq.top] = data;
    }
    else{
        PerException("the stack is full");
    }
}
//  
int pop(SeqStack &seq){
    int data = 0;
    if (seq.top > -1) {
        data = seq.stack[seq.top--];
    }else{
        PerException("the stack is empty");
    }
    return data;
}
//      
int getTop(SeqStack seq){
    if (seq.top == -1) {
        PerException("the stack is empty");
    }
    return seq.stack[seq.top];
}
//     
int length(SeqStack seq){
    return seq.top+1;
}
//     
bool isEmpty(SeqStack seq){
    if (seq.top == -1) {
        return true;
    }else{
        return false;
    }
}
//     
bool isFull(SeqStack seq){
    if (seq.top == MAXSIZE -1) {
        return true;
    }else{
        return false;
    }
}
//    
int main(){
    SeqStack seq ;
    initStack(seq);
    push(seq, 3);
    push(seq, 7);
    push(seq, 9);
    push(seq, 13);
    cout<cout<cout<cout<cout<return 0;
}

체인 스 택 (헤드 노드 는 아 닙 니 다)

//      (     ，   )
//N->H->d->b->c->R
typedef struct LSNode{
    int data;
    LSNode* next;
}LSNode ,*LinkStack;

//      
void initStack(LinkStack &top){
    top =nullptr;
}
//     
void clearStack(LinkStack &top){
    while (top != nullptr) {
        LSNode* p =top;
        top = top->next;
        delete p;
    }
}
//  
void push(LinkStack &top,int data){
    LSNode*p = new LSNode{data,top};
    top = p;
}
//  
int pop(LinkStack &top){
    if (top == nullptr) {
        PerException("the stack is empty");
    }
    int res = 0;
    LSNode* p = top;
    top = top->next;
    res = p->data;
    return res;
}
//      
int getTop(LinkStack top){
    if (top == nullptr) {
        PerException("the stack is empty");
    }
    return top->data;
}
//     
int length(LinkStack top){
    int count =0;
    LSNode* p =top;
    while (p!=nullptr) {
        p = p->next;
        count++;
    }
    return count;
}
//     
bool isEmpty(LinkStack top){
    if (top == nullptr) {
        return true;
    }
    return false;
}
//     
bool isFull(LinkStack top){
    return false;
}
//    
int main(){
    LinkStack top;
    initStack(top);
    cout<" ";
    push(top, 32);
    push(top, 2);
    push(top, 3);
    cout<" ";
    cout<" ";
    cout<" " ;
    cout<cout<return 0;
}

순서 스 택 과 체인 스 택 의 비교
순서 역 과 체인 전 을 실현 하 는 모든 기본 조작 알고리즘 은 상수 시간 만 필요 하기 때문에 유일 하 게 공간 성능 을 비교 할 수 있다.초기 에 순서 스 택 은 고정된 길 이 를 정 해 야 하기 때문에 요소 의 개 수 를 저장 하 는 제한 과 공간 낭비 문제 가 있 습 니 다.체인 스 택 에 스 택 이 가득 찬 문제 가 없습니다. 메모리 에 사용 가능 한 공간 이 없 을 때 만 스 택 이 가득 합 니 다. 그러나 모든 요 소 는 하나의 포인터 필드 가 필요 해서 구조 적 인 비용 이 발생 합 니 다.따라서 스 택 의 사용 과정 에서 요소 의 개수 변화 가 비교적 클 때 체인 스 택 을 사용 하 는 것 이 적당 하 다.반대로 순서 창 고 를 채택 해 야 한다.
대열
순서 대기 열 - 순환 대기 열

//             
//1      2   3   (       )
//      
typedef struct CQueue{
    int* queue;
    int front;
    int rear;
    int length;

}CQueue;
//        
void initQueue(CQueue &cQueue){
    cQueue.queue = new int[MAXSIZE];
    cQueue.front =0;
    cQueue.rear =0;
    cQueue.length =0;
}
//      
void clearQueue(CQueue &cQueue){
    for (int i=0; iqueue[i] =0;
    }
    cQueue.front=0;
    cQueue.rear =0;
    cQueue.length =0;
}
//      
bool enQueue(CQueue &cQueue ,int data){
    if (cQueue.length == MAXSIZE) {
        PerException("the queue is full");
    }
    cQueue.front = cQueue.front == MAXSIZE ? 0:cQueue.front;
    cQueue.queue[cQueue.front++]=data;
    cQueue.length++;
    return true;
}
//      
int DeQueue(CQueue &cQueue){
    if (cQueue.length == 0) {
        PerException("the queue is empty");
    }
    cQueue.rear = cQueue.rear == MAXSIZE ? 0:cQueue.rear;
    int data = cQueue.queue[cQueue.rear++];
    cQueue.length--;
    return data;
}
//      
int length(CQueue cQueue){
    return cQueue.length;
}
//      
bool isEmpty(CQueue cQueue){
    return cQueue.length == 0? true:false;
}
//      
bool isFull( CQueue cQueue){
    return cQueue.length ==MAXSIZE?true:false;
}
//    
int main(){
    CQueue cQueue;
    initQueue(cQueue);
    enQueue(cQueue, 1);
    enQueue(cQueue, 2);
    enQueue(cQueue, 3);
    enQueue(cQueue, 4);
    enQueue(cQueue, 5);
    //    enQueue(cQueue, 6);
    cout<" ";
    cout<" ";
    cout<" ";
    enQueue(cQueue, 6);
    cout<" ";
    cout<" ";
    clearQueue(cQueue);
    cout<" ";
    return 0;
}

순서 대기 열 - 비 순환 대기 열

//      
typedef struct CQueue{
    //c++   c   realloc           ，
    //     vector  ，     。
    //           ，     。
    //    
    vector<int> queue;
}CQueue;
//        
void initQueue(CQueue &cQueue){
}
//      
void clearQueue(CQueue &cQueue){
    cQueue.queue.clear();
}
//      
bool enQueue(CQueue &cQueue ,int data){
    //    cQueue.front++;
    cQueue.queue.push_back(data);
    return true;
}
//      
int DeQueue(CQueue &cQueue){
    int data = cQueue.queue.front();
    cQueue.queue.erase(cQueue.queue.begin());
    return data;
}
//      
int length(CQueue cQueue){
    return (int)cQueue.queue.size();
}
//      
bool isEmpty(CQueue cQueue){
    return cQueue.queue.size() == 0? true:false;
}
//      
bool isFull( CQueue cQueue){
    return false;
}
//    
int main(){
    CQueue cQueue;
    initQueue(cQueue);
    enQueue(cQueue, 1);
    enQueue(cQueue, 2);
    enQueue(cQueue, 3);
    enQueue(cQueue, 4);
    enQueue(cQueue, 5);
    //    enQueue(cQueue, 6);
    cout<" ";
    cout<" ";
    cout<" ";
    enQueue(cQueue, 6);
    cout<" ";
    cout<" ";
    clearQueue(cQueue);
    cout<" ";
    return 0;
}

체인 대기 열 - 비 순환 대기 열

//    H->a->b->c->N
//           ,        
//  
typedef struct LQNode
{   int data;
    LQNode * next;
} LQNode;

typedef struct LinkQueue
{   LQNode  *front;
    LQNode  *rear;
} LinkQueue;

//       
void initQueue(LinkQueue &queueLink){
    LQNode* q = new LQNode;
    q->next =nullptr;
    queueLink.front =q;
    queueLink.rear =q;
}
//      ：  ClearQueue(&Q)
void clearQueue(LinkQueue &queueLink){
    while(queueLink.front != queueLink.rear){
        LQNode* p = queueLink.front;
        queueLink.front  =p->next;
        delete p;
    }
}
//      ：  EnQueue (&Q, x)
void enQueue(LinkQueue &queueLink,int data){
    LQNode* p = new LQNode{data,nullptr};
    LQNode* q  = queueLink.rear;
    q->next =p;
    queueLink.rear = p;
}
//      ：  DeQueue(&Q, &x)
bool deQueue(LinkQueue &queueLink){
    if (queueLink.front == queueLink.rear) {
        PerException("the queue is empty");
    }
    LQNode* p = queueLink.front;
    LQNode* q = p->next;
    p->next = q->next;
    delete q;
    return true;
}
//     ：  QueueLength(Q)
int length(LinkQueue queueLink){
    LQNode* p = queueLink.front;
    int count = 0;
    while (p->next != nullptr) {
        p=p->next;
        count++;
    }
    return count;
}
//      ：boolean QueueEmpty( Q )
bool isEmpty(LinkQueue queueLink){
    return queueLink.front == queueLink.rear ? true:false;
}
//      ：boolean QueueFull( Q )
bool isfull(LinkQueue queueLink){
    return false;
}
//    
int main(){
    LinkQueue queueLink;
    initQueue(queueLink);
    cout<<"isEmpty:"<1);
    enQueue(queueLink, 2);
    enQueue(queueLink, 3);
    enQueue(queueLink, 4);
    cout<<"length:"<cout<<"dequeue:"<cout<<"length:"<cout<<"isEmpty:"<cout<<"isEmpty:"<5);
    cout<<"length:"<return 0;
}

활용 단어 참조
질문
재 귀 와 서브루틴 의 호출 은 모두 시스템 이 스 택 에 있 습 니 다. 매번 재 귀 프로그램 을 호출 할 때마다 시스템 은 이 함수 의 모든 정보 (줄 번호, 함수 명, 매개 변수, 다음 함수 이전의 모든 데 이 터 를 호출 합 니 다) 를 스 택 에 누 릅 니 다.
표현 식 값 구하 기
글 참고:https://blog.csdn.net/opooc/article/details/81188065
이 진 트 리 의 옮 겨 다 니 기 (재 귀적 이지 않 은 변환)
글 참고:https://blog.csdn.net/opooc/article/details/81187855