《数据结构高分笔记》栈和队列

ゞ浴缸里的玫瑰 2024-05-08 06:05 63阅读 0赞

#### 目录 ####

*   *   *   *  顺序栈的操作
             *  链栈基本操作
             *  例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("\n");
    }
    
    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;
    }