[科普中國]-先入后出隊列

定義

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

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

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

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

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

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

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

代碼實現(xiàn)C/C++C語言或C++語言實現(xiàn)先進后出隊列（可不加鎖），舉例代碼如下：

#include "cas.h" #include 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; };PythonQueue是python標(biāo)準(zhǔn)庫中的線程安全的隊列實現(xiàn),提供了一個適用于多線程編程的先進先出的數(shù)據(jù)結(jié)構(gòu)，即隊列，用來在生產(chǎn)者和消費者線程之間的信息傳遞。Python內(nèi)置四種隊列：LILO隊列，LIFO隊列，優(yōu)先隊列和雙端隊列。LIFO隊列，即先入后出隊列，舉例代碼如下：

import Queueq = Queue.LifoQueue()for i in range(5): q.put(i)while not q.empty(): print q.get()輸出：43210應(yīng)用舉例數(shù)制轉(zhuǎn)換十進制數(shù)N和其他d進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，基本算法基于下列原理：

其中，div為整除運算，mod為求余運算。下面舉例實現(xiàn)將輸入的十進制數(shù)轉(zhuǎn)換成對應(yīng)的八進制數(shù)：

/* 輸入一個數(shù)，然后輸出其對應(yīng)的8進制的數(shù) */ #include #define MAX 1000//順序棧存儲空間最大值 //int n,m;//n表示輸入的數(shù)，m表示輸出的數(shù)的進制 //先定義一個順序棧的結(jié)構(gòu) 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); } //數(shù)制轉(zhuǎn)換 void conversion(SqStack &S,int n){ //n表示輸入的數(shù)，m表示輸出的數(shù)的進制 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("請輸入數(shù)n:"); scanf("%d",&n); conversion(S,n); } 括號匹配的檢驗在算法中設(shè)置一個棧，每讀入一個括號，若是右括號，那么有兩種結(jié)果：①使置于棧頂?shù)淖罴逼鹊钠诖靡韵?；②不合法。若為左括號，則作為一個新的更急迫的期待壓入棧中，使得原有的在棧中的所以未消除的期待的急迫性下降一級。另外，在算法開始和結(jié)束時，棧都應(yīng)該是空棧。1下面舉例實現(xiàn)括號匹配的檢測：

void Matching(char e[]){ Stack S; InitStack(S); unsigned int i = 0, state = 1; char z; while((int)(i