天天看點
傳回

c語言建立棧（順序棧、雙棧和鍊式棧）順序存儲雙棧鍊式棧

c語言建立棧

  • 順序存儲
    • 棧的順序存儲定義
    • 初始化棧
    • 入棧操作
    • 出棧操作
    • 其餘操作
      • 讀取棧頂元素
      • 棧中元素個數
      • 棧是否為空
  • 雙棧
    • 雙棧的順序存儲結構定義
    • 建立雙棧
    • 判斷棧為空
    • 進棧操作
    • 出棧操作
  • 鍊式棧
    • 前言
    • 鍊式存儲表示
    • 進棧操作
    • 出棧操作
    • 取棧頂元素
    • 置空棧

順序存儲

我們采用的是動态配置設定方式來定義順序存儲。

有以下幾點聲明：

  1. 指派操作：

    *s->top = val;
  2. 棧為空：

    s->top == s->base
  3. 棧滿：

    s->top-s->base >=stacksize

棧的順序存儲定義 

#define MAXSTACKSIZE 100
#define STACKINCREMENT 10

typedef struct {
	int* base;
	int* top;
	int stacksize;
}SqStack;

初始化棧 

SqStack* InitStack_Sq() {
	SqStack* s;
	s = (SqStack*)malloc(sizeof(SqStack)); //記得申請空間
	s->base = (int*)malloc(MAXSTACKSIZE *sizeof(int));
	if (!s->base) {
		printf("記憶體配置設定失敗\n");
		return 0;
	}
	//同時指向一個位置
	s->top = s->base;
	s->stacksize = MAXSTACKSIZE;
	return s;
}

入棧操作 

//入棧
void Push_Sq(SqStack* s, int val) {
	if (s->top - s->base >= s->stacksize) { //滿棧了
		s->base = (int*)realloc(s->base,sizeof(int) * (MAXSTACKSIZE + STACKINCREMENT));
		if (!s->base) {
			printf("記憶體配置設定失敗\n");
			return;
		}
		s->stacksize += STACKINCREMENT;
		s->top = s->base;
	}
	*s->top = val;
	s->top++;
	// *s->top++ = val;
}

出棧操作 

//出棧
// s->top 指向的是棧頂的下一個，是以要先減，再取值
int Pop_Sq(SqStack* s) {
	if (s->base == s->top) {
		printf("隊列為空\n");
		return 0;
	}
	int val = *(--s->top);
	return val;
}

其餘操作

讀取棧頂元素 

//讀取棧頂
int Top_Sq(SqStack* s) {
	if (s->base == s->top) {
		printf("隊列為空\n");
		return 0;
	}
	return *(s->top - 1);
}

棧中元素個數 

//傳回棧中元素個數
int stackLength(SqStack* s) {
	return s->top - s->base;
}

棧是否為空 

//判斷棧是否為空
int empty_sq(SqStack* s) {
	if (s->base == s->top)
		return 1;
	else
		return 0;
}

雙棧

MAXSTACKSTZE為整個數組空間的長度，棧1的底端固定在下标為0的一端，棧2的底端固定在下标為MAXSTACKSIZE -1 的一端。 top⁡1 和 top2分别為棧1和棧2的棧頂指針，并約定棧頂指針指向目前元素，即棧1空的條件是 top1=−1,棧1滿的條件top1=top⁡2−

1，棧2空的條件是 top⁡2=MAXSTACSIZE,棧2滿的條件是 。top2=top1+1。

雙棧的順序存儲結構定義 

#define MAXSTACKSIZE 100

typedef struct {
	int data[MAXSTACKSIZE];
	int top1, top2;
}doubleStack;

建立雙棧 

//建立雙棧
doubleStack* init() {
	doubleStack* s;
	s = (doubleStack*)malloc(sizeof(doubleStack));
	s->top1 = -1;
	s->top2 = MAXSTACKSIZE;
	return  s;
}

判斷棧為空 

//flag = 1 是棧1，flag = 2 是棧2
int empty_D(doubleStack* s,int flag) {
	if (flag == 1) {
		if (s->top1 == -1)
			return 1;
		else
			return 0;
	}
	else {
		if (s->top1 == MAXSTACKSIZE)
			return 1;
		else
			return 0;
	}
}

進棧操作 

//進棧
void Push_D(doubleStack* s, int flag, int val) {
	if (s->top1 + 1 == s->top2) {
		printf("棧已滿\n");
		return;
	}
	if (flag == 1) // 對棧一進行操作
		s->data[++s->top1] = val; //先使棧1的頂指針增加1，再将元素插入
	else
		s->data[--s->top2] = val; //先使棧2的頂指針減1，再将元素插入
}

出棧操作 

// 出棧
// 指針移動就相當于删除操作
int Pop_D(doubleStack* s, int flag) {
	if (flag == 1) {
		if (s->top1 == -1) {
			printf("棧為空\n");
			return;
		}
		int val = s->data[s->top1--]; //先删除棧頂元素，再講棧頂指針減1
		return val;
	}
	else {
		if (s->top1 == MAXSTACKSIZE) {
			printf("棧為空\n");
			return;
		}
		int val = s->data[s->top1++];//先删除棧頂元素，再講棧頂指針加1
		return val;
	}
}

鍊式棧

前言

鍊式存儲表示

若是棧中元素的數目變化範圍較大或不清楚棧元素的數目，就應該考慮使用鍊式存儲結構。人們将用鍊式存儲結構表示的棧稱作“鍊棧”。

鍊棧通常用一個無頭結點的單連結清單表示。由于棧的插入、删除操作隻能在一端進行，而對于單連結清單來說，在首端插入、删除結點要比在尾端進行相對容易一些，是以将單連結清單的首端作為棧的頂端，即将單連結清單的頭指針作為棧頂指針。

typedef struct SNode {
	int data; //資料域
	SNode* next; //鍊域
}SNode,*LinkStack;
LinkStack top; //棧頂指針

進棧操作 

void init(LinkStack top) {
	top = NULL; 
}

//進棧操作
void Push_L(LinkStack top, int val) {
	SNode* node = (LinkStack)malloc(sizeof(SNode));
	if (!node) {
		printf("申請空間失敗\n");
		return;
	}
	node->data = val;
	node->next = top; //因為剛開始是空的，是以棧底元素指向的下一個元素為空
	top = node; //棧頂指針指向新節點
}

出棧操作 

//出棧操作
int Pop_L(LinkStack top) {
	if (!top) {
		printf("棧為空\n");
		return;
	}
	int val = top->data;
	SNode* p = top;
	top = top->next; //修改棧頂指針，将棧頂節點從鍊上摘下
	free(p);
	return val;
}

取棧頂元素 

//取棧頂元素
int Top_L(LinkStack top) {
	if (!top) {
		printf("棧為空\n");
		return;
	}
	int val = top->data; //取棧頂元素
	return val;
}

置空棧 

//棧置空
void Clear_L(LinkStack top) {
	while (top) {
		SNode* p = top;
		top = top->next;
		free(p);
	}
}
# 棧和隊列 c語言 資料結構 棧
上一篇: 棧的順序儲存和鍊式儲存棧
下一篇: C語言-棧tack順序存儲和鍊式存儲

繼續閱讀