堆棧與隊列是兩種重要的基礎數據結構，一個是先入后出，一個是先入先出，有著廣泛的應用，本文分別使用數組與鏈表實現堆棧與隊列

順序存儲方式實現堆棧

#define MaxSize 20 #define ERROR -1 typedef struct {int Data[MaxSize];int Top; } Stack;Stack *CreateStack( int maxSize)//： 生成空堆棧，其最大長度為MaxSize； {Stack *s=(Stack*)malloc(sizeof(Stack)*maxSize);s->Top=-1;return s; } int IsFull( Stack *S, int maxSize)//：判斷堆棧S是否已滿； {if (S->Top==maxSize-1){return 1;}else{return 0;} } void Push( Stack *S, int item )//：將元素item壓入堆棧； {if (S->Top==MaxSize-1){printf("the stack is full");return;}else{S->Data[++(S->Top)]=item;return;}} int IsEmpty ( Stack *S )//：判斷堆棧S是否為空； {if (S->Top=-1){return 1;}else{return 0;} } int Pop( Stack *S )//：刪除并返回棧頂元素； {if (S->Top==-1){printf("the stack is empty");return ERROR;}else{return S->Data[(S->Top)--];} }void show(Stack *s) {int i;for(i=0;i<=s->Top;i++){printf("%d ",s->Data[i]);} }void main() {int a,b;Stack *s=CreateStack(MaxSize);while (1){printf("please enter your order:");scanf("%d",&a);switch (a){case 1:scanf("%d",&b);Push(s,b);break;case 2:Pop(s);break;case 3:show(s);break;case 4:exit(0);break;default:break;}}}

鏈式堆棧

typedef struct Node{int Data;struct Node *Next; } LinkStack;LinkStack *CreateStack() {LinkStack *s=(LinkStack*)malloc(sizeof(LinkStack));s->Next=NULL;return s; }int IsEmpty(LinkStack *s) {return (s->Next==NULL); }void Push( int item, LinkStack *S ) {LinkStack *TmpCell;TmpCell=(LinkStack*)malloc(sizeof(LinkStack));TmpCell->Data=item;TmpCell->Next=S->Next;S->Next=TmpCell;}int pop(LinkStack *s) {LinkStack *firstItem;int topNum;if (IsEmpty(s)){printf("stack is empty");return NULL;}firstItem=s->Next;s->Next=firstItem->Next;topNum=firstItem->Data;free(firstItem);return topNum;} void show(LinkStack *s) {s=s->Next;while (s){printf("%d ",s->Data);s=s->Next;} }void main() {int a,b;LinkStack *s=CreateStack();while (1){printf("please enter your order:");scanf("%d",&a);switch (a){case 1:scanf("%d",&b);Push(b,s);break;case 2:pop(s);break;case 3:show(s);break;case 4:exit(0);break;default:break;}} }

順序存儲隊列

#define MaxSize 20 #define ERROR -1 typedef struct {int Data[ MaxSize ];int rear;int front; } Queue;void AddQ( Queue *PtrQ, int item) {if ((PtrQ->rear+1)%MaxSize==PtrQ->front){printf("the queue is full");}else{PtrQ->rear=(PtrQ->rear+1)%MaxSize;PtrQ->Data[PtrQ->rear]=item;} }int DeleteQ ( Queue *PtrQ ) {if (PtrQ->front==PtrQ->rear){printf("the queue is empty");}else{PtrQ->front=(PtrQ->front+1)%MaxSize;return PtrQ->Data[PtrQ->front-1];} } void show(Queue *PtrQ) {int i;for(i=PtrQ->front+1;i<=PtrQ->rear;i++){printf("%d ",PtrQ->Data[i%MaxSize]);} }void main() {int a,b;Queue *q=(Queue*)malloc(sizeof(Queue));q->front=-1;q->rear=-1;while (1){printf("please enter your order:");scanf("%d",&a);switch (a){case 1:scanf("%d",&b);AddQ(q,b);break;case 2:DeleteQ(q);break;case 3:show(q);break;case 4:exit(0);break;default:break;}} }

鏈式隊列

#define ERROR -1 typedef struct Node{int Data;struct Node *Next; }QNode; typedef struct { /* 鏈隊列結構 */QNode *rear; /* 指向隊尾結點 */QNode *front; /* 指向隊頭結點 */ } LinkQueue;LinkQueue* AddQuee(LinkQueue *PtrL,int item) {QNode *node;node=PtrL->rear;if (PtrL->front==NULL){QNode *q=(QNode*)malloc(sizeof(QNode));q->Next=NULL;q->Data=item;PtrL->front=q;PtrL->rear=q;return PtrL;}else{QNode *q=(QNode*)malloc(sizeof(QNode));q->Next=NULL;q->Data=item;node->Next=q;PtrL->rear=q;return PtrL;} }int DeleteQ ( LinkQueue *PtrQ ) {QNode *firstNode;int NodeItem;if (PtrQ->front==NULL){printf("queue is empty");return ERROR;}firstNode=PtrQ->front;if (PtrQ->front==PtrQ->rear){PtrQ->front=PtrQ->rear=NULL;}else{PtrQ->front=PtrQ->front->Next;}NodeItem=firstNode->Data;free(firstNode);return NodeItem; }void show(LinkQueue *q) {QNode *node;node=q->front;while (node){printf("%d ",node->Data);node=node->Next;} }void main() {int a,b;LinkQueue *q=(LinkQueue*)malloc(sizeof(LinkQueue));q->front=NULL;q->rear=NULL;while (1){printf("please enter your order:");scanf("%d",&a);switch (a){case 1:scanf("%d",&b);q=AddQuee(q,b);break;case 2:DeleteQ(q);break;case 3:show(q);break;case 4:exit(0);break;default:break;}} }

總結

以上是生活随笔為你收集整理的数据结构之堆栈与队列的全部內容，希望文章能夠幫你解決所遇到的問題。

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