一 、目的：

加深對抽象數(shù)據(jù)類型 ADT 棧和隊列的理解；

二 、環(huán)境：

operating system version：Win11

CPU instruction set:? x64

Integrated Development Environment：Viusal Studio 2022

三 、內(nèi)容：

編寫程序?qū)崿F(xiàn)ADT棧的定義，及常用操作（數(shù)組或指針實(shí)現(xiàn)

1) 生成棧

2) Push

3) Pop

編寫程序?qū)崿F(xiàn)ADT隊列的定義，及常用操作：

1) 生成隊列

2) Enqueues 入列

3) Isempty 判斷是否隊列為空 。

四 、步驟：

1.程序：

Part1：ADT棧的定義及常用操作

#include <stdio.h> #define MAXSIZE 100 typedef struct node { int* base; int* top; int stacksize; }Stack; //聲明棧 int InitStack(Stack& S);//初始化棧 int Push(Stack& S, int e);//聲明Push函數(shù)，實(shí)現(xiàn)壓棧 void Pop(Stack& S);//聲明Pop函數(shù)，實(shí)現(xiàn)出棧 int Get(Stack S);//聲明Get函數(shù)，取出棧 void PrintStack(Stack& S);//聲明PrintStack函數(shù)，輸出所有元素 int main(int argc, char* argv[]) { int num; int Value; int choice; Stack S; if (InitStack(S))//根據(jù)返回值判斷初始棧是否完成 printf("Initialization completed\n"); printf("Enter the number of data to be pushed into the stack:"); scanf_s("%d", &num); printf("Start Push\n");//開始壓棧 for (int n = 0; n < num; n++) { printf("Please enter the data %d :", n + 1); scanf_s("%d", &Value); Push(S, Value); } PrintStack(S); printf("Whether to perform Pop, 0 -> no others -> yes ："); scanf_s("%d", &choice); if (choice) Pop(S); PrintStack(S); return 0; } int InitStack(Stack& S) //初始化棧空間 { S.base = new int[MAXSIZE]; if (!S.base) return 0; S.top = S.base; S.stacksize = MAXSIZE; return 1; } int Push(Stack& S, int e) //壓棧 { if (S.top - S.base == S.stacksize) return 0; S.top++; *S.top = e; return 1; } //出棧 void Pop(Stack& S) //刪除棧頂元素并返回 { printf("The top-of-stack value of %d has been removed\n", *S.top); S.top--; } int Get(Stack S) //取棧 { if (S.top != S.base) return *(S.top - 1); } void PrintStack(Stack& S) //遍歷棧 { int i; if (S.top == S.base) printf("Stack empty\n"); else { printf("The data in the stack is\n"); i = S.top - S.base; for (int j = 0; j < i; j++) { printf("%d\n", *(S.top - j)); } } }

Part2：ADT隊列的定義及常用操作

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct { //定義隊列類型 char data[1001]; int Front; int Rear; int Size; }Queue; void InitQueue(Queue* Q) //初始化隊列 { Q->Front = 0; Q->Rear = 0; Q->Size = 0; } int IsEmpty(Queue* Q) //定義IsEmpty函數(shù)，判斷隊列是否為空 { return Q->Size == 0; } void EnQueue(Queue* Q, int x) //定義EnQueue函數(shù)，進(jìn)行入隊列 { Q->data[Q->Rear] = x; Q->Rear++; Q->Front = Q->Rear - 1; Q->Size++; } int main() { Queue Q; InitQueue(&Q);//初始化隊列 EnQueue(&Q, 5); EnQueue(&Q, 20); EnQueue(&Q, 3); EnQueue(&Q, 5); printf("\nGenerated Queue\n"); int m = Q.Rear; for (int i = 0; i < m; i++) printf("%d ", Q.data[i]); if (IsEmpty(&Q))//判斷是否空隊列 printf("\nEmpty queue\n"); else printf("\nQueue non-empty\n"); int f; for (int k = 4; k < 1001; k++) { printf("\nEnter incoming queue number："); scanf_s("%d", &f); EnQueue(&Q, f); printf("Result："); m = Q.Rear; int i; for (i = 0; i < m; i++) printf("%d ", Q.data[i]); if (IsEmpty(&Q)) printf("\nEmpty queue\n"); else printf("\nQueue non-empty\n"); } return 0; }

2.程序結(jié)果：

棧：

（1）首先進(jìn)行初始化棧測試，這里通過InitStack()函數(shù)返回值來判斷是否初始化成功。若初始化成功，則輸出Initialization completed。

（2）壓棧

輸入測試數(shù)據(jù)2023，可見按照FILO原則，棧內(nèi)保存狀態(tài)為3202.

（3）出棧

在這里將棧頂元素3出棧，然后輸出棧內(nèi)剩余元素，如下圖所示。

綜上，編寫程序?qū)崿F(xiàn)ADT棧的定義及常用操作（數(shù)組或指針實(shí)現(xiàn)

1) 生成棧2) Push 3) Pop

隊列：

（1）生成隊列，如下圖所示

（2）入列操作如下圖所示，這里以15和25為例：

（3）Isempty判斷隊列是否為空，即隊列size是否為0。如下圖所示，可見隊列非空。

編寫程序?qū)崿F(xiàn)ADT隊列的定義，及常用操作：

1) 生成隊列2) Enqueues 入列3) Isempty 判斷是否隊列為空 。

2.分析和改進(jìn)：

在實(shí)現(xiàn)ADT棧的中，完成了最終的生成棧、push和pop的操作，運(yùn)行效果也符合預(yù)期，但是在實(shí)際的分析中我發(fā)現(xiàn)最初的設(shè)計邏輯中在push操作中遺漏了棧空間的限制，在我的小樣本測試中程序運(yùn)行完美，但是若壓棧的輸入數(shù)據(jù)遠(yuǎn)遠(yuǎn)地超過了棧本身的容量，就會不可避免地造成爆棧的情況，因此，在實(shí)際的設(shè)計中還要考慮棧的空間，我后來改用了采用push函數(shù)返回值的判斷方法在一定程度上避免了爆棧的可能。如下：

int Push(Stack& S, int e) //壓棧 { if (S.top - S.base == S.stacksize) return 0; S.top++; *S.top = e; return 1; }

五 小結(jié)：

此次有關(guān)于ADT棧和隊列的實(shí)現(xiàn)，雖然對棧和隊列概念已經(jīng)較為熟悉，但是在實(shí)際的編程中仍然有一些細(xì)節(jié)沒有注意到，例如在壓棧的時候不能一味地考慮壓入以及指針的變化，還應(yīng)該考慮到棧的空間是否足夠，以免出現(xiàn)爆棧的現(xiàn)象。

加強(qiáng)了我對于棧和隊列的理解，也從實(shí)踐的角度很好的掌握了棧和隊列之間的區(qū)別。棧和隊列是兩種常用的數(shù)據(jù)結(jié)構(gòu)，棧和隊列是操作受限的線性表，棧和隊列的數(shù)據(jù)元素具有單一的前驅(qū)和后繼的線性關(guān)系；棧和隊列又是兩種重要的抽象數(shù)據(jù)類型。棧是限定在表尾進(jìn)行插入和刪除操作的線性表允許插入和刪除的一端為棧頂，另一端為棧底，出棧元素只能是棧頂元素，后進(jìn)先出，相鄰元素具有前驅(qū)與后繼關(guān)系。隊列是只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。允許插入的一端為隊尾，允許刪除的一端為隊頭，先進(jìn)先出，相鄰元素具有前驅(qū)與后繼關(guān)系。

總結(jié)

以上是生活随笔為你收集整理的ADT栈与队列的C语言编程与实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。