個人主頁：【??個人主頁】
系列專欄：【??數(shù)據(jù)結(jié)構(gòu)與算法】
學習名言：天子重英豪，文章教兒曹。萬般皆下品，惟有讀書高
系列文章目錄
第一章 ?? 學前知識
第二章 ?? 單向鏈表
第三章 ?? 遞歸
前言
相信大家小時后一定玩過玩具槍吧，在我們裝子彈時玩具槍的子彈只能從彈夾的一端進并且從同一端出來，這種特殊的結(jié)構(gòu)在我們數(shù)據(jù)結(jié)構(gòu)的世界稱為——棧
一.棧是什么？??????
棧(stack )是限定僅在表尾進行插人或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂(top)，相應地，表頭端稱為棧底( bttom)。不含元素的空表稱為空棧。
假設(shè)棧S= (a1,a2,… , an),則稱a1為棧底元素，an為棧頂元素。棧中元素按a1, a2, …,an的次序進棧，退棧的第一個元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的，因此,棧又稱為后進先出( Last In First Out, LIFO) 的線性表。
二、棧與線性表的關(guān)系??????
棧是一種重要的線性結(jié)構(gòu)。從數(shù)據(jù)結(jié)構(gòu)角度看，棧也是線性表，其特殊性在于棧的基本操作是線性表操作的子集，它們是操作受限的線性表，因此，可稱為具有限定性的數(shù)據(jù)結(jié)構(gòu)。但從數(shù)據(jù)類型角度看，它是和線性表不相同的兩類重要的抽象數(shù)據(jù)類型。
三、棧的基本操作??????
1.棧的儲存結(jié)構(gòu)結(jié)構(gòu)??
typedef int Elemtype;
typedef struct
{
Elemtype* top;//指向棧頂?shù)闹羔?/span>
Elemtype* base;//指向棧底的指針
int log;//存儲當前棧的最大容量
}snake;
2.棧的初始化?
void Creat(snake* a)
{
a->base = (Elemtype*)malloc(sizeof(int) * MAX);//
if (a == NULL)
exit(0);
a->top = a->base;
a->log = MAX;
}
3. 入棧??
void Push(snake* a, Elemtype o)
{
if (a->top - a->base >= a->log)//如果棧已滿則需擴容
{
a->base = (Elemtype*)realloc(a->base, sizeof(Elemtype) * (a->log + MAX));//擴充到原來的一倍
a->top = a->log + MAX;//重新指向未增容前的棧頂
a->log = a->log + MAX;//記入擴大前的容量
if (!a->base)
exit(0);
}
*(a->top) =o;//賦值
a->top++;//指向下一個
}
4.出棧??
Elemtype pop(snake* a, Elemtype *e)
{
if (a->top == a->base)
return 0;//棧已空
*e = *--(a->base);//先指向棧的第一個元素，并取出元素
return *e;//返回
}
5.清空與銷毀??
void QingKong(snake* a)
{
a->top = a->base;
a->log = MAX;
}//清空一個棧，棧本身沒有消失
void Destroy(snake* a)
{
int i, len;
len = a->log;
for (i = 0;i < len;i++)
{
free(a->base);
a->base++;
}
a->base = a->top = NULL;
a->log = 0;
}
總結(jié)??????
順序棧是指利用順序存儲結(jié)構(gòu)實現(xiàn)的棧，即利用一組 地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指針top指示棧頂元素在順序棧中的位置。通常習慣的做法是:以top= 0表示空棧，鑒于C語言中數(shù)組的下標約定從0開始，則當以C語言作描述語言時，如此設(shè)定會帶來很大不便，因此另設(shè)指針base指示棧底元素在順序棧中的位置。當top和base的值相等時，表示空棧。文章來源：http://www.zghlxwxcb.cn/news/detail-405114.html
#include<string.h>
#include<stdlib.h>
#define MAX 100//一次的最大容量
typedef int Elemtype;
typedef struct
{
Elemtype* top;//指向棧頂?shù)闹羔?/span>
Elemtype* base;//指向棧底的指針
int log;//存儲當前棧的最大容量
}snake;
void Creat(snake* a)
{
a->base = (Elemtype*)malloc(sizeof(int) * MAX);//
if (a == NULL)
exit(0);
a->top = a->base;
a->log = MAX;
}
void Push(snake* a, Elemtype o)
{
if (a->top - a->base >= a->log)//如果棧已滿則需擴容
{
a->base = (Elemtype*)realloc(a->base, sizeof(Elemtype) * (a->log + MAX));//擴充到原來的一倍
a->top = a->log + MAX;//重新指向未增容前的棧頂
a->log = a->log + MAX;//記入擴大前的容量
if (!a->base)
exit(0);
}
*(a->top) =o;//賦值
a->top++;//指向下一個
}
Elemtype pop(snake* a, Elemtype *e)
{
if (a->top == a->base)
return 0;//棧已空
*e = *--(a->base);//先指向棧的第一個元素，并取出元素
return *e;//返回
}
void QingKong(snake* a)
{
a->top = a->base;
a->log = MAX;
}//清空一個棧，棧本身沒有消失
void Destroy(snake* a)
{
int i, len;
len = a->log;
for (i = 0;i < len;i++)
{
free(a->base);
a->base++;
}
a->base = a->top = NULL;
a->log = 0;
}
int Snakelen(snake* a)
{
return (a->top - a->top);
}//計算棧的當前容量
int main()
{
snake* a;//創(chuàng)建棧
Creat(a);//賦值
return 0;
}
（文章中圖片與部分內(nèi)容來源與網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系刪除)
文章來源地址http://www.zghlxwxcb.cn/news/detail-405114.html
到了這里，關(guān)于棧的定義及基本操作實現(xiàn)（順序棧）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
