目錄

一、棧

1.1 棧的定義和結構

1.2 棧的函數實現

1.2.1 初始化

1.2.2 入棧

1.2.3 出棧

1.2.4 獲取棧頂元素

?1.2.5 棧的長度

?1.2.6 棧的完整代碼

二、隊列的定義和結構

2.1 隊列的定義和結構

2.2 隊列的函數實現

2.2.1 隊列的初始化

?2.2.2 入隊

2.2.3 出隊?

2.2.4 獲取隊頂元素

2.2.5 獲取隊尾元素

?2.2.6 隊列的長度

2.2.7 隊列的完整代碼

---

一、棧

1.1 棧的定義和結構

棧：一種特殊的線性表。棧中的數據元素遵守先進后出的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

1.2 棧的函數實現

1.2.1 初始化

void StackInit(ST* st)

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = st->capacity = 0;
}

1.2.2 入棧

void StackPush(ST* st, STDataType x)

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

1.2.3 出棧

void StackPop(ST* st)

bool StackEmpty(ST* st)//判斷棧是否為空
{
	assert(st);
	return st->top == 0;

}
void StackPop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}

1.2.4 獲取棧頂元素

STDataType StackTop(ST* st)

STDataType StackTop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top - 1];
}

?1.2.5 棧的長度

int StackSize(ST* st)

int StackSize(ST* st)
{
	assert(st);
	return st->top;
}

?1.2.6 棧的完整代碼

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = st->capacity = 0;
}
void StackPush(ST* st, STDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		STDataType* tmp = (STDataType)realloc(st->a,newcapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top] = x;
	st->top++;
}
void StackPrint(ST* st)
{
	assert(st);
	while (st->top >0)
	{
		st->top--;
		printf("%d ", st->a[st->top]);
	}
}
bool StackEmpty(ST* st)//判斷棧是否為空
{
	assert(st);
	return st->top == 0;

}
void StackPop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}
STDataType StackTop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top - 1];
}
int StackSize(ST* st)
{
	assert(st);
	return st->top;
}

二、隊列的定義和結構

2.1 隊列的定義和結構

隊列：只允許在隊尾進行插入數據操作，在隊頭進行刪除數據操作的特殊線性表。隊列具有先進先出的特點

2.2 隊列的函數實現

2.2.1 隊列的初始化

void QInit(Queue* q)

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;

}Qnode;
typedef struct Queue
{
	Qnode* head;
	Qnode* tail;
	int size;
}Queue;
void QInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}

?2.2.2 入隊

void QPush(Queue* q, QDataType x)

oid QPush(Queue* q, QDataType x)
{
	assert(q);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if(newnode==NULL)
    {
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (q->tail == NULL)
		q->tail = q->head = newnode;
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}

2.2.3 出隊?

void QPop(Queue* q)

bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
void QPop(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		Qnode* del = q->head;
		q->head = q->head->next;
		free(del);
		del= NULL;
		q->size--;
	}
}

2.2.4 獲取隊頂元素

QDataType QFront(Queue* q)

QDataType QFront(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->head->data;
}

2.2.5 獲取隊尾元素

QDataType QBack(Queue* q)

QDataType QBack(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->tail->data;
}

?2.2.6 隊列的長度

size_t QSize(Queue* q)

size_t QSize(Queue* q)
{
	assert(q);
	return q->size;
}

2.2.7 隊列的完整代碼

#include<stdio.h>
#include<assert.h>
#include<stdlib.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;
}Queue;
void QInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}
void QPrint(Queue* q)
{
	assert(q);
	Qnode* cur = q->head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}
void QPush(Queue* q, QDataType x)
{
	assert(q);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if(newnode==NULL)
    {
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (q->tail == NULL)
		q->tail = q->head = newnode;
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}
bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
void QPop(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		Qnode* del = q->head;
		q->head = q->head->next;
		free(del);
		del= NULL;
		q->size--;
	}
}
QDataType QFront(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->head->data;
}
QDataType QBack(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->tail->data;
}
size_t QSize(Queue* q)
{
	assert(q);
	return q->size;
}