學習随記三——順序棧和鍊棧的定義和基本運算

順序棧和鍊棧的定義和基本運算

1. 順序棧和鍊棧的差別

   （1）、順序棧是事先确定好大小的，鍊棧是動态的，它們的差別類似于數組和連結清單

   （2）、存儲空間不同，順序棧是一塊連續的存儲空間，鍊棧是不連續的存儲空間，也類似于數組和連結清單

   順序棧和鍊棧更像是運算受限制的數組和連結清單

2. 順序棧的定義和基本運算

#include<stdio.h>
const int StackSize=100;	//确定棧的大小
typedef struct Stack{
	int data[StackSize];		//資料域 
	int top;		//訓示棧頂位置 
}Stack;
//順序棧的基本運算
//置棧空，判棧空，判棧滿，進棧，退棧，取棧頂元素 
void InitStack(Stack*s){		//置棧空 
	s->top=-1;
} 
int StackEmpty(Stack*s){		//判棧空
	return s->top==-1; 
}
int StackFull(Stack*s){			//判棧滿
	return s->top==StackSize-1;
}
int Push(Stack*s,int x){				//進棧
	if(StackFull(s)){
		printf("The stack is overflow\n");
		return 0;
	} else{
		s->data[++s->top]=x;	//s->top先自加然後存入變量x
	}
	return 1;	//傳回1代表函數正常調用
}
int Pop(Stack*s){				//退棧 
	if(StackEmpty(s)){
		printf("The stack is empty\n");
		return 0;
	}else
	return s->data[s->top--];	//傳回data[s->top]然後s->top減一
}
int StackTop(Stack*s){			//取棧頂元素
	if(StackEmpty(s)){
		printf("The stack is empty\n");
		return 0;
	} else
	return s->data[s->top];
}
int main(void){
}
           

1. 鍊棧的定義和基本運算

#include<stdio.h>
#include<stdlib.h>
typedef struct StackNode{
	int data;		//資料域
	struct StackNode *next;		//指針域
}Stack;
typedef struct LinkStack{	//再命名一個結構體是為了友善使用棧頂指針，可以在這個結構體中加一個計數變量來記錄位置
	struct StackNode* top;	//棧頂指針
}LinkStack;
void InitStack(LinkStack*s){		//置棧空
	s->top=NULL;
}
int StackEmpty(LinkStack*s){		//判棧空
	return s->top==NULL; 
}
int Push(LinkStack*s,int x){			//進棧
	 Stack *p=(Stack*)malloc(sizeof(Stack));
	 p->data=x;
	 p->next=s->top;
	 s->top=p;
}
int Pop(LinkStack*s){				//退棧
	if(StackEmpty(s)){
		printf("Stack underflow\n");
		return 0;
	} 
	Stack*p=s->top;		//儲存棧頂指針的位址
	int x=p->data;		//儲存data中的資料
	s->top=p->next;		//删除棧頂
	free(p);			//釋放不需要的結點
	return x;			//返滬棧頂資料
}
int StackTop(LinkStack*s){			//取棧頂元素
	if(StackEmpty(s)){
		printf("the stack is empty\n");
		return 0;
	} 
	return s->top->data;
}
int main(void){
}