目錄

一、順序棧

存儲結構

?總代碼

二、兩棧共享空間

存儲結構：

總代碼：

三、鏈棧

存儲結構：

?總代碼：

---

一、順序棧

存儲結構：

棧特點：先進后出，后進先出。（特殊的線性表）

入棧時在棧頂添加元素，出棧時在棧頂刪除元素。（無論進出都始終在棧頂進行操作）

//棧
typedef struct
{int data[MAXSIZE];int top;
}sqStack;
sqStack s;

?總代碼：

//順序棧
//先進先出，入棧時在棧頂加入元素，出棧時在棧頂刪除元素（主要是s.top標志移動即可）
#include <stdio.h>#define MAXSIZE 3
int i = 0, save = 0;typedef struct
{int data[MAXSIZE];int top;
}sqStack;
sqStack s;//棧初始化
void Init_Stack()
{s.top = -1;			//棧頂
}//入棧
void Push(int num)
{if (s.top >= MAXSIZE - 1)							//判斷棧滿{printf("棧已滿，不能繼續添加！\n");return;}s.top++;s.data[s.top] = num;
}//出棧
void Pop()
{if (s.top == -1){printf("棧已空\n");return;}s.top--;
}//遍歷
void Traverse()
{for (i = 0; i <= s.top; i++)printf("%d\n", s.data[i]);
}int main()
{Init_Stack();				//棧初始化Push(0);					//入棧Push(1);Push(2);Pop();						//出棧Pop();Traverse();return 0;
}

二、兩棧共享空間

兩棧共享空間，代碼結構其實是一個棧，兩端都作為頂(top)，都能存儲，節省空間。

存儲結構：

//兩棧共享空間
typedef struct
{int data[MAXSIZE];int top1;int top2;
}Stack;
Stack s;

總代碼：

//兩棧共享空間（節省空間）
//共兩個top，top1指向表頭，top2指向表尾，兩端都能存儲
#include<stdio.h>#define MAXSIZE 20typedef struct
{int data[MAXSIZE];int top1;int top2;
}Stack;
Stack s;void Init_Stack()
{s.top1 = -1;s.top2 = MAXSIZE;
}//入棧
void Push(int num, int choice)
{if (s.top1 + 1 == s.top2){printf("棧已滿！\n");return;}if (choice == 1){s.top1++;s.data[s.top1] = num;}else if (choice == 2){s.top2--;s.data[s.top2] = num;}
}//出棧
int Pop(int choice)
{int num = -2;if (s.top1 == -1 && s.top2 == MAXSIZE){printf("兩棧已空！\n");return -1;}if (choice == 1){if (s.top1 >= 0){num = s.data[s.top1];s.top1--;}else{printf("棧1已空！\n");return -1;}}else if (choice == 2){if (s.top2 < MAXSIZE){num = s.data[s.top2];s.top2++;}else{printf("棧2已空！\n");return -1;}}return num;
}int main()
{Init_Stack();//入棧Push(0, 1);Push(1, 1);Push(2, 2);Push(3, 2);//出棧printf("%d\n", Pop(2));return 0;
}

三、鏈棧

鏈棧和鏈表類似，只不過它的指針(*next)是從棧頂指向棧低(從top指向head)。

存儲結構：

//鏈棧結點
typedef struct Node
{int data;struct Node* next;
}Node;

?總代碼：

//鏈棧
//鏈棧沒有存儲大小限值，可以無限拓展（只要內存夠）
//依然是top指向棧頂元素，但*next由棧頂指向棧底。
#include <stdio.h>
#include <malloc.h>//鏈棧結點
typedef struct Node
{int data;struct Node* next;
}Node;Node* head, * top;//鏈棧初始化
void Init_Stack()
{head = (Node*)malloc(sizeof(Node));top = (Node*)malloc(sizeof(Node));head->next = NULL;top = head;
}//插入元素
void Push(int num)
{Node* p = (Node*)malloc(sizeof(Node));p->data = num;p->next = top;top = p;
}//取出元素
int Pop()
{Node* s = top;top = top->next;return s->data;
}//遍歷元素
void Print()
{Node* p = top;while (p != head){printf("%d\n", p->data);p = p->next;}
}int main()
{Init_Stack();			//初始化Push(0);			//入棧Push(1);Push(2);printf("%d\n", Pop());printf("%d\n", Pop());//Print();return 0;
}

四、計算器(棧應用)

?逆波蘭計算器：中綴表達式轉后綴表達式，利用棧的后進先出/先進后出。利用兩個棧（一個存放數據元素，一個存放運算符元素）。把要放入的運算符和棧頂運算符比較，如果棧頂運算符優先級＞要放入的運算符，則取出棧頂運算符和數據棧頂的兩個元素進行運算，運算結果存入數據棧，要入棧的小優先級運算符存入運算符棧。

前綴、中綴、后綴表達式解釋：

?總代碼

//計算器
//利用兩個棧，一個存放數值，一個存放運算符
//把中綴表達式（平時的正常表達式）轉換為后綴表達式（逆波蘭表達式），利用棧的特性進行計算
//（首）先把數值存入數據棧，再把運算符存入字符棧，繼續存入數值
//碰到運算符時進行判斷，如果優先級比棧頂運算符低，則取出棧頂的運算符、2個數據棧棧頂數值（比如要存入+，棧內的是*，則把*取出來）
//最后再順序全部取出
//附加功能：括號		（如果碰到前括號'('：則不再進行運算符取出，只存入;		碰到后括號')'：恢復正常）
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>#define MAXSIZE 20//數據棧
typedef struct
{double data[MAXSIZE];int top;
}doubleStack;
doubleStack* d;//運算符棧
typedef struct
{char data[MAXSIZE];int top;
}charStack;
charStack* c;//初始化
void InitStack()
{d = (doubleStack*)malloc(sizeof(doubleStack));c = (charStack*)malloc(sizeof(charStack));d->top = -1;c->top = -1;
}//double型進棧
void dou_Push(double num)
{if (d->top >= MAXSIZE){printf("棧已滿！\n");return;}d->top++;d->data[d->top] = num;
}//字符型進棧
void ch_Push(char ch)
{if (c->top >= MAXSIZE){printf("棧已滿！\n");return;}c->top++;c->data[c->top] = ch;
}//double型出棧
double dou_Pop()
{double temp;if (d->top == -1){printf("棧空！\n");return 0.0;}temp = d->data[d->top];d->top--;return temp;
}//字符型出棧
char ch_Pop()
{char ch;if (c->top == -1){printf("棧空！\n");return 0.0;}ch = c->data[c->top];c->top--;return ch;
}//棧頂運算符優先級
int topPriority()
{if (c->data[c->top] == '*' || c->data[c->top] == '/')			//最高級return 0;else if (c->data[c->top] == '+' || c->data[c->top] == '-')	//最低級return 1;elsereturn 2;				//什么都沒有
}//當前運算符優先級
int nowPriority(char ch)
{if (ch == '*' || ch == '/')			//最高級return 0;else if (ch == '+' || ch == '-')	//最低級return 1;elsereturn 2;
}//清空字符串數組
void Clear_ch(char* ch_a)
{int i = 0;while (ch_a[i] != '\0'){ch_a[i] = ' ';i++;}
}//計算的結果
double Compute(double num1, double num2, char ch_now)
{double result = 0;switch (ch_now){case '*':result = num1 * num2;return result;case '/':result = num2 / num1;return result;case '+':result = num1 + num2;return result;case '-':result = num2 - num1;return result;default:return -1;}
}int main()
{int i = 0, flag = 0;double num = 0, result = 0, sum = 0, num1, num2;char ch = ' ', ch_now, ch_a[MAXSIZE] = { ' ' };InitStack();printf("請輸入一個中綴運算符表達式：\n");while (ch != '\n'){scanf_s("%c", &ch);if ((ch >= '0' && ch <= '9') || ch == '.')							//數字0~9及小數點'.'{i++;ch_a[i] = ch;}else if (ch == '*' || ch == '/' || ch == '+' || ch == '-')		//字符'*'、'/'、'+'、'-'{i = 0;//把數字放入棧num = atof(ch_a);							//字符型轉double型dou_Push(num);//把運算符放入棧if (topPriority() < nowPriority(ch) && flag == 0){ch_now = ch_Pop();			//彈出棧頂運算符num1 = dou_Pop();			//彈出棧頂元素1num2 = dou_Pop();			//彈出棧頂元素2result = Compute(num1, num2, ch_now);dou_Push(result);				//入棧ch_Push(ch);						//入棧}else if (topPriority() >= nowPriority(ch) || flag == 1){ch_Push(ch);			//入棧}Clear_ch(ch_a);								//清空字符串數組	}else if (ch == '(')		//進入括號內flag = 1;else if (ch == ')')		//出括號flag = 0;}//把最后的數字放入棧num = atof(ch_a);dou_Push(num);//最后取出所有元素while (c->top != -1){ch_now = ch_Pop();			//彈出棧頂運算符num1 = dou_Pop();			//彈出棧頂元素1num2 = dou_Pop();			//彈出棧頂元素2result = Compute(num1, num2, ch_now);dou_Push(result);}//最后的計算printf("%lf\n", result);return 0;
}

總結

以上是生活随笔為你收集整理的数据结构与算法（3-1）栈（顺序栈、两栈共享空间、链栈、栈的计算器）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。