스 택 과 대기 열

순서 창고 의 조작

체인 스 택 기본 조작

예 3 - 1 괄호 가 일치 하 는 지 판단

계산 접미사 표현 식

순환 대기 열

체인 팀 의 조작

순차 스 택 작업
top 포인터 로 스 택 상단 요 소 를 가리 키 며 - 1 로 초기 화 합 니 다.창고 에 들 어 갈 때 바늘 을 이동 해서 값 을 부여 하기;창 고 를 나 갈 때 값 을 추출 하고 바늘 이동 하기;

const int maxn = 1000;
int Stack[maxn], top = -1;//top      ，       ，  -1
int push(int x){
     //if stack is full
     if(top == maxn - 1) return 1;
     Stack[++top] = x;//first move top, then assign
     return 0;
}
int pop(int &x){
     //if Stack is empty
     if(top == -1) return 1;
     x = Stack[top--];//first assign, then top--
     return 0;
}
int isEmpty(){
     if(top == -1) return 1;
     else return 0;
}

체인 스 택 기본 조작
앞장 서 는 노드 의 링크 로 이 루어 집 니 다. 헤드 삽입 법 을 사용 하여 삭제 할 때 첫 번 째 요 소 를 삭제 합 니 다.

const int maxn = 1000;
//define of node
typedef struct LNode{
     int data;
     struct LNode *next;
}LNode;

LNode *lst;
//be same with head insert
void push(LNode *lst, int x){
     LNode *p;
     p = (LNode *)malloc(sizeof(LNode));
     p->data = x;
     p->next = lst->next;
     lst->next = p;
}
int pop(LNode *lst){
     LNode *p;
     if(lst->next == NULL) return 0;
     p = lst->next;
     lst->next = p->next;
     free(p);
     return 1;
}
int isEmpty(LNode *lst){
     if(lst->next == NULL) return 0;
     else return 1;
}

void show(LNode *lst){
     lst = lst->next;
     while(lst != NULL){
          printf("%d ", lst->data);
          lst = lst->next;
     }
     printf("
");
}

int main()
{
     //initialize stack
     lst = (LNode *)malloc(sizeof(LNode));
     lst->next = NULL;
     push(lst, 2);
     push(lst, 1);
     show(lst);
     pop(lst);
     show(lst);
     return 0;
}

예 3 - 1 괄호 일치 여부 판단
왼쪽 괄호 를 만 나 서 바로 창고 에 들 어가 고 오른쪽 괄호 를 만 나 서 창고 에 왼쪽 괄호 가 있 는 지 없 는 지 판단 하고 어떤 것 은 창고 에서 나온다.마지막 으로 스 택 이 비어 있 지 않 으 면 왼쪽 괄호 가 남아 있 고 일치 하지 않 는 다 는 것 을 설명 합 니 다. 그렇지 않 으 면 일치 합 니 다.

int match(char exp[], int n){
     char Stack[maxn];
     int top = -1;
     for(int i = 0; i < n; i ++){
          if(exp[i] == '(') Stack[++top] = '(';//if char equal '(', push
          else if(exp[i] == ')'){
               if(top != -1) top --;//determine if there is '('
               else return 0;
          }
     }
     //Determine if there is any excess '('
     if(top == -1) return 1;
     else return 0;
}

계산 접미사 식
숫자 가 스 택 에 직접 들 어가 면 조작 자 를 만 나 두 번 의 스 택 꼭대기 요 소 를 연산 한 후에 결 과 를 다시 스 택 에 넣 습 니 다.

const int maxn = 1000;
int op(int a, char Op, int b){
     if(Op == '+') return a + b;
     else if(Op == '-') return a - b;
     else if(Op == '*') return a * b;
     else if(Op == '/'){
          //Handle exceptions with a zero denominator
          if(b == 0){
               cout << "ERROE" << endl;
               return 0;
          }
          else return a / b;
     }
     return 0;
}

int com(char exp[]){
     int a, b, c;
     int Stack[maxn], top = -1;
     for(int i = 0; exp[i] != '\0'; i ++){
          //deal cases that exp[i] is number
          if(exp[i] >= '0' &&exp[i] <= '9'){
               Stack[++top] = exp[i] - '0';
          }
          else{
               b = Stack[top--], a = Stack[top--];
               c = op(a, exp[i], b);
               Stack[++top] = c;
          }
     }
     return Stack[top];
}

void transToBehind(char s[], char exp[]){
     char Stack[maxn];
     int top = -1, j = 0;
     for(int i = 0; exp[i] != '\0'; i ++){
          if(exp[i] >= '0' && exp[i] <= '9'){
               s[j++] = exp[i];
          }
          else{
               while(compare(exp[i], Stack[top]) == 1){
                    s[j++] = Stack[top--];
               }
               
          }
     }
}

순환 대기 열
rear 는 마지막 요 소 를 가리 키 고 front 는 첫 번 째 요소 의 앞 위 치 를 가리 키 며 항상 빈 요 소 를 가리 키 며 구역 이 꽉 차고 빈 두 가지 상황 을 가리킨다.

int push(int x){
     if((rear + 1) % maxn == frontt) return 0;
     rear = (rear + 1) % maxn;
     Queue[rear] = x;
     return 1;
}

int pop(){
     if(rear == frontt) return 0;
     frontt = (frontt + 1) % maxn;
}

체인 조작
삽입 용 꼬리 삽입 법, 토론 대기 열 이 비어 있 는 지 없 는 지, 빈 머리 지침 도 업데이트 해 야 합 니 다. 그렇지 않 으 면 꼬리 지침 만 업데이트 해 야 합 니 다.팀 을 나 갈 때 먼저 대기 열 에 요소 가 있 는 지 판단 하고 하나의 요소 와 여러 요소 로 나 뉘 며 하나의 요소 가 있 을 때 꼬리 포인터 도 업데이트 해 야 합 니 다. 그렇지 않 으 면 헤드 포인터 만 업데이트 해 야 합 니 다.

const int maxn = 100;
//define of node
typedef struct QNode{
     int data;
     struct QNode *next;
}QNode;
//define of head
typedef struct{
     QNode *Front, *rear;
}LiQueue;

LiQueue *lqu;
//insert into tail
void enQueue(LiQueue *lqu, int x){
     QNode *p;
     p = (QNode)malloc(sizeof(QNode));
     p->data = x, p->next = NULL;
     //There are two cases based on whether the queue is empty or not
     if(lqu->rear == NULL) lqu->rear = lqu->Front = p;
     else{
          lqu->rear->next = p;
          lqu->rear = p;
     }
}

int deQueue(LiQueue *lqu){
     QNode *p;
     //deal with case that queue is empty
     if(lqu->Front == NULL) return 0;
     else p = lqu->Front;
     //there are two cases based on whether queue have one or multi elem 
     if(lqu->Front == lqu->rear) {
          lqu->Front = lqu->rear = NULL;
     }
     else {
          lqu->Front = p->next;
     }
     free(p);
     return 1;
}

int main()
{
     lqu = (LiQueue)malloc(sizeof(LiQueue));
     lqu->Front = lqu->rear = NULL;
     return 0;
}

스 택 과 대기 열

좋은 웹페이지 즐겨찾기