我們平常所說的線性表是指操作的位置或元素的內容沒有限制的一種資料結構。 在特定的情況下， 對操作或元素有所限制是很有必要的， 如下圖：
具體到對現實世界的映射， 不同的容器有不同的用途。 普通順序表就像一個敞開的貨架， 你可以放任何東西， 也可以在頭、尾、中間放入和拿取。 佇列就像排隊， 新加入的只能在後面排， 最前面的可以先出隊， 不能插隊。 棧就如同只有一個口的容器， 拿取時只能取出後面放入的。
棧（stack）是一種後進先出（LIFO）的線性表， 棧規定只能在線性表的一端進行插入和刪除元素的操作。 棧一般使用順序存儲的方式存儲， 當然也可以是鏈表存儲。
編寫一個程式， 使用棧結構實現一個二/八進制的轉換器， 二進位和八進位數均可用字串表示。
進制轉換經常使用棧實現， 這與資料流程的輸入方式有關。 輸入一串0字串， 先輸入的字元處於二進位數字的高位，
I 輸入二進位表示的0字串， 將每次輸入的0字元放入棧s1中保存。 按照這種方式進棧後， 棧底存放的是二進位數字的最高位， 棧頂存放的是二進位數字的最低位；
II 從棧s1中取出元素， 每取出三位元0字串， 就將其轉換成一個對應的八進位數， 並用字元表示。 因為先得到的是八進位數的低位， 所以可以將該八進位數保存到一個新棧s2中， 直到將棧s1中的元素取完為止。 這樣八進位數的高位位於s2棧頂， 低位位於s2棧底；
III 將棧s2中的字元逐一取出顯示，
代碼：
運行效果：
運算過程圖示如下：
上面需要轉換的資料1011101將高位先放入s1棧底，後面放入的是低位，轉換後將低位放入s2棧底，高位放到棧底。取出輸出時在s2棧頂先取出高位，剛好就是我們習慣排列的135。
附源碼：
#include "stdio.h"
#include "math.h"
#include "malloc.h"
#define STACK_INIT_SIZE 30
#define STACKINCREMENT 10
typedef struct{
char *base;
char *top;
int stacksize;
}sqStack;
int initStack(sqStack *s)
{
/*記憶體中開闢一段連續空間作為棧空間，首位址賦值給s->base*/
s->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!s->base) return 0;/*分配空間失敗*/
s->top = s->base;/*最開始，棧頂就是棧底*/
s->stacksize = STACK_INIT_SIZE;/*最大容量為STACK_INIT_SIZE */
return 1;
}
int Push(sqStack *s, char e){
if(s->top - s->base >= s->stacksize){/*棧滿，追加空間*/
s->base = (char *)realloc(s->base, (s->stacksize +
STACKINCREMENT)*sizeof(char));
if(!s->base) return 0;/*存儲分配失敗*/
s->top = s->base + s->stacksize;
s->stacksize = s->stacksize + STACKINCREMENT;/*設置棧的最大容量*/
}
*(s->top) = e;/*放入數據*/
s->top++;
return 1;
}
int Pop(sqStack *s , char *e){
if(s->top == s->base) return 0;
*e = *--(s->top);
return 1;
}
void Bi2Oct()
{
sqStack s1;
sqStack s2;
char c;
int i,sum=0;
initStack(&s1);/*創建一個棧s1，用來存放二進位字元串*/
scanf("%c",&c);/*輸入0/1字元表示的二進位數字，以#結束*/
while(c!='#')
{
if(c=='0' || c=='1')
Push(&s1,c);
scanf("%c",&c);
}
initStack(&s2);/*創建一個棧s2，用來存放八進制字串*/
while(s1.top!=s1.base)
{
for(i=0;i<3 && s1.top!=s1.base;i++)
{
Pop(&s1,&c);/*取出棧頂元素*/
sum = sum + (c-48) * pow(2,i);/*轉換為八進位數*/
//數位0-9在ASCII中是48-57號字元
}
Push(&s2,sum+48) ;/*將八進位數以字元形式壓入棧中*/
sum = 0;
}
while(s2.base != s2.top ){/*輸出八進制棧的內容*/
Pop(&s2,&c);
printf("%c",c);
}
}
main()
{
printf("Please input a binary number to convert to octal number，ended by '#' ");
Bi2Oct();
getchar();
getchar();
}
－End－
上面需要轉換的資料1011101將高位先放入s1棧底，後面放入的是低位，轉換後將低位放入s2棧底，高位放到棧底。取出輸出時在s2棧頂先取出高位，剛好就是我們習慣排列的135。
附源碼：
#include "stdio.h"
#include "math.h"
#include "malloc.h"
#define STACK_INIT_SIZE 30
#define STACKINCREMENT 10
typedef struct{
char *base;
char *top;
int stacksize;
}sqStack;
int initStack(sqStack *s)
{
/*記憶體中開闢一段連續空間作為棧空間，首位址賦值給s->base*/
s->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!s->base) return 0;/*分配空間失敗*/
s->top = s->base;/*最開始，棧頂就是棧底*/
s->stacksize = STACK_INIT_SIZE;/*最大容量為STACK_INIT_SIZE */
return 1;
}
int Push(sqStack *s, char e){
if(s->top - s->base >= s->stacksize){/*棧滿，追加空間*/
s->base = (char *)realloc(s->base, (s->stacksize +
STACKINCREMENT)*sizeof(char));
if(!s->base) return 0;/*存儲分配失敗*/
s->top = s->base + s->stacksize;
s->stacksize = s->stacksize + STACKINCREMENT;/*設置棧的最大容量*/
}
*(s->top) = e;/*放入數據*/
s->top++;
return 1;
}
int Pop(sqStack *s , char *e){
if(s->top == s->base) return 0;
*e = *--(s->top);
return 1;
}
void Bi2Oct()
{
sqStack s1;
sqStack s2;
char c;
int i,sum=0;
initStack(&s1);/*創建一個棧s1，用來存放二進位字元串*/
scanf("%c",&c);/*輸入0/1字元表示的二進位數字，以#結束*/
while(c!='#')
{
if(c=='0' || c=='1')
Push(&s1,c);
scanf("%c",&c);
}
initStack(&s2);/*創建一個棧s2，用來存放八進制字串*/
while(s1.top!=s1.base)
{
for(i=0;i<3 && s1.top!=s1.base;i++)
{
Pop(&s1,&c);/*取出棧頂元素*/
sum = sum + (c-48) * pow(2,i);/*轉換為八進位數*/
//數位0-9在ASCII中是48-57號字元
}
Push(&s2,sum+48) ;/*將八進位數以字元形式壓入棧中*/
sum = 0;
}
while(s2.base != s2.top ){/*輸出八進制棧的內容*/
Pop(&s2,&c);
printf("%c",c);
}
}
main()
{
printf("Please input a binary number to convert to octal number，ended by '#' ");
Bi2Oct();
getchar();
getchar();
}
－End－