数据结构与算法（C语言） | 栈和队列——栈(自己做过测试)
棧是一種重要的線性結構，通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。（后進先出）
–棧的元素必須“后進先出”。
–棧的操作只能在這個線性表的表尾進行。
–注：對于棧來說，這個表尾稱為棧的棧頂（top），相應的表頭稱為棧底（bottom）。
?因為棧的本質是一個線性表，線性表有兩種存儲形式，那么棧也有分為棧的順序存儲結構和棧的鏈式存儲結構。
?最開始棧中不含有任何數據，叫做空棧，此時棧頂就是棧底。然后數據從棧頂進入，棧頂棧底分離，整個棧的當前容量變大。數據出棧時從棧頂彈出，棧頂下移，整個棧的當前容量變小。
?
//棧的順序存儲結構
typedef struct
{
? ? ElemType *base;
? ? ElemType *top;
? ? int stackSize;
}sqStack;
?????????????????????????????????????????????????????????????順序棧
//----- 棧的動態分配順序存儲結構 -----
#define STACK_INIT_SIZE 100 ? //順序棧初始容量
#define STACKINCREMENT ?10 ? ? //順序棧容量增量
typedef struct {
? ? SElemType ?*base; ? ? //順序棧基地址(棧底指針)
? ? SElemType ?*top; ? ? ? //棧頂指針
? ? int ? ? ? ? ? ?stacksize; ? ?//順序棧當前存儲容量
}SqStack;
初始化
//----- 基本操作的算法描述 -----
Status InitStack( SqStack &S ) {
? ? // 構造一個空棧 S
? ? S.base=(SElemType*)malloc
? ? ? ? ? ? ? ? ?(STACK_INIT_SIZE*sizeof(SElemType));
? ? if ?(!S.base) exit(OVERFLOW); ? ?// 存儲分配失敗
? ? S.top = S.base; ?
? ? S.stacksize = STACK_INIT_SIZE; ??
? ? return OK;
}//InitStack?
返回棧頂元素
Status GetTop( SqStack S, SElemType &e ) {
? ? // 若棧不空，則用 e 返回 S 的棧頂元素，并返回 OK;
? ? ?// 否則返回 ERROR
? ? if ?(S.top = = S.base) ?return ERROR;
? ? e = *(S.top-1); ?
? ? return OK;
}//GetTop?
壓入棧
Status Push( SqStack &S, ?SElemType e ) {
? ? // 在棧 S 中插入元素 e 為新的棧頂元素
? ? if (S.top-S.base>=S.stacksize) { // 棧滿，追加存儲空間?
? ? ? ?newbase=(SElemType*)realloc(S.base, ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
? ? ? ?if ?(!newbase) exit(OVERFLOW); ? ?// 存儲分配失敗
? ? ? ?S.base = newbase;
? ? ? ?S.top = S.base+S.stacksize; ?
? ? ? ?S.stacksize += STACKINCREMENT;?
? ? }
? ? *S.top++ = e; ?
? ? return OK;
}//Push?
彈出棧
Status Pop( SqStack S, SElemType &e ) {
? ? // 若棧不空，則刪除 S 的棧頂元素，用 e 返回其值,
? ? ?// 并返回 OK; 否則返回 ERROR
? ? if ?(S.top = = S.base) ?return ERROR;
? ? e = *--S.top; ?
? ? return OK;
}//Pop?
????????
注：c語言中->和.的區別——->用于指針， .用于對象
"->"用于指向結構成員，它的左邊應為指向該結構類型的指針（結構指針），而"."的左邊應為該結構類型的變量（結構變量），如已定義了一個結構體struct student，里面有一個int a；然后有一個結構體變量struct student stu及結構體變量指針struct student *p；且有p=&stu，那么p->a和stu.a表示同一個意思。
?
????????????????????????????????????????????????????
實例分析：
?題目：利用棧的數據結構特點，將二進制轉換為十進制數。
?分析：地球人都知道，二進制數是計算機數據的存儲形式，它是由一串0和1組成的，每個二進制數轉換成相應的十進制數方法如下：
(XnXn-1……X3X2X1)2 = X1*2^0+X2*2^1+…+Xn*2^(n-1)
?一個二進制數要轉換為相應的十進制數，就是從最低位起用每一位去乘以對應位的積，也就是說用第n位去乘以2^(n-1)，然后全部加起來。
由于棧具有后進先出的特性，例如我們輸入11001001這樣的二進制數
?
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
?
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
?
typedef char ElemType;
typedef struct
{
? ? ElemType *base;
? ? ElemType *top;
? ? int stackSize;
}sqStack;
?
void InitStack(sqStack *s)
{
? ? s->base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
? ? if(!s->base)
? ? {
? ? ? ? exit(0);
? ? }
? ? s->top = s->base;
? ? s->stackSize = STACK_INIT_SIZE;
}
?
void Push(sqStack *s,ElemType e)
{
? ? if(s->top-s->base >= s->stackSize )
? ? {
? ? ? ? s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT)*sizeof(ElemType));
? ? ? ? if(!s->base)
? ? ? ? {
? ? ? ? ? ? exit(0);
? ? ? ? }
? ? s->top = s->base + s->stackSize;
? ? s->stackSize = s->stackSize + STACKINCREMENT;
? ? }
? ? *(s->top) = e;
? ? s->top++;
?
}
void Pop(sqStack *s,ElemType *e)
{
? ? if(s->top == s->base)
? ? {
? ? ? ? return;
? ? }
? ? *e = *--(s->top);
}
?
int StackLen(sqStack s)
{
? ? return (s.top - s.base);
? ? //不是地址的相減而是內容
}
int main()
{
? ? ElemType c;
? ? sqStack s;
? ? int len, i, sum = 0;
? ? InitStack(&s);
? ? printf("請輸入二進制書，輸入#符號表示結束！\n");
? ? scanf("%c",&c);
? ? while(c!= '#')
? ? {
? ? ? ? Push(&s, c);
? ? ? ? scanf("%c",&c);
? ? }
? ? //清理鍵盤緩沖區 回車的ASCII=10
? ? getchar();
? ? len = StackLen(s);
? ? printf("棧的當前容量是：%d\n",len);
? ? for(i=0; i<len ; i++)
? ? {
? ? ? ? Pop(&s,&c);
? ? ? ? sum = sum + (c-48) * pow(2, i);
? ? }
? ? printf("轉化為十進制為：%d \n",sum);
? ? return 0;
}
二進制轉化為八進制、二進制轉化為十六進制：
二進制每三位轉化為一個八進制
修改一下以上的主函數部分：
int main()
{
? ? ElemType c;
? ? sqStack s1;
? ? sqStack s2;
? ? int len, i, j, sum = 0;
?
? ? InitStack(&s1); // 初始化棧s1，用來存放二進制輸入
?
? ? printf("請輸入二進制數，輸入‘#’號表示結束！\n\n");
? ? scanf("%c", &c);
? ? while( c != '#' )
? ? {
? ? ? ? if( c=='0' || c=='1' ) ?// 檢查輸入是否二進制
? ? ? ? ? ? Push(&s1, c);
? ? ? ? scanf("%c", &c);
? ? }
? ? getchar(); ? ? ?// 把'\n'從緩沖區去掉
? ? len = StackLen(s1);
?
? ? InitStack(&s2); // 初始化棧s2，用來存放轉換的八進制
?
? ? for( i=0; i < len; i+=3 )
? ? {
? ? ? ? for( j=0; j < 3; j++ )
? ? ? ? {
? ? ? ? ? ? Pop( &s1, &c ); // 取出棧頂元素
? ? ? ? ? ? sum = sum + (c-48) * pow(2, j);
?
? ? ? ? ? ? if( s1.base == s1.top )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
?
? ? ? ? Push( &s2, sum+48 );
? ? ? ? sum = 0;
? ? }
?
? ? printf("\n轉化為八進制數是: ");
? ? while( s2.base != s2.top )
? ? {
? ? ? ? Pop( &s2, &c );
? ? ? ? printf("%c", c);
? ? }
? ? printf("(O)\n");
?
? ? return 0;
}
二進制每四位有一個十六進制與之呼應
int main()
{
? ? ElemType c;
? ? sqStack s1;
? ? sqStack s2;
? ? int len, i, j, sum = 0;
?
? ? InitStack(&s1); // 初始化棧s1，用來存放二進制輸入
?
? ? printf("請輸入二進制數，輸入‘#’號表示結束！\n\n");
? ? scanf("%c", &c);
? ? while( c != '#' )
? ? {
? ? ? ? if( c=='0' || c=='1' ) ?// 檢查輸入是否二進制
? ? ? ? ? ? Push(&s1, c);
? ? ? ? scanf("%c", &c);
? ? }
? ? getchar(); ? ? ?// 把'\n'從緩沖區去掉
? ? len = StackLen(s1);
?
? ? InitStack(&s2); // 初始化棧s2，用來存放轉換的八進制
?
? ? for( i=0; i < len; i+=4 )
? ? {
? ? ? ? for( j=0; j < 4; j++ )
? ? ? ? {
? ? ? ? ? ? Pop( &s1, &c ); // 取出棧頂元素
? ? ? ? ? ? sum = sum + (c-48) * pow(2, j);
?
? ? ? ? ? ? if( s1.base == s1.top )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
?
? ? ? ? switch( sum )
? ? ? ? {
? ? ? ? ? ? case 10: sum = 'A'; break;
? ? ? ? ? ? case 11: sum = 'B'; break;
? ? ? ? ? ? case 12: sum = 'C'; break;
? ? ? ? ? ? case 13: sum = 'D'; break;
? ? ? ? ? ? case 14: sum = 'E'; break;
? ? ? ? ? ? case 15: sum = 'F'; break;
? ? ? ? ? ? default: sum += 48;
? ? ? ? }
?
? ? ? ? Push( &s2, sum );
? ? ? ? sum = 0;
? ? }
?
? ? printf("\n轉化為十六進制數是: ");
? ? while( s2.base != s2.top )
? ? {
? ? ? ? Pop( &s2, &c );
? ? ? ? printf("%c", c);
? ? }
? ? printf("(H)\n");
?
? ? return 0;
}
???????????????????????????????????????????????????????????鏈式棧
?
teypedef struct StackNode
{
ElemType data;?? ?// 存放棧的數據
struct StackNode *next;
} StackNode, *LinkStackPtr;
teypedef struct LinkStack
{
LinkStackPrt top;?? ?// top指針
int count;?? ??? ?// 棧元素計數器
}
?
?
實踐：計算數學表達式(1-2)*(4+5)
簡介：逆波蘭表達式
——后來，在20世紀三十年代，波蘭邏輯學家Jan.Lukasiewicz不知道是像牛頓一樣被蘋果砸到腦袋而想到萬有引力原理，或者還是像阿基米德泡在浴缸里突發奇想給皇冠是否純金做驗證，總之他也是靈感閃現了，然后發明了一種不需要括號的后綴表達式，我們通常把它稱為逆波蘭表達式(RPN) 。
?如果用逆波蘭表示法，應該是這樣：1 2 – 4 5 + *
實現對逆波蘭輸入的表達式進行計算，并且支持帶小數點的數據。
---------------------?
linux上面編譯的時候需要加上-lm選項，因為上面的類引用了#include <math.h>
gcc zhan.c -o zhan -lm
作者：Shannon333?
來源：CSDN?
原文：https://blog.csdn.net/qq_35924276/article/details/81384826?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！
總結
以上是生活随笔為你收集整理的数据结构与算法（C语言） | 栈和队列——栈(自己做过测试)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 埃塞俄比亚首都是哪里（埃塞俄比亚首都）
- 下一篇： gcc - lm的含义