数据结构严蔚敏版精简版-栈和队列以及c语言代码实现

1栈的定义和特权

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。

注：虽然说栈的实现就是一端插入和删除，但不一定是在“表尾”，这个“表尾”是广义的。

头插法实现链栈

尾插法实现链栈

因此，对栈来说，表尾端有其特殊含义，称为栈顶(top),相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈。

2队列的定义和特权

和栈相反，队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表 的一端进行插入，而在另一端删除元素。

如果入队序列为1，2，3，4出队序列也为1，2，3，4

队列在程序设计中也经常出现。一个最典型的 例子就是操作系统中的作业排队。在允许多道程序 运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求 输入的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出 做输出操作。凡是申请输出的作业都从队尾进入队列。

python实现LRU置换算法和先进先出算法

2.1循环队列

假设当前队列分配的最大空间为6,则当队列处于图d所示的状态时不可再继续 插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实 上，此时队列的实际可用空间并未占满，所以这种现象称 为“假溢出＂。这是由＂队尾入队，队头出队”这种受限制 的操作造成的。

最常用的方式是少用一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队 空的条件不变， 即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等 千头指针，则认为队满。因此，在循环队列中队空和队满的条件是：

队空的条件： Q.front = Q.rear

队满的条件： (Q rear+ 1)%M心CQSIZE= Q.front

入队尾指针变化：Q.front=(Q.front+1)%m

出队头指针变化：Q.front=(Q.front+1)%m

void EnQueue(Queue *Q,Elemtype x)//入队 
{
	if((Q->tail+1)%MAX_QUEUE==Q->front)
		{
		printf("已满\n");
		return;
		}
	Q->base[Q->tail]=x;
	Q->tail=(Q->tail+1)%MAX_QUEUE;
	printf("%d已经入队\n",x); 
}
void DeQueue(Queue *Q)//出队 
{	printf("%d出队\n",Q->base[Q->front]);
	Q->front=(Q->front+1)%MAX_QUEUE;
}

3栈和队列的实现c语言

3.1顺序栈的实现

#define STACK_INC_SIZE 3
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include <iostream>
#define MAX_SIZE 8

#define Elemtype char 
typedef struct stack{
	Elemtype *base;
	int top;
	int stacksize;
}Sqstack;

void Initstack(Sqstack *S)//初始化 
{
	S->base=(Elemtype*)malloc(sizeof(Elemtype)*MAX_SIZE);
	S->stacksize=8;
	S->top=0; 
 } 
 void show(Sqstack *S)//查看栈内元素 
 {
 	for(int i=S->top-1;i>=0;i--)
 	{
 		printf("%d\n",S->base[i]);
	}
 }
 bool IsFull(Sqstack *S)//判断是否满 
 {
 	return S->top>=S->stacksize; 
  } 
 bool IsEmpty(Sqstack *S)//判断是否为空栈 
 {
 	return S->top==0;
 }
 bool Inc(Sqstack *s)//栈满了则扩容，如果内存不够扩容则失败 
 {
 	Elemtype *newbase=(Elemtype*)realloc(s->base,sizeof(Elemtype)*(s->stacksize+STACK_INC_SIZE));
 	if(newbase==NULL)
 	{
 		printf("满了");
		 return false; 
	 }
	 s->base=newbase;
	 s->stacksize+=STACK_INC_SIZE;
	 return true;
 }
 
 void push(Sqstack *S,Elemtype x)//入栈 
 {
	if(IsFull(S)&&!Inc(S))
	{
		printf("满了,%d不能入栈\n",x);
		return;
	}
	S->base[S->top++]=x;
 }
 void pop(Sqstack *S)//出栈 
 {
 	if(IsEmpty(S))
 	{
 		printf("空的");
 		return;
	 }
	 S->top--;
 }
Elemtype Gettop(Sqstack *S) //获取栈顶元素 
 {
 	if(IsEmpty(S))
 	{
 		return false;
	 }
	 return S->base[S->top-1];
 }
 int length(Sqstack *S)//长度 
 {
 	return S->top;
 }
 void clear(Sqstack *S)//清空栈 
 {
 	S->top=0;
 }
 void destory(Sqstack *S)//销毁栈 
 {
 	free(S->base);
 	S->base=NULL;
 	S->stacksize=S->top==0;
 }
 
void conversion(int value)//进制转换 
{	Sqstack s;
	Initstack(&s);
	
	while(value)
	{
		push(&s,value%8);
		value=value/8;
	}
	while(!IsEmpty(&s))
{	int v;
	v=Gettop(&s);
	pop(&s);
	printf("%d",v);
	}	
}

bool Cheack(char *str)//括号匹配 
{ char v;
	Sqstack s;
	Initstack(&s);
	while(*str !='0')
	{
		if(*str=='['||*str=='(')
		{
			push(&s,*str);
		}
		else if(*str==']')
	{
		 v=Gettop(&s);
		if(v!='[')
			return false;
			pop(&s);
	}
	else if(*str==')')
	{
		 v=Gettop(&s);
		if(v!='(')
			return false;
			pop(&s);
	}
	++str;
	}
	return IsEmpty(&s);
}
int main(void)
{
	char *str="[())]";
	bool flag=Cheack(str);
	if(flag)
	{
		printf("OK\n");
	}
	else{
		printf("False");
	}
	
	
 } 
/*
int main()
{
	Elemtype Itim;
	Sqstack S;
	Initstack(&S);
	//conversion(13456);
	/*for(int i=1;i<=10;i++)
	push(&S,i);
	show(&S);
	Itim=Gettop(&S);
	printf("%d出栈\n",Itim);
	pop(&S);
	show(&S);
	}*/

3.2队列的实现

由于队列的实现比较简单，文章的开头就给出了2种链栈的实现方式，由于循环队列一直是队列的热门考点，这里只实现循环队列。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define Elemtype int
#define MAX_QUEUE 8//最大数量为8个 
typedef struct Queue{
	Elemtype *base;//基地址 
	int front;//队头头 
	int tail;//队尾 
}Queue;

void InitQueue(Queue *Q)//初始化队列 
{
	Q->base=(Elemtype*)malloc(sizeof(Elemtype)*MAX_QUEUE);
	Q->front=Q->tail=0;
}

void EnQueue(Queue *Q,Elemtype x)//入队 
{
	if((Q->tail+1)%MAX_QUEUE==Q->front)
		{
		printf("已满\n");
		return;
		}
	Q->base[Q->tail]=x;
	Q->tail=(Q->tail+1)%MAX_QUEUE;
	printf("%d已经入队\n",x); 
}

void show(Queue *Q)//展示队列 
{
	for(int i=Q->front;i!=Q->tail;)
	{
	
	printf("%d  ",Q->base[i]);
	i=(i+1)%MAX_QUEUE;
	}
	
	printf("\n");
}
void DeQueue(Queue *Q)//出队 
{	printf("%d出队\n",Q->base[Q->front]);
	Q->front=(Q->front+1)%MAX_QUEUE;
}
int lenQueue(Queue *Q) 
{
	return (Q->tail-Q->front);
}
void Gethead(Queue *Q,Elemtype *x)//获取对头元素 
{
if(Q->front==Q->tail)
	return;
	
	*x=Q->base[Q->front];
}
void ClearQueue(Queue *Q)//清空 
{
	Q->front=Q->tail=0;
}
void DestroyQueue(Queue *Q)//销毁 
{
	ClearQueue(Q);
	free(Q->base);
	Q->base=NULL;
}

int main()
{	int x;
	Queue Q;
	InitQueue(&Q);
	EnQueue(&Q,1);
	EnQueue(&Q,2);
	EnQueue(&Q,3);
	EnQueue(&Q,4);
	DeQueue(&Q);
	show(&Q);
	printf("队列长%d\n",lenQueue(&Q));
	Gethead(&Q,&x);
	printf("队头元素为%d\n",x);
}