前言
棧和隊(duì)列是一種特殊的線性結(jié)構(gòu)，他與之前學(xué)的線性結(jié)構(gòu)不同，棧和隊(duì)列是擁有一種特殊規(guī)則的線性結(jié)構(gòu)，雖然它是用數(shù)組或者鏈表實(shí)現(xiàn)，但是只有符合這種規(guī)則才能被稱(chēng)作?；蛘哧?duì)列
一、棧
1.棧的概念及定義
棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。棧中的數(shù)據(jù)元素遵守
后進(jìn)先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
2.棧的實(shí)現(xiàn)
棧的實(shí)現(xiàn)有兩種實(shí)現(xiàn)，但是我們可以想想棧的特點(diǎn)，后進(jìn)先出，我們只對(duì)尾部操作，那么是不是用數(shù)組剛好合適，雖然用鏈表也可以，但是數(shù)組的尾插的損耗更加小一點(diǎn)，所以我這里就一數(shù)組來(lái)進(jìn)行講解
我這里用動(dòng)態(tài)的數(shù)組來(lái)實(shí)現(xiàn)棧
（1）棧的結(jié)構(gòu)
typedef int STDataType;//方便存儲(chǔ)各種數(shù)據(jù)
typedef struct Stack
{
STDataType* a;
int top;//棧頂位置，如果等于capacity=0時(shí)為空
int capacity;//容量
}ST;
（2）StackInit（初始化）
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;//初始化時(shí)如果top是0，即top指向棧頂上的后一位，所以取出元素時(shí)需要減一
ps->capacity = 0;
}
（3）StackPush（壓棧）
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;
STDataType* temp = (STDataType * )realloc(ps->a, sizeof(STDataType)*newcapacity);
if (temp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = temp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
這里的代碼參考動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)
（4）StackPop（出棧）
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
（5）StackTop（取棧頂?shù)脑兀?/h4>
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];//這里需要減一是因?yàn)閠op指向棧頂上的后一位，如果還不理解就看初始化代碼
}
（6）StackEmpty（檢查棧是否為空）
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];//這里需要減一是因?yàn)閠op指向棧頂上的后一位，如果還不理解就看初始化代碼
}
布爾類(lèi)型的數(shù)據(jù)在c使用需要加stdbool頭文件
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
（7）StackDestroy（銷(xiāo)毀棧）
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
3.完整代碼
（1）頭文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
（2）源文件
#include"Stack.h"
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;//初始化時(shí)如果top是0，即top指向棧頂上的后一位
ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;
STDataType* temp = (STDataType * )realloc(ps->a, sizeof(STDataType)*newcapacity);
if (temp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = temp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
至此，棧算是搞完了，接下來(lái)講隊(duì)列
二、隊(duì)列
1.隊(duì)列的概念及定義
隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有
先進(jìn)先出FIFO(First In First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾 出隊(duì)列：進(jìn)行刪除操作的一端稱(chēng)為隊(duì)頭
2.隊(duì)列的實(shí)現(xiàn)
隊(duì)列需要能夠?qū)︻^和尾操作，所以數(shù)組是不好實(shí)現(xiàn)的，我們用鏈表來(lái)實(shí)現(xiàn)
（1）隊(duì)列的結(jié)構(gòu)
隊(duì)列的特點(diǎn)與排隊(duì)購(gòu)物差不多，我們要能夠控制頭的出和尾的進(jìn)，所以與棧不一樣，我們需要頭和尾的位置所以我們就要實(shí)現(xiàn)成下面的樣子
typedef int QDataType;
typedef struct QueueNode//隊(duì)列的節(jié)點(diǎn)
{
struct QueueNode* next;
QDataType data;
}QN;
typedef struct Queue//存儲(chǔ)了頭和尾，方便我們直接對(duì)頭和尾操作
{
QN* head;
QN* tail;
}Queue;
此處的實(shí)現(xiàn)可以參考我前面的文章鏈表
（2）QueueInit（初始化）
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
（3）QueuePush（入隊(duì)）
尾入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QN* newnode = (QN*)malloc(sizeof(QN));
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
（4）QueuePop（出隊(duì)）
頭出
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QN* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
（5）QueueFront（獲取頭部元素）
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
（6）QueueBack（獲取尾部元素）
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq->tail));
return pq->tail->data;
}
（7）QueueEmpty（檢查隊(duì)列是否為空）
布爾類(lèi)型需要包括頭文件stdbool文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-794159.html
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
3.完整代碼
（1）頭文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QN;
typedef struct Queue
{
QN* head;
QN* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
（2）源文件
#include"Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QN* cur = pq->head;
while (cur)
{
QN* next = cur->next;
free(cur);
cur = next;
}
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QN* newnode = (QN*)malloc(sizeof(QN));
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QN* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq->tail));
return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
結(jié)語(yǔ)
好了，棧和隊(duì)列算是講完了，如果有什么不妥之處歡迎指正，謝謝文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-794159.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
