栈和队列 | 漫漫长夜

栈(Stack)

1.栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构

2.栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。

3.栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素。**

栈的概念.gif

进栈(Push)和出栈(Pop)

1.向栈中添加元素，此过程被称为”进栈”

进栈.gif

2.从栈中提取出指定元素，此过程被称为”出栈”

出栈.gif

栈的实现

顺序栈

//使用顺序栈实现二进制转换
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define  MAXSIZE   100   //根据需要自己定义MAXSIZE为顺序栈的最大存储容量
typedef struct stack
{
	int data[MAXSIZE];
	int top;
}SEQSTACK;

void initstack(SEQSTACK *s)//顺序栈初始化
{
	s->top=-1;	                         ;//将栈顶指针指向初始的位置
}

int empty(SEQSTACK *s)    //判断栈空
{
	if(s->top==-1)
		return 1;
	else 
		return 0;
}

void push(SEQSTACK *s,int x)//元素x进栈
{
	if(s->top==MAXSIZE-1)
		printf("存储空间已满，元素进栈失败！\n");
	else
	{
		 s->top++;                        ;//栈顶指针加1
         s->data[s->top]=x;                        ;//将元素x送到栈顶位置
	}		
}

int pop(SEQSTACK *s)//元素出栈，出栈元素用e返回
{
	int e;
	if(empty(s)==-1)
	{
		printf("栈中元素已空，出栈元素失败！\n");
	    return -99;
	}
	else
	{
	  	e=s->data[s->top];                         ;//将栈顶元素赋值给变量e
	  	s->top--;                       ;//栈顶指针减1
		return e;
	}

}

void conversion(SEQSTACK *s,int N,int r)  
   { //将十进制数N转换为r进制的数
    int   x;
    initstack(s);
	while (N!=0)  //此循环为入栈操作
    {  
      push(s,N%r);                          ;//将N除以r所得的余数压入栈 
	  N=N/r;                          ; //N整除r所得的商赋值给N
    } 
    
    while (!empty(s))  		//此循环为出栈操作
    {   
      x=pop(s);
      if(x==10)printf("A");
	  else if(x==11)printf("B");
	  else if(x==12)printf("C");
	  else if(x==13)printf("D");
	  else if(x==14)printf("E");
	  else if(x==15)printf("F");
	  else printf("%d",x);
    }
	printf("\n");
  }

void main()       
     {
		int number,r;    //number为待准备转换的十进制数，r为进制
		SEQSTACK stack;
		char choice;
		while(1)
		{
			printf("请输入一个十进制整数：");
			scanf("%d",&number);
			printf("选择将该数转换为几进制数(2，8，16)：");
			scanf("%d",&r);
			fflush(stdin);
			printf("转换后的结果为：");
			conversion(&stack,number,r);
			printf("是否继续？按N结束，其他任意键继续…");
			scanf("%c",&choice);
			system("cls");
		    if(choice=='N'||choice=='n')
				break;
		}
}

链栈

#include<stdio.h>
#include<stdlib.h> 
typedef struct LinkStack{
	int data;
	struct LinkStack *next;
}LStack;
LStack *CreateLStack(){
	LStack *S;
	S=(LStack*)malloc(sizeof(LStack));
	if(S==NULL)
	return S;
	else{	
		S->next=NULL;
		return S;
	}
}
void LStack_Push(LStack *S,int item){
	LStack *p,*r;
	p=(LStack*)malloc(sizeof(LStack));
	p->data=item;
	p->next=S->next;
	S->next=p;
}
int LStack_Pop(LStack *S,int item){
	LStack *p;
	p=S->next;
	S->next=p->next;
	item=p->data;
	free(p);
	return item;	
}
int main()
{
	LStack *S=CreateLStack();
	if(S==NULL)
	printf("申请空间失败");
	int i,num,j;
	printf("请输入个数");
	scanf("%d",&i);
	j=i;
	for(i;i>=1;i--)
	{
		scanf("%d",&num);
		LStack_Push(S,num);
	}
	printf("依次出栈\n");
	for(j;j>=1;j--)
	{
		printf("%d\n",LStack_Pop(S,num));
	}
	return 0; 
}

队列(Queue)

1.队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。

2.队列是一个先进先出的线性表，相应的也有顺序存储和链式存储两种方式。

进队(PushQueue)和出队(PopQueue)

进队

将该数据元素用节点包裹，例如新节点名称为 elem；
与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
最后移动 rear 指针指向该新节点，即 rear=elem；

进队.gif

出队

通过 front 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
将 p 节点（即要出队的队头节点）从链表中摘除；
释放节点 p，回收其所占的内存空间；

出队.gif

队列的实现

顺序队列

#include <stdio.h>
int enQueue(int *a,int rear,int data){
    a[rear]=data;
    rear++;
    return rear;
}
void deQueue(int *a,int front,int rear){
    //如果 front==rear，表示队列为空
    while (front!=rear) {
        printf("出队元素：%d\n",a[front]);
        front++;
    }
}
int main() {
    int a[100];
    int front,rear;
    //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
    front=rear=0;
    //入队
    rear=enQueue(a, rear, 1);
    rear=enQueue(a, rear, 2);
    rear=enQueue(a, rear, 3);
    rear=enQueue(a, rear, 4);
    //出队
    deQueue(a, front, rear);
    return 0;
}

链队列

//链队列基本操作
//根据实际处理数据的类型定义链队中结点的值域类型elemtype
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef int elemtype;
typedef  struct node		    //队列结点类型定义
{    elemtype data; 		    //队列的数据元素类型
     struct node  *next; 		//指向后继结点的指针
}NODE;
typedef struct 
{	                  //定义链队
    NODE *front,*rear;//定义链队队头和队尾指针
}LINKQUEUE;

void initqueue(LINKQUEUE *QL)//队列的初始化
{
	QL->front=(NODE *)malloc(sizeof(NODE));//队列为带头结点的链队列
	QL->front->next=NULL;
	QL->rear=QL->front;
}
LINKQUEUE  *pushqueue(LINKQUEUE *QL,elemtype x) 
{ //将元素x插入到链队列QL中，作为QL的新队尾
    NODE *p;
    p=(NODE*)malloc(sizeof(NODE));
    p->data=x;
    p->next=NULL;
    if(QL->rear==NULL){
    	QL->front=QL->rear=p;
    }
    else{
    	QL->rear->next=p;
    	QL->rear=p;
    }
	return QL;
}
elemtype popqueue(LINKQUEUE *QL)  
{  //若链队列不为空，则删除队头元素，返回其元素值
 	NODE *t;
 	elemtype x; 
	t=QL->front;
	if(QL->front==QL->rear)
 	return 0;
	else
 	QL->front=QL->front->next;
	x=t->next->data;
	free(t);
	return x;
}

void printqueue(LINKQUEUE *QL)//队列的显示
{
	NODE *p;
	p=QL->front->next;
	if(p==NULL)
		printf("队列空!");
	while(p!=NULL)
	{
		if(p->next==NULL)
		   printf("%d",p->data);
		else
           printf("%d<--",p->data);
	    p=p->next;
	}
	printf("\n");
}
void main()       
     {
	   LINKQUEUE *p;
	   int choice,elemdata,x=0;
	   p=(LINKQUEUE *)malloc(sizeof(LINKQUEUE));
	   initqueue(p);
	   while(1)
	   {
        printf("      欢迎使用队列操作小程序：\n");
	    printf("\t1、元素入队\n");
	    printf("\t2、元素出队\n");
	    printf("\t3、显示队列\n");
	    printf("\t4、清屏幕\n");
        printf("\t5、退出程序\n");
		printf("      请选择你的操作：");
	    scanf("%d",&choice);
	    switch(choice)
		{
	    case 1:printf("请输入进队元素：");
		       scanf("%d",&elemdata);
               p=pushqueue(p,elemdata);
			   printf("队列中的元素为：\n");
               printqueue(p);
			   system("pause");
		 	   break;
	    case 2:x=popqueue(p);
			   if(x!=0)
			      printf("元素%d出队!\n",x);
			   printf("队列中的元素为：\n");
               printqueue(p);
			   system("pause");
		       break;
	    case 3:printf("队列中的元素分别为：\n");
		       printqueue(p);
			   system("pause");
			   break;
	    case 4:system("cls");
			   break;
		case 5:return;
		}
		system("cls");
	   }
}