c語言建立棧

• 順序存儲
• • 棧的順序存儲定義
  • 初始化棧
  • 入棧操作
  • 出棧操作
  • 其余操作
  • • 讀取棧頂元素
    • 棧中元素個數
    • 棧是否為空
• 雙棧
• • 雙棧的順序存儲結構定義
  • 建立雙棧
  • 判斷棧為空
  • 進棧操作
  • 出棧操作
• 鏈式棧
• • 前言
  • 鏈式存儲表示
  • 進棧操作
  • 出棧操作
  • 取棧頂元素
  • 置空棧

順序存儲

我們采用的是動態分配方式來定義順序存儲。

順序棧本質上是順序表的簡化，由于棧底位置是不變的，所以可以將棧底位置設置在存儲空間的基地址上，站定位置隨著元素的增刪而變化，故用top來指示當前棧頂元素的下一個位置，通常稱top為棧頂指針。

有以下幾點聲明：

賦值操作：*s->top = val;

棧為空：s->top == s->base

棧滿：s->top-s->base >=stacksize

棧的順序存儲定義

#define MAXSTACKSIZE 100 #define STACKINCREMENT 10typedef struct {int* base;int* top;int stacksize; }SqStack;

初始化棧

SqStack* InitStack_Sq() {SqStack* s;s = (SqStack*)malloc(sizeof(SqStack)); //記得申請空間s->base = (int*)malloc(MAXSTACKSIZE *sizeof(int));if (!s->base) {printf("內存分配失敗\n");return 0;}//同時指向一個位置s->top = s->base;s->stacksize = MAXSTACKSIZE;return s; }

入棧操作

//入棧 void Push_Sq(SqStack* s, int val) {if (s->top - s->base >= s->stacksize) { //滿棧了s->base = (int*)realloc(s->base,sizeof(int) * (MAXSTACKSIZE + STACKINCREMENT));if (!s->base) {printf("內存分配失敗\n");return;}s->stacksize += STACKINCREMENT;s->top = s->base;}*s->top = val;s->top++;// *s->top++ = val; }

出棧操作

//出棧 // s->top 指向的是棧頂的下一個，所以要先減，再取值 int Pop_Sq(SqStack* s) {if (s->base == s->top) {printf("隊列為空\n");return 0;}int val = *(--s->top);return val; }

其余操作

讀取棧頂元素

//讀取棧頂 int Top_Sq(SqStack* s) {if (s->base == s->top) {printf("隊列為空\n");return 0;}return *(s->top - 1); }

棧中元素個數

//返回棧中元素個數 int stackLength(SqStack* s) {return s->top - s->base; }

棧是否為空

//判斷棧是否為空 int empty_sq(SqStack* s) {if (s->base == s->top)return 1;elsereturn 0; }

雙棧

MAXSTACKSTZE為整個數組空間的長度，棧1的底端固定在下標為0的一端，棧2的底端固定在下標為MAXSTACKSIZE -1 的一端。 top?1 和 top2分別為棧1和棧2的棧頂指針，并約定棧頂指針指向當前元素，即棧1空的條件是 top1=?1,棧1滿的條件top1=top?2?
1，棧2空的條件是 top?2=MAXSTACSIZE,棧2滿的條件是 。top2=top1+1。

雙棧的順序存儲結構定義

#define MAXSTACKSIZE 100typedef struct {int data[MAXSTACKSIZE];int top1, top2; }doubleStack;

建立雙棧

//建立雙棧 doubleStack* init() {doubleStack* s;s = (doubleStack*)malloc(sizeof(doubleStack));s->top1 = -1;s->top2 = MAXSTACKSIZE;return s; }

判斷棧為空

//flag = 1 是棧1，flag = 2 是棧2 int empty_D(doubleStack* s,int flag) {if (flag == 1) {if (s->top1 == -1)return 1;elsereturn 0;}else {if (s->top1 == MAXSTACKSIZE)return 1;elsereturn 0;} }

進棧操作

//進棧 void Push_D(doubleStack* s, int flag, int val) {if (s->top1 + 1 == s->top2) {printf("棧已滿\n");return;}if (flag == 1) // 對棧一進行操作s->data[++s->top1] = val; //先使棧1的頂指針增加1，再將元素插入elses->data[--s->top2] = val; //先使棧2的頂指針減1，再將元素插入 }

出棧操作

// 出棧 // 指針移動就相當于刪除操作 int Pop_D(doubleStack* s, int flag) {if (flag == 1) {if (s->top1 == -1) {printf("棧為空\n");return;}int val = s->data[s->top1--]; //先刪除棧頂元素，再講棧頂指針減1return val;}else {if (s->top1 == MAXSTACKSIZE) {printf("棧為空\n");return;}int val = s->data[s->top1++];//先刪除棧頂元素，再講棧頂指針加1return val;} }

鏈式棧

前言

鏈式存儲表示

若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。人們將用鏈式存儲結構表示的棧稱作“鏈棧”。

鏈棧通常用一個無頭結點的單鏈表表示。由于棧的插入、刪除操作只能在一端進行，而對于單鏈表來說，在首端插入、刪除結點要比在尾端進行相對容易一些，所以將單鏈表的首端作為棧的頂端，即將單鏈表的頭指針作為棧頂指針。

typedef struct SNode {int data; //數據域SNode* next; //鏈域 }SNode,*LinkStack; LinkStack top; //棧頂指針

進棧操作

void init(LinkStack &top) {top = NULL; }//進棧操作 void Push_L(LinkStack &top, int val) {SNode* node = (LinkStack)malloc(sizeof(SNode));if (!node) {printf("申請空間失敗\n");return;}node->data = val;node->next = top; //因為剛開始是空的，所以棧底元素指向的下一個元素為空top = node; //棧頂指針指向新節點 }

出棧操作

//出棧操作 int Pop_L(LinkStack &top) {if (!top) {printf("棧為空\n");return 0;}int val = top->data;SNode* p = top;top = top->next; //修改棧頂指針，將棧頂節點從鏈上摘下free(p);return val; }

取棧頂元素

//取棧頂元素 int Top_L(LinkStack top) {if (!top) {printf("棧為空\n");return;}int val = top->data; //取棧頂元素return val; }

置空棧

//棧置空 void Clear_L(LinkStack &top) {while (top) {SNode* p = top;top = top->next;free(p);p = NULL;} }

總結

以上是生活随笔為你收集整理的c语言建立栈（顺序栈、双栈和链式栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。