一、堆疊(Stack)的介紹
堆疊（stack）又名堆疊，它是一種運算受限的線性表，限定僅在表尾進行插入和洗掉操作的線性表，這一端被稱為堆疊頂，相對地，把另一端稱為堆疊底，向一個堆疊插入新元素又稱作進堆疊、入堆疊或壓堆疊，它是把新元素放到堆疊頂元素的上面，使之成為新的堆疊頂元素；從一個堆疊洗掉元素又稱作出堆疊或退堆疊，它是把堆疊頂元素洗掉掉，使其相鄰的元素成為新的堆疊頂元素，
二、具體
1、添加相關頭檔案
#include <stdio.h>
#include <stdlib.h>
#include <time.h>2、定義堆疊
typedef struct Stack {
int *data;
int top, size;
} Stack;3、初始化堆疊
Stack *init(int n) {
Stack *s = (Stack *)malloc(sizeof(Stack));
s->data = https://www.cnblogs.com/HanaKoo/archive/2022/04/04/(int *)malloc(sizeof(int) * n);
s->size = n;
s->top = -1;
return s;
}4、判斷是否為空及查看堆疊頂
int empty(Stack *s) {
return s->top == -1;
}
int top(Stack *s) {
if (empty(s)) return 0;
return s->data[s->top];
}5、插入
int push(Stack *s, int val) {
if (s == NULL) return 0;
if (s->top + 1 == s->size) return 0;
s->top += 1;
s->data[s->top] = val;
return 1;
}6、出堆疊操作
int pop(Stack *s) {
if (s == NULL) return 0;
if (empty(s)) return 0;
s->top -= 1;
return 1;
}7、清空
void clear(Stack *s) {
if (s == NULL) return ;
free(s->data);
free(s);
return ;
}8、輸出堆疊
void output(Stack *s) {
printf("stack(%d) = [", s->top + 1);
for (int i = s->top; i >= 0; i--) {
printf(" %d", s->data[i]);
}
printf("]\n");
return ;
}9、主函式（隨機進行20次隨機測驗）
int main() {
srand(time(0));
#define MAX_OP 20
Stack *s = init(MAX_OP);
for (int i = 0; i < MAX_OP; i++) {
int op = rand() % 2, val = rand() % 100;
switch (op) {
case 0: {
printf("push %d to stack = %d\n", val, push(s, val));
} break;
case 1: {
printf("pop %d from stack = %d\n", top(s), pop(s));
}
}
output(s);
}
return 0;
}10、完整代碼
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Stack {
int *data;
int top, size;
} Stack;
Stack *init(int n) {
Stack *s = (Stack *)malloc(sizeof(Stack));
s->data = https://www.cnblogs.com/HanaKoo/archive/2022/04/04/(int *)malloc(sizeof(int) * n);
s->size = n;
s->top = -1;
return s;
}
int empty(Stack *s) {
return s->top == -1;
}
int top(Stack *s) {
if (empty(s)) return 0;
return s->data[s->top];
}
int push(Stack *s, int val) {
if (s == NULL) return 0;
if (s->top + 1 == s->size) return 0;
s->top += 1;
s->data[s->top] = val;
return 1;
}
int pop(Stack *s) {
if (s == NULL) return 0;
if (empty(s)) return 0;
s->top -= 1;
return 1;
}
void clear(Stack *s) {
if (s == NULL) return ;
free(s->data);
free(s);
return ;
}
void output(Stack *s) {
printf("stack(%d) = [", s->top + 1);
for (int i = s->top; i >= 0; i--) {
printf(" %d", s->data[i]);
}
printf("]\n");
return ;
}
int main() {
srand(time(0));
#define MAX_OP 20
Stack *s = init(MAX_OP);
for (int i = 0; i < MAX_OP; i++) {
int op = rand() % 2, val = rand() % 100;
switch (op) {
case 0: {
printf("push %d to stack = %d\n", val, push(s, val));
} break;
case 1: {
printf("pop %d from stack = %d\n", top(s), pop(s));
}
}
output(s);
}
return 0;
}
三、堆疊的基本概念
要搞清楚這個概念，首先要明白”堆疊“原來的意思，如此才能把握本質，堆疊,存盤貨物或供旅客住宿的地方,可引申為倉庫、中轉站，所以引入到計算機領域里，就是指資料暫時存盤的地方，所以才有進堆疊、出堆疊的說法， 首先系統或者資料結構堆疊中資料內容的讀取與插入（壓入)push和 彈出pop是兩回事！壓入是增加資料，彈出是洗掉資料 ，這些操作只能從堆疊頂即最低地址作為約束的介面界面入手操作 ，但讀取堆疊中的資料是隨便的，沒有介面約束之說，很多人都誤解這個理念從而對堆疊產生困惑，而系統堆疊在計算機體系結構中又起到一個跨部件互動的媒介區域的作用 即 cpu 與記憶體的交流通道 ，cpu只從系統給我們自己撰寫的應用程式所規定的堆疊入口線性地讀取執行指令， 用一個形象的詞來形容它就是pipeline（管道線、流水線），cpu內部互動具體參見 EU與BIU的概念介紹， 堆疊作為一種資料結構，是一種只能在一端進行插入和洗掉操作的特殊線性表，它按照后進先出的原則存盤資料，先進入的資料被壓入堆疊底，最后的資料在堆疊頂，需要讀資料的時候從堆疊頂開始彈出資料（最后一個資料被第一個讀出來），堆疊具有記憶作用，對堆疊的插入與洗掉操作中，不需要改變堆疊底指標， 堆疊是允許在同一端進行插入和洗掉操作的特殊線性表，允許進行插入和洗掉操作的一端稱為堆疊頂(top)，另一端為堆疊底(bottom)；堆疊底固定，而堆疊頂浮動；堆疊中元素個數為零時稱為空堆疊，插入一般稱為進堆疊（PUSH），洗掉則稱為退堆疊（POP），堆疊也稱為先進后出表， 堆疊可以用來在函式呼叫的時候存盤斷點，做遞回時要用到堆疊！ 以上定義是在經典計算機科學中的解釋， 在計算機系統中，堆疊則是一個具有以上屬性的動態記憶體區域，程式可以將資料壓入堆疊中，也可以將資料從堆疊頂彈出，在i386機器中，堆疊頂由稱為esp的暫存器進行定位，壓堆疊的操作使得堆疊頂的地址減小，彈出的操作使得堆疊頂的地址增大， 堆疊在程式的運行中有著舉足輕重的作用，最重要的是堆疊保存了一個函式呼叫時所需要的維護資訊，這常常稱之為堆疊幀或者活動記錄，堆疊幀一般包含如下幾方面的資訊： 1．函式的回傳地址和引數 2． 臨時變數：包括函式的非靜態區域變數以及編譯器自動生成的其他臨時變數，如果有任何問題請留言
Love for Ever Day轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/455598.html
標籤：其他
上一篇：Ncrystal Skill設計