?
?? 博客內(nèi)容：順序棧的原理詳解
?? 作??者：陳大大陳
?? 個(gè)人簡(jiǎn)介：一個(gè)正在努力學(xué)技術(shù)的準(zhǔn)前段，專注基礎(chǔ)和實(shí)戰(zhàn)分享 ，歡迎私信！
?? 歡迎大家：這里是CSDN，我總結(jié)知識(shí)和寫筆記的地方，喜歡的話請(qǐng)三連，有問題請(qǐng)私信 ?? ?? ??
目錄
順序棧的定義
結(jié)構(gòu)體定義
順序棧的初始化?
判斷順序棧是否為空
求順序棧的長(zhǎng)度
清空順序棧
銷毀順序棧
順序棧的入棧
順序棧的出棧
求棧頂元素
順序棧的遍歷
菜單的打印?
順序棧的代碼實(shí)現(xiàn)
順序棧的定義
棧（stack），是僅限在表尾進(jìn)行插入或者刪除操作的線性表，因此，對(duì)棧來說，表尾端有其特殊含義，稱為棧頂，表頭端則稱為棧底，不含元素的空表稱為空棧。棧的修改是按照后進(jìn)先出的原則進(jìn)行的，因此，棧也被稱為后進(jìn)先出的線性表。
結(jié)構(gòu)體定義
我們定義一個(gè)棧頂指針top和一個(gè)棧底指針base，棧頂指針和棧頂指針一開始指向同一片空間。
所以top==base可以作為?？盏臉?biāo)記。
當(dāng)插入一個(gè)新數(shù)據(jù)時(shí)，棧頂指針加一，刪除一個(gè)元素時(shí)，棧頂指針減一。
所以當(dāng)順序棧非空時(shí)，棧頂指針永遠(yuǎn)在棧頂元素的下一位。
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#define maxsize 100
#define inc 10
typedef struct Sqstack
{
int* base;//棧頂指針
int* top;//棧底指針
int stacksize;//棧的容量
}stack;順序棧的初始化?
上面也說了，順序棧一開始棧頂指針和戰(zhàn)地指針是指向一塊空間的，因此這里就讓棧頂指針和棧底指針相等。
我們使用動(dòng)態(tài)內(nèi)存開辟空間，先給棧一個(gè)默認(rèn)的空間大小。
如果不夠，后面的入棧會(huì)檢測(cè)到并開辟空間。
如果空間開辟失敗，就退出。
void InitStack(stack& s)
{
s.base = (int*)malloc(sizeof(int) * maxsize);
if (!s.base) exit(0);
s.top=s.base;
s.stacksize = maxsize;
}判斷順序棧是否為空
這里沒什么好說的，如果棧頂指針和棧底指針指向同一片空間，那就說明它們中間沒有數(shù)據(jù)，順序棧是空棧。
int isEmpty(stack s)
{
if (s.base==s.top)
{
return 1;
}
return 0;
}求順序棧的長(zhǎng)度
棧頂指針減去棧底指針的值即為順序棧的長(zhǎng)度。
int stacklength(stack s)
{
return s.top - s.base;
}清空順序棧
如果順序棧不是空棧，就讓棧頂指針等于棧底指針，這就在邏輯上清空了順序棧的元素。
如果順序表是空棧，就表明順序棧已經(jīng)清空，不需要重復(fù)操作。
void stackclean(stack& s)
{
if (s.base)
{
s.top = s.base;
printf("順序棧清空成功\n");
}
else
{
printf("順序棧已清空，無需再次重復(fù)操作\n");
}
}銷毀順序棧
我們直接用delete函數(shù)來銷毀棧底指針?biāo)赶虻目臻g，也就是順序棧。
之后不要忘記將棧頂指針和棧底指針置空，否則會(huì)造成內(nèi)存泄露的問題 。
void destorystack(stack& s)
{
if (s.base)
{
delete(s.base);
s.stacksize = 0;
s.base = NULL;
s.top = NULL;
printf("銷毀成功\n");
}
else
{
printf("棧已經(jīng)被銷毀，無需銷毀\n");
}
}順序棧的入棧
當(dāng)順序棧里的空間不夠用的時(shí)候，就需要?jiǎng)討B(tài)的開辟空間。
使用realloc函數(shù)來開辟新的空間，并讓棧底指針指向這一片空間。
需要注意的是，棧頂指針和棧底指針在新空間的位置需要我們重新定義。
stacksize也要加上我們之前定義的增加量。
void push(stack& s,int e)
{
if ((s.top - s.base) >= s.stacksize)
{
s.base = (int*)realloc(s.base, (maxsize + inc) * sizeof(int));
if (!s.base) perror("realloc");
s.top = s.base + s.stacksize;
s.stacksize += inc;
}
else
{
*(s.top) = e;
s.top++;
printf("添加成功\n" );
}
}順序棧的出棧
這里用到了之前判斷順序棧是否為空的函數(shù)。
如果為空，則打印無法彈出。
不為空，先讓棧頂指針減一到棧頂?shù)谝粋€(gè)元素的位置，再將其值復(fù)制給指針變量e。成功彈出元素。
void pop(stack& s,int &e)
{
if (isEmpty(s))
{
printf("棧為空，無法彈出\n");
}
else
{
if (s.top != s.base)
{
s.top--;
e = *(s.top);
printf("成功彈出\n");
}
}
}求棧頂元素
求棧頂元素的操作看起來和出棧的操作一模一樣。
是不是有的小伙伴會(huì)擔(dān)心這里的操作會(huì)把數(shù)據(jù)彈出？？
那你就忽略了一個(gè)點(diǎn)，這里函數(shù)聲明里所傳的是一級(jí)指針，并沒有改變實(shí)參的能力。
也就是說，這里函數(shù)聲明里的形參只是實(shí)參的臨時(shí)拷貝而已。翻不起風(fēng)浪。
int top(stack s)
{
if (isEmpty(s))
{
printf("棧為空，沒有棧頂元素\n") ;
return -1;
}
else
{
s.top--;
return *(s.top);
}
}順序棧的遍歷
這里需要用到上面求長(zhǎng)度的函數(shù)，求出長(zhǎng)度遍歷并打印順序棧元素即可。
void traverse(stack s)
{
int length = stacklength(s);
if (length > 0)
{
for (int i = 0; i < stacklength(s); i++)
{
printf("%d ", s.base[i]);
}
}
else
{
printf("順序棧為空\(chéng)n");
}
}菜單的打印?
void menu()
{
printf("**********************************\n");
printf("1.初始化\n");
printf("2.判斷棧是否為空\(chéng)n");
printf("3.求棧的長(zhǎng)度\n");
printf("4.清空棧\n");
printf("5.銷毀棧\n");
printf("6.入棧\n");
printf("7.出棧\n");
printf("8.求棧頂元素\n");
printf("9.遍歷順序棧\n");
printf( "10.退出\n");
printf( "**********************************\n" );
}順序棧的代碼實(shí)現(xiàn)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
typedef struct Sqstack
{
int* base;//棧頂指針
int* top;//棧底指針
int stacksize;//棧的容量
}stack;
#define maxsize 100
#define inc 10
void InitStack(stack& s)
{
s.base = (int*)malloc(sizeof(int) * maxsize);
if (!s.base) exit(0);
s.top=s.base;
s.stacksize = maxsize;
}
int isEmpty(stack s)
{
if (s.base==s.top)
{
return 1;
}
return 0;
}
int stacklength(stack s)
{
return s.top - s.base;
}
void stackclean(stack& s)
{
if (s.base)
{
s.top = s.base;
printf("順序棧清空成功\n");
}
else
{
printf("順序棧已清空，無需再次重復(fù)操作\n");
}
}
void destorystack(stack& s)
{
if (s.base)
{
delete(s.base);
s.stacksize = 0;
s.base = NULL;
s.top = NULL;
printf("銷毀成功\n");
}
else
{
printf("棧已經(jīng)被銷毀，無需銷毀\n");
}
}
void push(stack& s,int e)
{
if ((s.top - s.base) >= s.stacksize)
{
s.base = (int*)realloc(s.base, (maxsize + inc) * sizeof(int));
if (!s.base) perror("realloc");
s.top = s.base + s.stacksize;
s.stacksize += inc;
}
else
{
*(s.top) = e;
s.top++;
printf("添加成功\n" );
}
}
void pop(stack& s,int &e)
{
if (isEmpty(s))
{
printf("棧為空，無法彈出\n");
}
else
{
if (s.top != s.base)
{
s.top--;
e = *(s.top);
printf("成功彈出\n");
}
}
}
void traverse(stack s)
{
int length = stacklength(s);
if (length > 0)
{
for (int i = 0; i < stacklength(s); i++)
{
printf("%d ", s.base[i]);
}
}
else
{
printf("順序棧為空\(chéng)n");
}
}
int top(stack s)
{
if (isEmpty(s))
{
printf("棧為空，沒有棧頂元素\n") ;
return -1;
}
else
{
s.top--;
return *(s.top);
}
}
void menu()
{
printf("**********************************\n");
printf("1.初始化\n");
printf("2.判斷棧是否為空\(chéng)n");
printf("3.求棧的長(zhǎng)度\n");
printf("4.清空棧\n");
printf("5.銷毀棧\n");
printf("6.入棧\n");
printf("7.出棧\n");
printf("8.求棧頂元素\n");
printf("9.遍歷順序棧\n");
printf( "10.退出\n");
printf( "**********************************\n" );
}
int main()
{
int choice;
stack s;
int e1, e2;
while (1)
{
menu();
scanf("%d",&choice);
switch (choice)
{
case 1:
InitStack(s);
printf( "初始化成功\n" );
break;
case 2:
if (isEmpty(s))
printf("棧為空\(chéng)n" );
else
printf("棧不為空\(chéng)n");
break;
case 3:
printf("棧的長(zhǎng)度為%d\n", stacklength(s));
break;
case 4:
stackclean(s);
break;
case 5:
destorystack(s);
break;
case 6:
printf("請(qǐng)輸入想要入棧的元素值:>");
scanf("%d",&e1);
push(s, e1);
break;
case 7:
pop(s, e2);
printf("彈出的元素為%d\n" ,e2 );
break;
case 8:
if (top(s) != -1)
printf("棧頂元素為%d\n" , top(s) );
break;
case 9:
traverse(s);
printf("\n");
break;
case 10:
printf ( "成功退出\n" );
exit(0);
default:
printf ("輸入有誤，請(qǐng)重新輸入\n" );
break;
}
}
}
運(yùn)行實(shí)例
總結(jié)
??感謝觀看，本文到這里就結(jié)束了，如果覺得有幫助，請(qǐng)給文章點(diǎn)個(gè)贊吧，讓更多的人看到。?? ?? ??
?
??也歡迎你，關(guān)注我。?? ?? ??文章來源：http://www.zghlxwxcb.cn/news/detail-406139.html
??原創(chuàng)不易，還希望各位大佬支持一下，你們的點(diǎn)贊、收藏和留言對(duì)我真的很重要?。。?? ?? ?? 最后，本文仍有許多不足之處，歡迎各位認(rèn)真讀完文章的小伙伴們隨時(shí)私信交流、批評(píng)指正！下期再見。??文章來源地址http://www.zghlxwxcb.cn/news/detail-406139.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)專欄】動(dòng)態(tài)擴(kuò)容順序棧詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
