棧和隊列

棧

棧的存儲結構：

順序棧

typedef struct SqStack
{
    int data[maxSize];
    int top;
}SqStack;
           

鍊式棧

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;
           

::棧的本質是線性表::,和線性表的定義方式完全一樣！

順序棧

四要素：兩狀态+兩操作

• 幾個狀态
  1. 空棧：st.top == -1//top 代表棧頂元素的index
  2. 滿棧：st.top == maxSize-1
  3. 非法上下溢
• 兩個基本操作
  1. 進棧：先移動指針，再進入元素

1. 出棧：先取出元素，後移動指針

::用前先判斷，空時不出，滿時不進！::

鍊棧

四要素：兩狀态+兩操作

• 兩個狀态
  1. 空棧：lst->next == NULL
  2. 滿棧：不存在這種情況
• 兩個基本操作

  1. 進棧：頭插法

     ::頭結點原來是指向的棧頂啊！！！::

  2. 出棧：出棧元素儲存到x中

p = lst->next;
x = p->data;
lst->next = p->next;
free(p);
           

::考試不用寫棧的函數，直接寫必要的語句！::

習題

1. 編寫算法，判斷一個表達式中括号是否真确配對，表達式個數為n

int match(char exp[], int n){
    //初始化棧
    char stack[maxSize];
    int top = -;

    for(int i = ; i < n; ++i){
        if(exp[i] == '(')
        stack[++top] = '(';
        if(exp[i] == ')'){
            if(top == -)
            return ;
            else 
            --top;
        }
    }
    if(top == -)
    return ;
    else
    return ;
}
           

::棧中隻放左括号！然後看到右括号就出棧::

1. 編寫一個函數，求字尾式的數值，其中字尾式存于字元數組exp中，exp中最後一個‘/0’作為結束符，并假設字尾式中的數字都隻有一位。

//先定義操作符
int op(int a, char op, int b){
    if(op == '+') return a + b;
    if(op == '-') return a - b;
    if(op == '*') return a * b;
    if(op == '/'){
        if(b == ){
            std::cout<<"b不能為0！"<<endl;
            return ;
        }
        else return a/b;
    }
}

//再定義字尾計算函數
int com(char exp[]){
    int stack[maxSize];
    int top == -;
    int a, b, c;
    char op;
    for(int i = ; exp[i] != '/0'; ++i){
        if(exp[i] >= '0' && exp[i] <= '9')
        stack[++top] = exp[i] - '0';
        else{
            op = exp[i];
            b = stack[top--];
            a = stack[top--];
            c = op(a, op, b);
            stack[++top] = c;
        }
    }
    return stack[top];
}
           

隊列

隊列的存儲結構

順序隊

typedef struct SqQueue
{
    int data[maxSize];
    int front;
    int rear;
}SqQueue;
           

鍊隊

//隊結點類型定義
typedef struct QNode
{
    int data;
    struct QNode *next;
}QNode;

//隊類型定義
typedef struct LiQueue
{
    QNode *front;
    QNode *rear;
}LiQueue;
           

順序隊

使用傳統的順序隊列會産生“假溢出”情況，我們一般使用循環隊列。

當元素進隊時，rear指針向後移動；

當元素出隊時，front指針向前移動。

• 兩狀态
  1. 隊空狀态：qu.rear == qu.front
  2. 隊滿狀态：(qu.rear + 1)%maxSize == front
• 兩操作
  1. 元素x進隊：

qu.rear == (qu.rear + )%maxSize;
qu.data[qu.rear] = x;
           

1. 元素x出隊：

qu.front == (qu.front + )%maxSize;
x = qu.data[qu.front];
           

::都是先移動指針，後存取資料。::

鍊隊

不存在“假溢出”。

• 兩狀态
  1. 隊空狀态：lqu->rear == NULL || lqu->front == NULL
  2. 不存在隊滿狀态
• 兩操作
  1. 入隊：

lqu->rear->next = p;
lqu->rear = p;
           

1. 出隊：

p = lqu->front;
lqu->front = lqu->front->next;
x = p->data;
free(p);
           

::順序隊比鍊隊簡單多了，要盡量用順序隊。::

總習題

1. 設循環隊列的下标範圍是0~n-1，其頭、尾指針分别為f和r，則其元素個數為 (r - f + n)%n
   • 當r > f 時，隊列内元素為r - f；
   • 當r < f 時，隊列内元素為n - ( f - r )
2. 編寫一個算法，将一個非負的十進制整數N轉換為一個二進制數。

int BaseTrans(int N){
    int i, result = ;
    int stack[maxSize], top = -;
    while(N != ){
        i = N % ;
        N = N / ;
        stack[++top] = i;
    }
    while(top != -){
        i = stack[top--];
        result = result *  + i;
    }
    return result;
}