棧
棧是限制在一端進(jìn)行插入和刪除操作的線性表（俗稱堆棧），允許進(jìn)行操作的一端稱為“棧頂”戈轿，另一固定端稱為“棧底”，當(dāng)棧中沒有元素時稱為“空椪笞樱”思杯。特點(diǎn)：先進(jìn)后出（LIFO）。
基本運(yùn)算：
創(chuàng)建空棧：
CreateStack(len)清空棧：
ClearStack(S)判斷是否椖咏空：
EmptyStack(S)判斷是否棧滿：
FullStack(S)元素進(jìn)棧：
PushStack(S)元素出棧：
PopStack(S)取棧頂元素：
GetTop(S)
順序棧：它是順序表的一種智蝠，具有順序表同樣的存儲結(jié)構(gòu)，由數(shù)組定義奈梳，配合用數(shù)組下標(biāo)表示的棧頂指針top（相對指針）完成各種操作杈湾。
typedef int data_t; //定義棧中數(shù)據(jù)元素的數(shù)據(jù)類型
typedef struct
{
data_t *data; //用指針指向棧的存儲空間
int maxlen; //當(dāng)前棧的最大元素個數(shù)
int top; //指示棧頂位置（數(shù)組下標(biāo)）的變量
}seqstack_t; //順序棧類型定義
創(chuàng)建棧
seqstack_t *CreateStack(int len)
{
seqstack_t *ss;
ss = (seqstack_t *)malloc(sizeof(seqstack_t));
ss->data = (data_t *)maloc(sizeof(data_t) *len)
ss->top = -1;
ss->maxlen = len;
return ss;
}
清空棧
ClearStack(seqstack_t *S)
{
S->top = -1
}
判斷棧是否空
int EmptyStack(seqstack_t *S)
{
return (S->top == -1 ? 1:0);
}
進(jìn)棧
void PushStack(seqstack_t *S, data_t x)
{
if(S->top == NULL){
printf("overflow!\n");
return;
}
else{
S->top++;
S->data[S->top] = x;
}
return ;
}
鏈?zhǔn)綏?/h2>
插入操作和刪除操作均在鏈表頭部進(jìn)行，鏈表未卜就是棧底攘须，棧頂指針就是頭指針漆撞。
typedef int data_t; //定義棧中數(shù)據(jù)元素的數(shù)據(jù)類型
typedef struct node_t
{
data_t data; //數(shù)據(jù)域
struct node_t *next; //鏈接指針域
}linkstack_t; //鏈棧類型定義
創(chuàng)建空棧
linkstack_t *CreateLinkstack()
{
linkstack_t *top;
top = (linkstack_t *)malloc(sizeof(linkstack_t));
top->next = NULL;
return top;
}
判斷是否是空棧
int EmptyStack(linkstack_t *top)
{
return (top->next == NULL ? 1:0)
}
入棧
void PushStack(linkstack_t *top, data_t x)
{
linkstack_t *p; //定義輔助指針
p = (linkstack_t *)malloc(sizeof(linkstack_t)); //指向新結(jié)點(diǎn)
p->data = x; //將數(shù)據(jù)存入新結(jié)點(diǎn)的數(shù)據(jù)域中
p->next = top->next;
top->next = p; //新結(jié)點(diǎn)插入原棧頂之前
reurn;
}
隊(duì)列概念及特征
隊(duì)列概念：隊(duì)列是限制在兩端進(jìn)行插入操作和刪除操作的線性表，允許進(jìn)行存入操作的一端稱為“隊(duì)尾”于宙，允許進(jìn)行刪除操作的一端稱為“隊(duì)頭”浮驳。當(dāng)線性表中沒有元素時，稱為“空對”捞魁。
特點(diǎn)：先進(jìn)先出（FIFO）
隊(duì)列的特征：
-
數(shù)據(jù)：
對于非空的隊(duì)列至会，表頭沒有直接前驅(qū)，表尾沒有直接后繼谱俭，其他有且僅有一個直接前驅(qū)和一個直接后繼奉件。
-
操作
只允許在表尾插入數(shù)據(jù)，在表頭刪除數(shù)據(jù)昆著。
規(guī)定：
front:始終存放在表頭前一個位置的下標(biāo)
rear:始終存放隊(duì)尾的下標(biāo)
Ｃ語言中：
結(jié)構(gòu)體——封裝數(shù)據(jù)
函數(shù)——封裝代碼
隊(duì)列的順序存儲
typedef int data_t; //定義隊(duì)列中數(shù)據(jù)元素的數(shù)據(jù)類型
#define MAXSIZE 64 //定義隊(duì)列的容量
typedef struct
{
data_t data[MAXSIZE]; //用數(shù)組作為隊(duì)列的儲存空間
int front, rear; //指示隊(duì)頭前一個位置和隊(duì)尾位置的指針
}sequeue; //順序隊(duì)列類型定義
sequeue *sq; //定義指向順序隊(duì)列的指針
順序隊(duì)列基本算法分析
-
初始化
申請順序隊(duì)列的空間
初始化隊(duì)頭和隊(duì)尾指針
front = rear = -1;
插入
刪除
是否空
是否滿
