資料結構學習---棧和隊列

棧和隊列的定義和特點

1、棧

• 棧和隊列是限定插入和删除隻能在表的“端點”進行的線性表
• 表尾稱為棧頂（top），表底稱為棧底（bottom）
• 不含有元素的空表稱為空棧
• 與線性表不同，棧插入的隻能插入在最後的位置，删除也隻能删除最後的位置（後進先出）
• 一般用于解決下列的問題
  • 數制轉換
  • 表達式求值
  • 括号比對檢驗
  • 八皇後問題
  • 行編輯程式
  • 函數調用
  • 迷宮求解
  • 遞歸調用的實作等

一般線性表	棧
邏輯結構	一對一
存儲結構	順序表、連結清單	順序表、鍊棧
運算規則	随機存取	後進先出（LIFO）

2、隊列

• 隊列是一種先進先出的線性表
• 插入的時候隻能插入在隊尾（rear），删除的時候隻能在隊頭（front）删除（先進先出）
• 一般用于解決類似下列的問題
  • 脫機列印輸出
  • 多使用者系統中，用于使用者排成隊，分時地循環使用CPU和主存
  • 按使用者的優先級排成多個隊，每個優先級一個隊列
  • 實時控制系統中，信号按接收的先後順序依次處理
  • 網絡電文傳輸，按到達時間先後順序依次進行等
• 隊列的特點

隊列
存儲方式	順序隊、鍊隊
	先進先出
實作方式	入隊和出隊操作，具體實作依順序隊或鍊隊的不同而不同

棧與隊列的應用案例

• 1.進制的轉換，如将十進制轉換為八進制數
  • 将十進制數除以8，然後将餘數分别入棧，最後在出棧，出棧的順序就是最終轉換為8進制的結果
• 2.括号比對的檢驗，括号在實際使用的時候一定是成對出現的，現在可以使用過堆棧來檢測使用的括号是否是成對出現的
  • 将左括号分别入棧，當檢測到一個有括号的時候，就将棧頂的元素與之對應 出棧一個，如果存在不比對的情況，那麼入棧的和出棧之間就不能配對，這樣就起到了檢測括号是否成對的效果。
• 3.表達式求值，實際應用中，加減乘除與括号優先級不同，需要按照優先級進行計算，此時可以使用棧來解決優先級問題
  • 使用兩個棧，一個存放運算符，另外一個存放運算數
  • 當掃描的是運算數的時候直接壓入棧
  • 當時運算符的時候
    • 若這個運算符比運算符（OPTR）棧頂優先級高，則入棧繼續向後處理
    • 若這個運算符比OPTR棧頂運算符優先級低，則從OPTR棧中彈出兩個運算數，從棧OPTR中彈出棧頂運算符進行運算，并将運算結果壓入存放運算數（OPND）的棧
  • 繼續處理目前字元，直到遇到結束符為止
  • 實際上還能将标準的運算式轉換為中綴表達式，僅需要使用一個棧即可完成運算
• 舞伴問題
  • 問題：假設在舞會上，男士和女士各自排成一隊，舞會開始時，依次從男隊和女隊的隊頭各出一人配成舞伴，如果兩隊初始人數不相同，則較長的那一隊中未配對者等待下一輪舞曲。
  • 思路：首先構造兩個隊列，依次将隊頭元素出隊配成舞伴，某隊為空，則另外一對等待着則是下一舞曲第一個可獲得舞伴的人

棧的表示和操作的實作

• 棧的抽象資料類型定義(後面将會在順序和鍊式結構中實作)

// 1、初始化堆棧
InitStack(&s)
// 2、銷毀棧操作
DestroyStack(&S)
// 3、判定S是否為空棧
StackEmply(S)
// 4、求棧的長度
StackLength(S)
// 5、取棧頂元素
GetTop(S, &e)
// 6、棧置空操作
ClearStack(&S)
//  7、入棧操作
Push(&S, e)
// 出棧操作
Pop(&S, &e)

           

• 1、棧在順序表中的實作（順序棧）

  利用一組位址連續的存儲單元依次存放自棧底到棧頂的資料元素，棧底一般在低位址端

  • 附設top指針，訓示棧底元素在順序棧中的位置
  • 另設base指針，訓示棧底元素在順序棧中的位置

//順序棧的存儲結構
#define MAXSIZE 100
typedef struct
{
  SElemType *base;
  SElemType *top;
  int stacksize;
}SqStack;
           

• base 為棧底指針，初始化完成後，棧底指針base始終指向棧底的位置，若base的值為NULL，則表明棧結構不存在。top為棧頂指針，其初值指向棧底。每當插入新的棧頂元素時，指針top增1; 删除棧頂元素時，指針top減l。是以，棧空時，top和base的值相等，都指向棧底；棧非空時，top始終指向棧頂元素的上一個位置。
• stacksize訓示棧可以使用的最大容量
• 兩個指針相減，相當于獲得兩個元素之間差幾個元素，也就是兩個元素之間的元素個數。

//順序棧的初始化
Status InitStack(SqStack &S)
{
  S.base = new SElemType[MAXSIZE];  //c++中，使用該方法删除的時候需要使用delete S；
  if(!S.base)
    exit(OVERFLOW);                 //存儲空間配置設定失敗
  S.top = S.base;
  S.stacksize = MAXSIZE;
  return OK;
  
}
           

//判斷棧是否為空
Status StackEmpty(SqStack S)
{
  if(S.top == S.base)
    return TRUE;
  else
    return FALSE;
}
           

//求順序棧的長度
int StackLength(SqStack S)
{
  return S.top-S.base;  //直接使用棧頂減去棧底就是棧的長度
}
           

//清空順序棧，棧仍然保留，但是裡面的元素為空，不用将所有的資料删除，
//直接将指針指向棧底即可，新資料入棧時自然會将就資料覆寫掉
Status ClearStack(SqStack &S)
{
  if(S.base)
    S.top = S.base;
  return OK;
}

           

//銷毀一個棧，與清空不一樣，空間全部需要釋放了
Status DestroyStack(SqStack &S)
{
  if(S.base)
  {
    delete S.base;     //釋放空間
    S.stacksize = 0;
    S.base = S.top = NULL;
  }
  return OK;
}

           

//順序棧的入棧操作，在棧頂插入元素e
Status Push(SqStack &S, SElemType e)
{
  if(S.top-S.base == S.stacksize)    //判斷棧是否滿了
    return ERROR;                    //棧已滿，上溢
  *S.top++ = e;                      //兩步合成一步 *S.top = e; S.top++;存完後指針後一位
  return OK;
}

           

//出棧操作
Status Pop(SqStack &S,SElemType &e)
{
   //删除s的棧頂元素，用e傳回删除的值
   if(S.top == S.base)
      return ERROR;
    e = *--S.top;      //棧頂指針是指向最上面元素在往後一個位置的，是以要先--才能通路到棧頂的值
    return OK;
}


           

//取出順序棧的棧頂元素
SElemType GetTop(SqStack S)
{
  //傳回棧頂元素，不修改棧頂指針
  if(S.top != S.base)      //棧非空
    return *(S.top - 1);   //傳回棧頂元素的值，棧頂指針不變
}