一、概念
1.棧只允許在棧頂位置入棧和出棧元素，鏈表可以在任意位置插入和刪除元素，棧和隊列只允許在指定位置插入和刪除元素
2.鏈表、棧和隊列都是一種線性結構（一對一），棧和隊列是一種特殊的表狀結構
二、棧
1.基礎概念
先進后出，后進先出
棧頂：允許入棧和出棧的一端稱為棧頂
棧底：不允許入棧和出棧的一端稱為棧底
入棧（壓棧）：將元素放入棧頂位置
出棧（彈棧）：將棧頂元素取出
棧針：記錄棧頂位置的標記
2.分類：
（1）順序棧：
增棧：棧的方向自低向高增長? ? 減棧：棧的方向自高向低增長
空棧：棧針指向要入棧的位置? ? 滿棧：棧針指向棧頂元素的位置
常見順序棧：?空增棧、空減棧、滿增棧、滿減棧
此圖為空減棧
①順序棧的實現
#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__
typedef int datatype;???????????????? //存放數據的類型
typedef struct stack
{
datatype *pdata; ??????????????//存放數據空間首地址
int top;??????????????????????????????//棧頂元素位置
int tlen;?????????????????????????????//最多存放元素個數
}seqstack;
#endif
②順序棧的創建
申請存放標簽的空間，申請存放數據的空間
seqstack *create_seqstack(int len)
{
seqstack *ptmpstack = NULL;
//申請標簽空間
ptmpstack = malloc(sizeof(seqstack));
if (NULL == ptmpstack)
{
perror("fail to malloc");
return NULL;
}
//申請存放數據的空間
ptmpstack->pdata = malloc(sizeof(datatype) * len);
if (NULL == ptmpstack->pdata)
{
perror("fail to malloc");
return NULL;
}
ptmpstack->top = 0;
ptmpstack->tlen = len;
return ptmpstack;
}
③ 順序棧的銷毀：
銷毀存放數據的空間，銷毀存放標簽的空間
int destroy_seqstack(seqstack **pptmpstack)
{
free((*pptmpstack)->pdata);
free((*pptmpstack));
*pptmpstack = NULL;
return 0;
}
（注意先后順序）
④是否為空棧:棧針為0即為空棧
int is_empty_seqstack(seqstack *ptmpstack)
{
return 0 == ptmpstack->top;
}
⑤是否為滿棧：棧針與tlen相同即為滿棧
int is_full_seqstack(seqstack *ptmpstack)
{
return ptmpstack->tlen == ptmpstack->top;
}
⑥?壓棧：將元素放入棧頂位置，棧針位置++
int push_seqstack(seqstack *ptmpstack, datatype tmpdata)
{
if (is_full_seqstack(ptmpstack))
{
return -1;
}
ptmpstack->pdata[ptmpstack->top++] = tmpdata;
return 0;
}
⑦出棧：棧針位置--，將棧頂元素出棧
datatype pop_seqstack(seqstack *ptmpstack)
{
if (is_empty_seqstack(ptmpstack))
{
return -1;
}
return ptmpstack->pdata[--ptmpstack->top];
}
（2）鏈式棧
使用鏈表的思想實現鏈式棧，參考單向鏈表節點定義，壓棧使用頭插法，出棧返回鏈表第一個有效節點的值，并刪除該節點，在主函數循環出棧，銷毀棧參考單向鏈表的銷毀
linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;
//創建空白節點
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}????????//初始化節點中的值
ptmpnode->pnext = NULL;
//返回空白節點地址
return ptmpnode;
}
/* 判斷順序棧是否為空 */
int is_empty_linkstack(linknode *phead)
{
//判斷空白節點后面還有沒有節點
return NULL == phead->pnext;
}/* 壓棧 */
int push_linkstack(linknode *phead, datatype tmpdata)
{
linknode *ptmpnode = NULL;
//頭插法
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;
return 0;
}/* 出棧 */
datatype pop_linkstack(linknode *phead)
{????????datatype retval;
linknode *ptmpnode = NULL;
if (is_empty_linkstack(phead))
{
return -1;
}????????//刪除第一個有效元素
ptmpnode = phead->pnext;
phead->pnext = ptmpnode->pnext;
retval = ptmpnode->data;
free(ptmpnode);
//返回數據
return retval;}
/* 銷毀棧 */
int destroy_linkstack(linknode **pphead)
{
linknode *ptmpnode = NULL;
linknode *pfreenode = NULL;
ptmpnode = pfreenode = *pphead;
while (ptmpnode != NULL)
{
ptmpnode = ptmpnode->pnext;
free(pfreenode);
pfreenode = ptmpnode;
}
*pphead = NULL;
return 0;
}
三、隊列
1.基礎概念
先進先出，后進后出
隊頭：出隊的一端
隊尾：入隊的一端
入隊：將元素放入隊列末尾
?出隊：將元素從隊頭中取出
2.分類
（1）循環隊列
①定義
typedef int datatype;
typedef struct queue
{
datatype *pdata; ????????//存放數據空間的首地址
int head; ????????????????????//頭下標
int tail; ???????????????????????//尾下標
int tlen; ?????????????????????//最多存放元素個數
}seqqueuee
②循環隊列創建
seqqueue *create_seqqueue(int len)
{
seqqueue *ptmpqueue = NULL;
ptmpqueue = malloc(sizeof(seqqueue));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return NULL;
}
ptmpqueue->pdata = malloc(sizeof(datatype) * len);
if (NULL == ptmpqueue->pdata)
{
perror("fail to malloc");
return NULL;
}????????ptmpqueue->head = 0;
ptmpqueue->tail = 0;
ptmpqueue->tlen = len;
return ptmpqueue;
}
③?循環隊列銷毀
int destroy_seqqueue(seqqueue **pptmpqueue)
{
free((*pptmpqueue)->pdata);
free(*pptmpqueue);
*pptmpqueue = NULL;
return 0;
}
④判斷循環隊列是否為空
int is_empty_seqqueue(seqqueue *ptmpqueue)
{
return ptmpqueue->head == ptmpqueue->tail;
}
⑤?判斷循環隊列是否為滿
1）為避免循環隊列空與滿的條件沖突，犧牲一個存放數據的空間，將tail+1 == head作為判斷隊滿的條件
2）循環隊列如果head或者tail下標超過tlen范圍，需要對tlen取余，保障head和tail的值在隊列下標范圍內變化
int is_full_seqqueue(seqqueue *ptmpqueue)
{
return ((ptmpqueue->tail + 1) % ptmpqueue->tlen) ==
ptmpqueue->head;
}
⑥入隊
int enter_seqqueue(seqqueue *ptmpqueue, datatype tmpdata)
{
if (is_full_seqqueue(ptmpqueue))
{
return -1;
}
ptmpqueue->pdata[ptmpqueue->tail] = tmpdata;
ptmpqueue->tail = (ptmpqueue->tail + 1) % ptmpqueue->tlen;
return 0;
}
⑦出隊
datatype quit_seqqueue(seqqueue *ptmpqueue)
{
datatype retval;
if (is_empty_seqqueue(ptmpqueue))
{
return -1;
}
retval = ptmpqueue->pdata[ptmpqueue->head];
ptmpqueue->head = (ptmpqueue->head + 1) % ptmpqueue->tlen;
return retval;
}
（2）鏈式隊列
使用鏈表的思想實現鏈式隊列，參考單向鏈表節點定義，入隊使用尾插法，出隊返回鏈表第一個有效節點的值，并刪除該節點，在主函數循環出棧隊，銷毀棧參考單向鏈表的銷毀
#include "linkstack.h"
#include <stdio.h>
#include <stdlib.h>linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;? ? ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}? ? ptmpnode->pnext = NULL;
? ? return ptmpnode;
}int is_empty_linkstack(linknode *phead)
{
return NULL == phead->pnext;
}int push_linkstack(linknode *phead, datatype tmpdata)
{
linknode *ptmpnode = NULL;? ? ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}? ? ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;? ? return 0;
}datatype pop_linkstack(linknode *phead)
{
linknode *ptmpnode = NULL;
datatype tmpdata = 0;? ? ptmpnode = phead->pnext;
tmpdata = ptmpnode->data;
phead->pnext = ptmpnode->pnext;
free(ptmpnode);
ptmpnode ?= phead->pnext;?? ? return tmpdata;
}int destory_linkstack(linknode **phead)
{
linknode *ptmpnode = NULL;
linknode *pprenode = NULL;? ? ptmpnode = pprenode = *phead;
while(ptmpnode != NULL)
{
ptmpnode = ptmpnode->pnext;
free(pprenode);
pprenode = ptmpnode;
}
*phead = NULL;? ? return 0;
}
)
