基本介紹
- 中文名：先入後出佇列
- 外文名：First-in last-out queue
- 別名：堆疊
- 領域：計算機
- 類型：數據結構
- 相關：FIFO，LIFO
定義,基本算法,進棧算法,退棧算法,代碼實現,C/C++,Python,套用舉例,數制轉換,括弧匹配檢驗,
定義
棧（Stack）是限定僅在表尾進行插入或刪除操作的線性表。即棧的修改是按照後進先出的原則進行的，故棧又成為後進先出（Last In First Out）的線性表或先入後出佇列。
基本算法
進棧算法
①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；
③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 Queue
q = Queue.LifoQueue()
for i in range(5):
q.put(i)
while not q.empty():
print q.get()
輸出：
4
3
2
1
0
套用舉例
數制轉換
十進制數N和其他d進制數的轉換是計算機實現計算的基本問題，基本算法基於下列原理：
/*
輸入一個數，然後輸出其對應的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);
}
