定義--“彈夾”原理----先進後出--first in last out -FILO
(類似于往箱子裡面放東西)
分類--1> 靜态棧--數組
2> 動态棧--鍊棧,順序棧(連結清單原理)
--隻能在頭部進行插入和删除
算法：
1>出棧push
2>入棧(壓棧)pop
3.判斷棧滿棧空
應用：
函數的調用--依靠壓棧和出棧
函數參數的存儲--壓棧
局部變量的存儲
中斷
表達式求值
記憶體配置設定
緩沖處理
迷宮
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <assert.h> 4 #include <unistd.h> 5 //棧--動态棧--一般不存在棧滿的問題 6 //1.棧的初始化--建立空棧 7 //2.入棧(壓棧)--往棧中添加元素 8 //3.棧的周遊輸出 9 //4.出棧--lifo-後進先出 10 //5.判斷棧是否為空 11 //6.出棧--一個一個的出 "彈夾原理" 12 //7.清空棧 13 14 15 16 typedef struct node 17 { 18 int data; 19 struct node next; 20 }node,pnode; 21 22 typedef struct stack 23 { 24 pnode top;//棧頂 25 pnode base;//棧底 26 }stack,*pstack; 27 28 29 //函數的聲明 30 void init(pstack s); 31 void push(pstack s); 32 void traverse(pstack s); 33 void pop(pstack s); 34 void clear(pstack s); 35 36 int main() 37 { 38 stack s; 39 init(&s); //棧的初始化--建立一個空棧 40 push(&s); //入棧--一個一個的壓 41 traverse(&s); //周遊輸出 42 putchar(10); // 換行 43 44 pop(&s);//出棧 45 traverse(&s); //周遊輸出 46 putchar(10); 47 clear(&s); //清空 48 } 49 50 51 //1.棧的初始化--建立一個空棧 52 void init(pstack s) 53 { 54 s->top=(pnode)malloc(sizeof(node)); //要初始化,首先就得先配置設定空間 55 assert(s->top != NULL ); //判斷動态記憶體空間是否配置設定成功 56 s->base =s->top; //空棧的時候,棧底就是棧頂 57 //隻能這樣寫,因為base沒有配置設定空間,如果換位置,就會發生段錯誤 58 s->top->next =NULL; //類似與連結清單中的初始化的頭節點指向NULL 59 60 } 61 62 //2.入棧 63 void push(pstack s) 64 { 65 int len=0; 66 int val=0; 67 int i=0; 68 printf("你想要往棧中添加幾個元素?\n"); 69 scanf("%d",&len); 70 char ch =getchar(); 71 for(i=0;i<len;i++) 72 { 73 pnode new =(pnode)malloc(sizeof(node)); 74 assert(new != NULL); 75 printf("請輸入第%d個壓入棧中的值: \n",i+1); 76 scanf("%d",&val); 77 new -> data =val; 78 new -> next =s->top; 79 s->top =new; 80 } 81 } 82 83 //周遊輸出 84 void traverse(pstack s) 85 { 86 pnode p=s->top; 87 while(p != s->base) 88 { 89 printf("%d ",p->data); 90 p=p->next; 91 } 92 93 } 94 95 //出棧 96 void pop(pstack s) 97 { 98 if(s->top != s->base) 99 { 100 pnode p=s->top; 101 s->top=s->top->next; 102 free(p); 103 printf("出棧成功!\n"); 104 } 105 else if(s->top == s->base) 106 { 107 printf("棧中已經沒有元素啦!\n"); 108 } 109 } 110 111 //棧的清空 112 void clear(pstack s) 113 { 114 if(s->top == s->base) 115 { 116 printf("棧中已經沒有元素啦!\n"); 117 } 118 else 119 { 120 printf("開始清空!\n"); 121 sleep(1); 122 while(s->top != s->base) 123 { 124 pnode p=s->top; 125 s->top=s->top->next; 126 free(p); 127 p=s->top; 128 } 129 printf("清空完畢,退出程式!\n"); 130 exit(-1); 131 132 } 133 134 135 }