先入後出佇列

堆疊是一個在計算機科學中經常使用的抽象數據類型。堆疊中的物體具有一個特性： 最後一個放入堆疊中的物體總是被最先拿出來， 這個特性通常稱為後進先出(LIFO)佇列，即先入後出佇列。 堆疊中定義了一些操作。 兩個最重要的是PUSH和POP。 PUSH操作在堆疊的頂部加入一個元素。POP操作相反， 在堆疊頂部移去一個元素， 並將堆疊的大小減一。

基本介紹

• 中文名：先入後出佇列
• 外文名：First-in last-out queue
• 別稱：堆疊
• 領域：計算機
• 類型：數據結構
• 相關：FIFO，LIFO

定義

棧（Stack）是限定僅在表尾進行插入或刪除操作的線性表。即棧的修改是按照後進先出的原則進行的，故棧又成為後進先出（Last In First Out）的線性表或先入後出佇列。

基本算法

進棧算法

①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；

②置TOP=TOP+1（棧指針加1，指向進棧地址）；

③S(TOP)=X，結束（X為新進棧的元素）；

退棧算法

①若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；

②X=S(TOP)，（退棧後的元素賦給X）；

③TOP=TOP-1，結束（棧指針減1，指向棧頂）。

代碼實現

C/C++

C語言或C++語言實現先進後出佇列（可不加鎖），舉例代碼如下：

#include "cas.h" #include <stddef.h>struct lifo_node {     volatile struct lifo_node *next; };struct lifo { void init() {     top = NULL;     cnt=0; }void push(lifo_node *node) {    struct lifo old_val, new_val;    do {      old_val = *this;      node->next = old_val.top;      new_val.top = node;      new_val.cnt = old_val.cnt;    }while(!CAS2(this, old_val, new_val)); }   lifo_node * pop() {    struct lifo_node *node;    struct lifo old_val, new_val;    do {      old_val = *this;      node = old_val.top;      new_val.top = old_val.top;      new_val.cnt = old_val.cnt+1;    }while(!CAS2((this), old_val, new_val));    return node; }struct lifo_node * volatile top; volatile unsigned int cnt; };

Python

Queue是python標準庫中的執行緒安全的佇列實現,提供了一個適用於多執行緒編程的先進先出的數據結構，即佇列，用來在生產者和消費者執行緒之間的信息傳遞。Python內置四種佇列：LILO佇列，LIFO佇列，優先佇列和雙端佇列。LIFO佇列，即先入後出佇列，舉例代碼如下：

import Queueq = Queue.LifoQueue()for i in range(5):    q.put(i)while not q.empty():    print q.get()輸出：43210

套用舉例

數制轉換

十進制數N和其他d進制數的轉換是計算機實現計算的基本問題，基本算法基於下列原理：

其中，div為整除運算，mod為求余運算。下面舉例實現將輸入的十進制數轉換成對應的八進制數：

/* 輸入一個數，然後輸出其對應的8進制的數  */   #include<stdio.h>  #define MAX 1000//順序棧存儲空間最大值   //int n,m;//n表示輸入的數，m表示輸出的數的進制       //先定義一個順序棧的結構  typedef struct{      int *base;//棧底4指針       int *top;//棧頂指針      int stacksize;   }SqStack;    //初始化順序棧  int InitStack(SqStack &S){      S.base=new int[MAX];      if(!S.base){          return 0;//存儲空間分配失敗       }      S.top=S.base;      S.stacksize=MAX;      return 1;  }     //判斷棧是否為空  int IsEmpty(SqStack &S){      if(S.base==S.top){          return 1;//棧空       }else{          return 0;//棧非空       }  }     //入棧  int Push(SqStack &S,int e){      if(S.top-S.base==S.stacksize){          return 0;//棧滿       }      *S.top++=e;      return 1;  }    //出棧   int Pop(SqStack &S,int &e){      if(S.top==S.base){          return 0;//棧空           //printf("棧空\n");      }      e=*--S.top;      return 1;      //printf("%d",e);  }    //數制轉換  void conversion(SqStack &S,int n){      //n表示輸入的數，m表示輸出的數的進制       InitStack(S);      while(n){          Push(S,n%2);          n=n/2;      }            while(!IsEmpty(S)){          int e;          Pop(S,e);          printf("%d",e);      }  }     int main(){            SqStack S;      if(InitStack(S)){          printf("棧S初始化成功!\n");      }else{          printf("棧S初始化失敗!\n");      }            if(IsEmpty(S)){          printf("棧為空.\n");      }else{          printf("棧非空.\n");      }            int n;      printf("請輸入數n:");      scanf("%d",&n);      conversion(S,n);  }  

括弧匹配的檢驗

在算法中設定一個棧，每讀入一個括弧，若是右括弧，那么有兩種結果：①使置於棧頂的最急迫的期待得以消除；②不合法。若為左括弧，則作為一個新的更急迫的期待壓入棧中，使得原有的在棧中的所以未消除的期待的急迫性下降一級。另外，在算法開始和結束時，棧都應該是空棧。下面舉例實現括弧匹配的檢測：

void Matching(char e[]){    Stack S;    InitStack(S);    unsigned int i = 0, state = 1;    char z;    while((int)(i <= strlen(e)) && state && e[i] != '\0')    //結束條件 超出數組長度或state為0或字元串結束    {        switch(e[i])        {        case '(':        case '{':            Push(S,e[i]);    //遇到({則進棧            i++;            break;        case ')':            GetTop(S,z);            if(!StackEmpty(S) && z == '(')    //遇到)則判斷棧頂是不是(，是的話出棧，不是則不匹配            {                Pop(S,z);                i++;            }            else                state = 0;            break;        case '}':            GetTop(S,z);            if(!StackEmpty(S) && z == '{')//遇到}則判斷棧頂是不是{，是則出棧，不是則不匹配            {                Pop(S,z);                i++;            }            else                state = 0;            break;        }    }    if(StackEmpty(S) && state)    //空棧且state不為0則全部匹配        printf("括弧全部匹配");    else        printf("括弧不匹配");}void main(){    char e[20];    printf("請輸入括弧:");    scanf("%s",e);    Matching(e);}