C語言編程數據結構的棧和隊列

Posted on by

棧

棧是一種以後進先出為順序對對象進行添加或刪除的數據結構
對棧進行形象記憶就像是桌子上的一堆書或一堆盤。對盤子取或者存盤子，都隻能對最上面的書或者盤子進行操作。

在這裡插入圖片描述

對於棧而言，隻有彈棧才能獲取其數據。
當我們用C語言實現棧這個數據結構。
其實有三種方法實現

1，數組

2，單鏈表

3，雙向鏈表

但是，對於雙向鏈表，實現棧而言過於復雜。
可以選擇數組或者單鏈表。

數組實現

標題全部代碼

Stack_array.c

#include "Stack_array.h"
void InitStack(STstack* st)//棧的初始化
{
	st->top = 0;
	st->arr = (STData*)malloc(CAP*sizeof(STData));
	st->capacity = CAP;
}
void StackPush(STstack* st, STData n)//元素入棧
{
	if (st->top == st->capacity)//判斷是否需要擴容
	{
		StackExpansion(st);
	}
	st->arr[st->top++] = n;
}
STData StackPop(STstack* st)//元素退棧
{
	assert(st);
	assert(!StackEmpty(st));//判斷是否為空棧
	return st->arr[--st->top];
}
int StackEmpty(STstack* st)//判斷棧是否為空
{
	if (st->top == 0)
		return 1;
	return 0;
}
void StackDestory(STstack* st)//銷毀棧，防止內存泄漏
{
	free(st->arr);
	st->arr = NULL;
}
void StackExpansion(STstack* st)//擴容
{
	STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
	if (tmp == NULL)
	{
		printf("Exparsion Error\n");
		exit(-1);
	}
	st->arr = tmp;
	st->capacity *= 2;
}
void StackPrint(STstack* st)//打印棧的元素，但前提是要退棧才能得到元素
{
	while(st->top)
	{
		STData ret = StackPop(st);
		printf("%d ", ret);
	}
}

Stack_array.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define CAP 4
typedef int STData;
typedef struct Stack//結構體用於維護棧
{
	int top;//棧頂標記
	STData* arr;//棧的指針
	int capacity;//棧的容量
}STstack;
void InitStack(STstack* st);//棧的初始化
void StackPush(STstack* st, STData n);//元素入棧
STData StackPop(STstack* st);//元素退棧
void StackExpansion(STstack* st);//擴容
int StackEmpty(STstack* st);//判斷棧是否為空
void StackDestory(STstack* st);//銷毀棧，防止內存泄漏
void StackPrint(STstack* st);//打印棧的元素，但前提是要退棧才能得到元素

對於數組實現而言。創建一個結構體用於維護整個棧。而其中有一個用於鏈接創建的數組。

typedef int STData;
typedef struct Stack//結構體用於維護棧
{
	int top;//棧頂標記
	STData* arr;//棧的指針
	int capacity;//棧的容量
}STstack;

作為數組棧，需要一個動態的數組。則這就需要一個Capacity作為衡量是否需要擴容的標準。而top需要作為入棧元素的位置。
當top的值等於Capacity時就意味著棧已經滿瞭。因為數組是從0開始的

在這裡插入圖片描述

初始化數組棧

在初始化時，要先動態開辟一個數組空間，且，未壓棧壓入數據元素，其top要設為0.要保證當需要壓棧時有明確指定的空間。同時，top的位置要為最後壓入數據的下一個下標。

void InitStack(STstack* st)//棧的初始化
{
	st->top = 0;
	st->arr = (STData*)malloc(CAP*sizeof(STData));
	st->capacity = CAP;
}

滿棧後擴容

其Capacity要作為判斷是否滿棧的標準。且，滿棧後要進行擴容（因為是動態數組）。

void StackExpansion(STstack* st)//擴容
{
	STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
	if (tmp == NULL)
	{
		printf("Exparsion Error\n");
		exit(-1);
	}
	st->arr = tmp;
	st->capacity *= 2;
}

同時，還要每次更改棧的容量，為下一次是否滿棧作為標準。

是否為空棧

int StackEmpty(STstack* st)//判斷棧是否為空
{
	if (st->top == 0)
		return 1;
	return 0;
}

其是否為空。也就是top的位置在數組的0下標位。

壓棧和退棧

void StackPush(STstack* st, STData n)//元素入棧
{
	if (st->top == st->capacity)//判斷是否需要擴容
	{
		StackExpansion(st);
	}
	st->arr[st->top++] = n;
}
STData StackPop(STstack* st)//元素退棧
{
	assert(st);
	assert(!StackEmpty(st));//判斷是否為空棧
	return st->arr[--st->top];
}

壓棧
每次壓棧，都需要判斷是否滿棧，並決定是否擴容。
同時，當在原先top位置的數位置進行賦值。並之後要將top向後移動一個位置。保證下一次壓棧。

退棧
退棧返回top的上一個位置的元素。同時top向前移動一個位置，不需要free，下次壓棧會自動覆蓋。

鏈表實現

stack_chain.h

#include <stdio.h>
#include <stdlib.h>
#define N 3
typedef struct stackele
{
	int n;
	int* point;
}sta;
sta* top;
void initstack(sta* a);//初始化棧
void pushstack(sta* a,int num);//入棧
//void printstack(sta* a);//打印棧
//void fullstack(sta* a);//檢查是否滿棧的情況
void emptystack(sta* a);//檢查是否空棧的情況
int popstack(sta*a);//出棧

stack_chain.c

#include "stack_chain.h"
void initstack(sta* a)//初始化棧
{
	top= NULL;
}
void pushstack(sta* a, int num)//入棧
{
	sta* p = (sta*)malloc(sizeof(sta));
	p->n = num;//新節點賦值
	p->point = top;
	top = p;
}
int popstack(sta* a)//出棧
{
	emptystack(a);//檢查是否空棧的情況
	int date;
	sta* des = top;
	top = top->point;
	date = des->n;
	free(des);
	des = NULL;
	return date;
}
void emptystack(sta* a)//檢查是否空棧的情況
{
	if (top == NULL)
	{
		printf("Stack empty");
		exit(0);
	}
}

對於鏈表實現棧而言，和數組其實差不多。隻不夠，每次壓棧都需要重新動態開辟一個新節點，並且鏈入棧中。但是，這並不是普通的直接鏈入。而是需要頭插入棧。

在這裡插入圖片描述

這樣頭插入棧，可以方便退棧的時候，可以找到上一個元素。而壓棧是不需要什麼順序。每一個壓棧節點就是top節點。

整個壓棧流程

在這裡插入圖片描述

void pushstack(sta* a, int num)//入棧
{
	sta* p = (sta*)malloc(sizeof(sta));
	p->n = num;//新節點賦值
	p->point = top;
	top = p;
}

整個彈棧流程

在這裡插入圖片描述

int popstack(sta* a)//出棧
{
	emptystack(a);//檢查是否空棧的情況
	int date;
	sta* des = top;
	top = top->point;
	date = des->n;
	free(des);
	des = NULL;
	return date;
}

出棧情況

尤其要把握一個條件：空棧
由於不是數組，且鏈式結構的特性，是不需要擴容的。即不需要判斷滿棧的情況。
隻考慮空棧的條件

void emptystack(sta* a)//檢查是否空棧的情況
{
	if (top == NULL)
	{
		printf("Stack empty");
		exit(0);
	}
}

這裡空棧的條件是top指針指向NULL時也就是

在這裡插入圖片描述

為什麼呢？
因為每次彈棧的時候，都會free掉top指向的空間然後讓top指向下一個節點。就這樣不斷移動。但是我設計初始化的時候是top= NULL;而且每次壓棧都是p->point = top;這就會有一個標準來限定空棧的情況。

對於棧而言，其更像是一個遞歸的具象化。

隊列

在這裡插入圖片描述

這種數據結構就像是銀行櫃臺的取號機，
先取號的先去櫃臺。

始終滿足先入先出的概念

隊列的實現

queue_chain.h

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QUData;
typedef struct queue
{
	QUData data;
	struct queue* next;
}queue;
typedef struct Queue//結構體用於維護隊列
{
	queue* Dequeue;//隊頭指針
	queue* Enqueue;//隊尾指針
}QUqueue;
void InitQueue(QUqueue* qu);//棧的初始化
void QueuePush(QUqueue* qu, QUData n);//元素入隊
QUData QueuePop(QUqueue* qu);//元素出隊
int QueueEmpty(QUqueue* qu);//判斷隊列是否為空
void QueueDestory(QUqueue* qu);//銷毀隊，防止內存泄漏
void QueuePrint(QUqueue* qu);//打印隊列中的元素，但前提是要出隊才能得到元素

queue_chain.c

#include "queue_chain.h"
void InitQueue(QUqueue* qu)//隊列的初始化
{
	qu->Dequeue = qu->Enqueue = NULL;
}
void QueuePush(QUqueue* qu, QUData n)//元素入隊
{
	queue* newcell = (QUData*)malloc(sizeof(QUData));
	newcell->data = n;
	newcell->next = NULL;
	if (qu->Dequeue == NULL)
	{
		qu->Enqueue = qu->Dequeue = newcell;
	}
	else
	{
		qu->Enqueue->next = newcell;
		qu->Enqueue = newcell;
	}
}
QUData QueuePop(QUqueue* qu)//元素出隊
{
	if (QueueEmpty(qu))
	{
		printf("Queue Is Empty");
		exit(-1);
	}
	QUData ret = qu->Dequeue->data;
	qu->Dequeue = qu->Dequeue->next;
	return ret;
}
int QueueEmpty(QUqueue* qu)//判斷隊列是否為空
{
	if (qu->Dequeue == qu->Enqueue)
		return 1;
	return 0;
}
void QueueDestory(QUqueue* qu)//銷毀隊，防止內存泄漏
{
	queue* cur = qu->Dequeue;
	while (cur)
	{
		queue* pnext = cur->next;
		free(cur);
		cur = pnext;
	}
	qu->Dequeue = qu->Enqueue = NULL;
}
void QueuePrint(QUqueue* qu)//打印隊列中的元素，但前提是要出隊才能得到元素
{
	queue* cur = qu->Dequeue;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

隊 畢竟是先入先出的數據結構。
所以要兩個指針，
qu->Dequeue 指向隊頭，
qu->Enqueue 指向隊尾，
不然每次都去找隊尾是相當浪費時間的。

一個結構體類型用於維護這個隊列

typedef int QUData;
typedef struct queue//描述每個隊的元素
{
	QUData data;
	struct queue* next;
}queue;
typedef struct Queue//結構體用於維護隊列
{
	queue* Dequeue;//隊頭指針
	queue* Enqueue;//隊尾指針
}QUqueue;

隊頭指針負責出隊，
隊尾指針負責入隊。

概念流程圖

入隊

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

入隊列的實現

void QueuePush(QUqueue* qu, QUData n)//元素入隊
{
	queue* newcell = (QUData*)malloc(sizeof(QUData));
	newcell->data = n;
	newcell->next = NULL;
	if (qu->Dequeue == NULL)
	{
		qu->Enqueue = qu->Dequeue = newcell;
	}
	else
	{
		qu->Enqueue->next = newcell;
		qu->Enqueue = newcell;
	}
}

**當然，入隊列在剛開始的時候，頭尾指針還是一起指向NULL。
當入第一個元素時，那個元素即是第一個元素也是最後一個元素。要獨立判斷。**這是一個特殊情況。

出隊

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

出隊列的實現

QUData QueuePop(QUqueue* qu)//元素出隊
{
	if (QueueEmpty(qu))
	{
		printf("Queue Is Empty");
		exit(-1);
	}
	QUData ret = qu->Dequeue->data;
	qu->Dequeue = qu->Dequeue->next;
	return ret;
}

但是每次出隊列都需要判斷是否為空隊。如果是空隊還繼續出隊會相當於NULL->next ,這是直接報錯的。

所以還要一個函數判斷是否空隊。

是否空隊

int QueueEmpty(QUqueue* qu)//判斷隊列是否為空
{
	if (qu->Dequeue == qu->Enqueue)
		return 1;
	return 0;
}

空隊就是相當於回到瞭初始化的情形

qu->Dequeue = qu->Enqueue = NULL;

也就是兩者都指向同一處，也就是NULL。

以上就是C語言編程數據結構的棧和隊列的詳細內容，更多關於C語言數據結構的資料請關註WalkonNet其它相關文章！

感謝觀看~

推薦閱讀：