国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<abbr id="ng56i"><xmp id="ng56i"><s id="ng56i"></s>

【數(shù)據結構】實現(xiàn)棧和隊列

2年前作者：～yY…s<#>分類：Toy博客閱讀(26)違法舉報

這篇具有很好參考價值的文章主要介紹了【數(shù)據結構】實現(xiàn)棧和隊列。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

一、棧

1.棧的概念及結構

（1）棧的概念

棧是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據元素遵守后進先出LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據也在棧頂。

（2）棧的結構

【數(shù)據結構】實現(xiàn)棧和隊列,數(shù)據結構,c語言,開發(fā)語言,鏈表

2.棧的實現(xiàn)

（1）類型和函數(shù)的聲明

棧的結構與順序表相同，也是用數(shù)組。因為棧的特點是出棧、入棧在同一位置，所以用數(shù)組尾插更方便。

typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}ST;
//初始化
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);
//入棧
void STPush(ST* ps, STDataType x);
//出棧
void STPop(ST* ps);
//檢查是否為空
bool STEmpty(ST* ps);
//獲取棧的元素個數(shù)
int STSize(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);

（2）初始化棧

void STInit(ST* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

（3）銷毀

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

（4）入棧

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

（5）出棧

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

（6）檢查是否為空

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

（7）獲取棧的元素個數(shù)

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

（8）獲取棧頂元素

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->data[ps->top - 1];
}

二、棧的全部代碼

1.Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}ST;
//初始化
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);
//入棧
void STPush(ST* ps, STDataType x);
//出棧
void STPop(ST* ps);
//檢查是否為空
bool STEmpty(ST* ps);
//獲取棧的元素個數(shù)
int STSize(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);

2Stack.c

#include "Stack.h"
//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//銷毀
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//入棧
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}
//出棧
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
//檢查是否為空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//獲取棧的元素個數(shù)
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
//獲取棧頂元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->data[ps->top - 1];
}

3.Test.c

#include "Stack.h"
void test()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
}
int main()
{
	test();
	return 0;
}

【數(shù)據結構】實現(xiàn)棧和隊列,數(shù)據結構,c語言,開發(fā)語言,鏈表

三、隊列

1.隊列的概念及結構

（1）隊列的概念

隊列：只允許在一端進行插入數(shù)據操作，在另一端進行刪除數(shù)據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out) 入隊列：進行插入操作的一端稱為隊尾出隊列：進行刪除操作的一端稱為隊頭

（2）隊列的結構

【數(shù)據結構】實現(xiàn)棧和隊列,數(shù)據結構,c語言,開發(fā)語言,鏈表

2.隊列的實現(xiàn)

隊列也可以數(shù)組和鏈表的結構實現(xiàn)，使用鏈表的結構實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結構，出隊列在數(shù)組頭上出數(shù)據，效率會比較低。

（1）類型和函數(shù)的聲明

隊列除了節(jié)點的結構體以外，還要再創(chuàng)建一個結構體，方便找到尾指針。

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
//初始化
void QueInit(Que* pq);
//銷毀
void QueDestroy(Que* pq);
//入隊
void QuePush(Que* pq, QDataType x);
//出隊
void QuePop(Que* pq);
//獲取頭部元素
QDataType QueFront(Que* pq);
//獲取隊尾元素
QDataType QueBack(Que* pq);
//獲取元素個數(shù)
int QueSize(Que* pq);
//檢查是否為空
bool QueEmpty(Que* pq);

（2）初始化隊列

void QueInit(Que* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

（3）銷毀

void QueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

（4）入隊

入隊相當于尾插，因為只有一個入口插入節(jié)點，所以直接在這個函數(shù)創(chuàng)建一個新節(jié)點。分兩種情況：剛開始沒有節(jié)點尾插、已有節(jié)點再尾插。

void QuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

（5）出隊

出隊相當于頭刪。如果沒有節(jié)點，就不能再刪了，所以要斷言檢查是否為空。這里的頭刪也要分兩種情況：只有一個節(jié)點、一個以上的節(jié)點。

void QuePop(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

（6）獲取頭部元素

QDataType QueFront(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->head->data;
}

（7）獲取隊尾元素

QDataType QueBack(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->tail->data;
}

（8）獲取元素個數(shù)

int QueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}

（9）檢查是否為空

bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}

四、隊列的全部代碼

1.Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
//初始化
void QueInit(Que* pq);
//銷毀
void QueDestroy(Que* pq);
//入隊
void QuePush(Que* pq, QDataType x);
//出隊
void QuePop(Que* pq);
//獲取頭部元素
QDataType QueFront(Que* pq);
//獲取隊尾元素
QDataType QueBack(Que* pq);
//獲取元素個數(shù)
int QueSize(Que* pq);
//檢查是否為空
bool QueEmpty(Que* pq);

2.Queue.c

#include "Queue.h"
//初始化
void QueInit(Que* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//銷毀
void QueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
//入隊
void QuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
//出隊
void QuePop(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
//獲取頭部元素
QDataType QueFront(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->head->data;
}
//獲取隊尾元素
QDataType QueBack(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->tail->data;
}
//獲取元素個數(shù)
int QueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}
//檢查是否為空
bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}

3.Test.c

#include "Queue.h"
void test()
{
	Que q;
	QueInit(&q);
	QuePush(&q, 1);
	QuePush(&q, 2);
	QuePush(&q, 3);
	QuePush(&q, 4);
	QuePush(&q, 5);
	while (!QueEmpty(&q))
	{
		printf("%d ", QueFront(&q));
		QuePop(&q);
	}
	printf("\n");
	QueDestroy(&q);
}
int main()
{
	test();
	return 0;
}

【數(shù)據結構】實現(xiàn)棧和隊列,數(shù)據結構,c語言,開發(fā)語言,鏈表

感謝觀看~文章來源地址http://www.zghlxwxcb.cn/news/detail-668855.html

到了這里，關于【數(shù)據結構】實現(xiàn)棧和隊列的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！

本文來自互聯(lián)網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如若轉載，請注明出處：如若內容造成侵權/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經查實，立即刪除！

分享到：

領支付寶紅包贊助服務器費用

C語言數(shù)據結構——線性表之棧和隊列
為什么會定義棧和隊列這兩種數(shù)據結構呢？原因在于：之所以會定義棧和隊列這樣的數(shù)據結構是因為他們有兩大特性：第一：他們可以保存程序運行路徑中各個點的信息，以便用于回溯操作或其他需要訪問已經訪問過的節(jié)點信息的操作。比如：棧用于解決迷宮問題，就
2023年04月11日
瀏覽(95)
【數(shù)據結構】實現(xiàn)棧和隊列
（1）棧的概念棧是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據元素遵守后進先出LIFO（Last In First Out）的原則。壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據在棧頂。出
2024年02月11日
瀏覽(26)
數(shù)據結構|棧和隊列以及實現(xiàn)
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據插入和數(shù)據刪除的一端稱為棧頂，另一端稱為棧頂。棧中的數(shù)據元素遵循后進先出的原則，簡稱LIFO（Last In First Out）。壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據在棧頂。出棧：棧
2024年02月09日
瀏覽(22)
數(shù)據結構（Java實現(xiàn)）-棧和隊列
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。先進后出棧的使用棧的模擬實現(xiàn) 上述的主要代碼改變元素的序列將遞歸轉化為循環(huán) 比如：逆序打印鏈表結果如下隊列：只允許在一端進行插入數(shù)據操作，在另一端進行刪除數(shù)據操作的特殊線性表
2024年02月10日
瀏覽(30)
【數(shù)據結構】棧和隊列的模擬實現(xiàn)
前言：前面我們學習了單鏈表并且模擬了它的實現(xiàn)，今天我們來進一步學習，來學習棧和隊列吧！一起加油各位，后面的路只會越來越難走需要我們一步一個腳??！ ?? 博主CSDN主頁:衛(wèi)衛(wèi)衛(wèi)的個人主頁 ?? ?? 專欄分類:數(shù)據結構 ?? ??代碼倉庫:衛(wèi)衛(wèi)周大胖的學習日記?? ??關
2024年02月05日
瀏覽(23)
數(shù)據結構基礎5：棧和隊列的實現(xiàn)。
1.基本概念棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據元素遵守后進先出LIFO（Last In First Out）的原則。壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據在棧頂。出棧：棧
2024年02月13日
瀏覽(25)
數(shù)據結構——Java實現(xiàn)棧和隊列
（1）棧是一種線性數(shù)據結構（2）規(guī)定只能從棧頂添加元素，從棧頂取出元素（3）是一種先進后出的數(shù)據結構（Last First Out）LIFO Java中可以直接調用方法來實現(xiàn)棧如何自己寫代碼來實現(xiàn)棧呢？先定義一個接口，方便后邊進行調用接下來來實現(xiàn)棧的方法，調用接口，完善方法
2024年01月20日
瀏覽(27)
c++實現(xiàn)數(shù)據結構棧和隊列
1、棧頭文件源文件主函數(shù) 2、循環(huán)隊列頭文件源文件主函數(shù) 3、思維導圖
2024年02月08日
瀏覽(28)
【數(shù)據結構】棧和隊列的模擬實現(xiàn)（兩個方式實現(xiàn)）
??作者簡介：加油，旭杏，目前大二，正在學習 C++ ，數(shù)據結構等?? ??作者主頁：加油，旭杏的主頁?? ?本文收錄在：再識C進階的專欄?? ??代碼倉庫：旭日東升 1?? ??歡迎大家點贊 ?? 收藏 ? 加關注哦！?? ???????這一篇博客將學習棧和隊列的相關知識，棧
2024年02月05日
瀏覽(29)
【數(shù)據結構和算法】---棧和隊列的互相實現(xiàn)
具體題目可以參考 LeetCode 232. 用棧實現(xiàn)隊列首先要想到的是，隊列是一種先進先出的結構，而棧是一種先進后出的結構。依此我們可以定義兩個棧結構來模擬先進先出，既然要定義兩個棧，那么為了方便調用，我們可以將這兩個棧結構定義在一個結構體中，如下：實現(xiàn)
2024年02月03日
瀏覽(29)

<strong id="ok6f3"></strong>