第二十四天（數據結構：棧和隊列）隊列實踐請看下一篇

棧和隊列棧 ： 是限定在表尾進行插入和刪除操作的線性表實現是一回事，但是必須要滿足棧的基本特點它的設計思路是:先進后出，后進先出棧有兩端1 棧頂(top) ：插入數據刪除數據都只能在這一端訪問也只能訪問棧頂2 棧底(bottom) : 棧底是不會動實現棧我們就需要實現如下操作：init    初始化這個棧top     返回棧頂元素，但是不出棧empty   判斷棧是否為空size    棧里面有多少個元素push    入棧pop     出棧clear   清空這個棧destory 銷魂這個棧我們可以使用鏈式結構或者順序結構來實現這個棧1 鏈式 --- 利用鏈表,對鏈表的操作進行限定struct stacknode{int data;struct stacknode * prev;};//利用頭節點來搞定stacknode的管理  對于用戶來說是最友好的struct ListStack{struct stacknode * top;//指向棧頂元素的int num;//為了防止爆棧(溢出)  我們可以弄一個最大值來進行限定int maxnum;.....};2 順序 --- 利用數組，對數組的操作進行限定struct ArrayStack //同樣是為了管理我們的棧的{//int stack[];//容納所有的棧里面的元素int * stack;//我給你開辟一個數組出來讓stack去保存int  top;//指向棧頂元素的int num;//為了防止爆棧(溢出)  我們可以弄一個最大值來進行限定int maxnum;.....};先弄一遍鏈式棧，請實現順序棧隊列：是限定在表尾進行插入，在表頭刪除操作的線性表實現是一回事，但是必須要滿足隊列的基本特點它的設計思路是:先進先出，后進后出有兩頭：隊頭(front)，刪除操作在這一邊進行隊尾(rear),插入操作在這一邊進行
隊列在實現的時候有兩種1 鏈式隊列 --- 鏈表實現 -> 不存在假溢出struct queuenode{int data;struct queuenode * next;//做尾插};//利用頭節點來搞定queuenode的管理  對于用戶來說是最友好的struct ListQueue{struct stacknode * front;//指向隊頭元素的 刪除的時候砍掉這個頭struct stacknode * rear;//指向隊尾元素的  插入的時候往rear的后面進行插入int num;//隊列里面有多少個元素//為了防止爆隊(溢出)  我們可以弄一個最大值來進行限定int maxnum;.....};2 順序隊列 --- 利用數組來實現根據隊列的特點我們可以知道入隊出隊front rear都是在++總有一個時候隊列沒有滿，但是入隊的時候已經溢出了 -- 假溢出因此我們設計順序隊列一定要設計為循環隊列讓前面已經出隊的地方可以繼續容納新的元素設計循環隊列有幾種思路1 用num來表示我們的循環隊列里面有多少個元素只要num沒有達到它的最大容納上限我就可以繼續入隊只是rear跑到最后去了之后，我們需要讓它從頭開始2 我們可以利用front 和 rear來進行元素個數，是否為空，是否滿的判斷-> 沒有變量num來對我們的元素個數來進行判斷 ---- 這種是常用的根據我們的分析可以知道 當front == rear的時候沒有辦法判斷這個隊列是空的還滿的因此循環隊列設計的時候，我們實際隊列容納個數要比最大的容納個數少一個maxnum == 5,實際隊列容納就是 5 - 1公式：隊空的判斷:front == rear隊滿的判斷:(rear + 1) % maxnum == front隊列的元素個數：(rear - front + maxnum) % maxnumstruct ArrayQueue //同樣是為了管理我們的隊列的{//int queue[];//容納所有的隊列里面的元素int * queue;//我給你開辟一個數組出來讓queue去保存int  front;//指向對頭元素的 指向要刪除的數據int rear;//指向隊尾元素 指向要插入的數據//為了防止爆隊(溢出)  我們可以弄一個最大值來進行限定int maxnum; // 實際隊列容納個數為 maxnum - 1};隊列需要實現如下操作init        初始化這個隊列front       返回隊頭元素，但是不出隊empty       判斷是否為空full        判斷是否為滿size        返回元素個數push(inqueue)        入隊pop(outqueue)         出隊clear       清空這個隊列destory     銷毀這個隊列搞定循環隊列，然后將鏈式隊列寫出來棧最基本的應用就是算表達式的值2+3*5-6*7+8*9-10%3=你輸入2+3*5-6*7+8*9-10%3=這個字符串簡單一點就用scanf(%s) -> 中間就不能有空格回車就會得到它的結果gets -> 從終端獲取一行字符串不想要警告，請使用fgets鏈式棧

.h與.c

#ifndef __LISTSTACK_H__
#define __LISTSTACK_H__#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int LS_DataType;
#define LS_ERRORVALUE (LS_DataType)(1 << 31)//棧的錯誤值//節點
typedef struct LS_Node
{LS_DataType _data;//棧的數據struct LS_Node * _next;//寫next就用頭插
}LS_Node;//管理棧的頭節點
typedef struct
{LS_Node * _top;//棧頂  插入刪除訪問都這一端int _num;//現在棧里面有多少個元素int _maxnum;//最大的容納個數
}ListStack;//init    初始化這個棧
//maxnum:程序員限定的最大元素個數   如果小于等于0   默認10000000
ListStack * ListStack_init(int maxnum);//top     返回棧頂元素，但是不出棧
//返回LS_ERRORVALUE表示失敗
LS_DataType ListStack_top(ListStack * st);//empty   判斷棧是否為空
bool ListStack_empty(ListStack * st);//full    判斷是不是滿了
bool ListStack_full(ListStack * st);//size    棧里面有多少個元素
int ListStack_size(ListStack * st);//push    入棧  失敗返回false
bool ListStack_push(ListStack * st,const LS_DataType data);//pop     出棧 沒有返回元素  失敗返回false
//如果你有需求返回元素也是可以的
//如果你要得到出棧元素 你需要先top再pop
bool ListStack_pop(ListStack * st);//clear   清空這個棧
//callback是否要處理數據，傳NULL為不處理
void ListStack_clear(ListStack * st,void (*callback)(const LS_DataType));//destory 銷魂這個棧
//callback是否要處理數據，傳NULL為不處理
void ListStack_destory(ListStack ** st,void (*callback)(const LS_DataType));#endif

#include "ListStack.h"//創建棧的節點  這個接口是不需要給用戶用的
static LS_Node * LS_Node_create(const LS_DataType data)
{LS_Node * ptr = (LS_Node *)calloc(1,sizeof(LS_Node));ptr ->_data = data;return ptr;
}//init    初始化這個棧
//maxnum:程序員限定的最大元素個數   如果小于等于0   默認10000000
ListStack * ListStack_init(int maxnum)
{if(maxnum <= 0){maxnum = 10000000;}ListStack * st = (ListStack *)calloc(1,sizeof(ListStack));st ->_maxnum = maxnum;return st;
}//top     返回棧頂元素，但是不出棧
//返回LS_ERRORVALUE表示失敗
LS_DataType ListStack_top(ListStack * st)
{if(ListStack_empty(st))//棧是空的 返回不了一點return LS_ERRORVALUE;return st ->_top ->_data;
}//empty   判斷棧是否為空
bool ListStack_empty(ListStack * st)
{if(!st)return true;return st ->_num == 0;
}
//full    判斷是不是滿了
bool ListStack_full(ListStack * st)
{if(!st)return true;return st ->_num == st ->_maxnum;
}
//size    棧里面有多少個元素
int ListStack_size(ListStack * st)
{return !st ? 0 : st ->_num;
}//push    入棧  失敗返回false
bool ListStack_push(ListStack * st,const LS_DataType data)
{//入棧就是一個頭插if(!st || ListStack_full(st))return false;//先弄一個節點LS_Node * ptr = LS_Node_create(data);//對這個節點進行頭插ptr ->_next = st ->_top;st ->_top = ptr;//將棧頂弄到新加入的節點上面來st ->_num++;return true;
}//pop     出棧 沒有返回元素  失敗返回false
//如果你有需求返回元素也是可以的
//如果你要得到出棧元素 你需要先top再pop
bool ListStack_pop(ListStack * st)
{if(!st || ListStack_empty(st))return false;//將top給刪除LS_Node * ptr = st ->_top;//標記要刪除的節點st ->_top = st ->_top ->_next;//top到后面去了st ->_num--;//數量少一個了ptr ->_next = NULL;//孤立這個節點free(ptr);return true;
}//clear   清空這個棧
//callback是否要處理數據，傳NULL為不處理
void ListStack_clear(ListStack * st,void (*callback)(const LS_DataType))
{while(!ListStack_empty(st))//只要你的棧不是空的 就一直出棧{LS_DataType data = ListStack_top(st);//獲取棧頂元素ListStack_pop(st);if(callback && LS_ERRORVALUE != data){callback(data);}}
}
//destory 銷魂這個棧
//callback是否要處理數據，傳NULL為不處理
void ListStack_destory(ListStack ** st,void (*callback)(const LS_DataType))
{if(!st)return;ListStack_clear(*st,callback);//先清空//將頭節點給刪除free(*st);*st = NULL;
}

順序棧：

.h與.c

#ifndef __ARRAYSTACK_H__
#define __ARRAYSTACK_H__#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>typedef int AS_DataType;
#define AS_ERRORVALUE (AS_DataType)(1 << 31)//棧的錯誤值typedef struct  //同樣是為了管理我們的棧的
{AS_DataType * _st_arr;//我給你開辟一個數組出來讓_st_arr去保存數據int  _top;//指向棧頂元素的  下標 入棧從_top開始，棧頂元素為_top-1int _num;//為了防止爆棧(溢出)  我們可以弄一個最大值來進行限定int _maxnum;
}ArrayStack;//init    初始化這個棧
//maxnum:程序員限定的最大元素個數   如果小于等于0   默認10000000
ArrayStack * ArrayStack_init(int maxnum);//top     返回棧頂元素，但是不出棧
//返回LS_ERRORVALUE表示失敗
AS_DataType ArrayStack_top(ArrayStack * st);//empty   判斷棧是否為空
bool ArrayStack_empty(ArrayStack * st);//full    判斷是不是滿了
bool ArrayStack_full(ArrayStack * st);//size    棧里面有多少個元素
int ArrayStack_size(ArrayStack * st);//push    入棧  失敗返回false
bool ArrayStack_push(ArrayStack * st,const AS_DataType data);//pop     出棧 沒有返回元素  失敗返回false
//如果你有需求返回元素也是可以的
//如果你要得到出棧元素 你需要先top再pop
bool ArrayStack_pop(ArrayStack * st);//clear   清空這個棧
//callback是否要處理數據，傳NULL為不處理
void ArrayStack_clear(ArrayStack * st,void (*callback)(const AS_DataType));//destory 銷魂這個棧
//callback是否要處理數據，傳NULL為不處理
void ArrayStack_destory(ArrayStack ** st,void (*callback)(const AS_DataType));#endif

#include "ArrayStack.h"//init    初始化這個棧
//maxnum:程序員限定的最大元素個數   如果小于等于0   默認10000000
//入棧從_top開始，棧頂元素為_top-1
ArrayStack * ArrayStack_init(int maxnum)
{if(maxnum <= 0) {printf("動動你的豬腦，0和負數能存東西嗎，給你開了10000000，慢慢填吧\n");maxnum = 10000000;}ArrayStack *st = (ArrayStack *)calloc(1,sizeof(ArrayStack));st ->_maxnum = maxnum;//開辟數組  用于保存數據st ->_st_arr = (AS_DataType *)calloc(st ->_maxnum,sizeof(AS_DataType));return st;
}//top     返回棧頂元素，但是不出棧
//返回LS_ERRORVALUE表示失敗
AS_DataType ArrayStack_top(ArrayStack * st)
{if (ArrayStack_empty(st)) {return AS_ERRORVALUE;}return st ->_st_arr[st ->_top - 1];
}//empty   判斷棧是否為空
bool ArrayStack_empty(ArrayStack * st)
{if (!st || st ->_num == 0) {return true;}return false;
}//full    判斷是不是滿了
bool ArrayStack_full(ArrayStack * st)
{if (!st || st ->_num == st ->_maxnum) {return true;}return false;
}//size    棧里面有多少個元素
int ArrayStack_size(ArrayStack * st)
{if (!st) {return AS_ERRORVALUE;}return st ->_num;
}//push    入棧  失敗返回false
bool ArrayStack_push(ArrayStack * st,const AS_DataType data)
{if (!st || ArrayStack_full(st)) {return false;}st ->_st_arr[st ->_top] = data;st ->_top++;st ->_num++;return true;
}//pop     出棧 沒有返回元素  失敗返回false
//如果你有需求返回元素也是可以的
//如果你要得到出棧元素 你需要先top再pop
bool ArrayStack_pop(ArrayStack * st)
{if (ArrayStack_empty(st)) {return false;}st ->_top--;st ->_num--;return true;
}//clear   清空這個棧
//callback是否要處理數據，傳NULL為不處理
void ArrayStack_clear(ArrayStack * st,void (*callback)(const AS_DataType))
{while (!ArrayStack_empty(st)) {ArrayStack_pop(st);}
}//destory 銷魂這個棧
//callback是否要處理數據，傳NULL為不處理
void ArrayStack_destory(ArrayStack ** st,void (*callback)(const AS_DataType))
{free((*st) ->_st_arr);free(*st);*st =NULL;}