3栈和队列

栈和队列

堆栈（简称栈）：先入后出，后入先出

存储方式：

一个连续的内存单元（类似数组），栈底指针不动，栈顶指针随着数据进出移动。当数据删除时，该空间将被标记为可使用

数组实现：

#include<stdio.h>
#include<stdlib.h>
#define SIZE 5
int* stack;//栈顶指针
int top;//栈顶下标
int end;//栈底下标
int maxSize;

void initstack()
{
    stack=(int*)malloc(sizeof(int)*SIZE);
    end=-1;
    top=-1;
    maxSize=SIZE;
}

//压栈（入栈）
void push(int key)
{
    //判断栈满
    if(top==maxSize)
    {
        return;
	}
    else
    {
        top++;
        stack[top]=key;
    }
}

//出栈
void pull()
{
    if(top==-1)
    {
        return;
	}
    else
    {
        top--;
    }
}

队列：先进先出，后进后出

队尾：插入

队首：删除

单向队列

实现方式

队首指针与队尾指针

入队：移动队尾指针

出队：移动队首指针

注：

为了解决“假溢出”的情况，将队列首尾相接（队尾指针来到队尾，取模）

rear=(rear+1)%maxSize

移动方式：

先放入数据，再移动尾指针

先删除数据，再移动头指针

注：

为了解决队空与队满的相同判定条件问题，留出一个空间（队首指针前的那个）不使用

rear==front 队空

rear=(rear+1)%maxSize==front 队满

#include<stdio.h>
#include<stdlib.h>
#define SIZE 5
int *queue;
int front;
int end;
int maxSize;

void Initqueue()
{
    queue=(int *)malloc(sizeof(int)*SIZE);
    maxSize=SIZE;
    front=end=0;
}

void insert_queue(int key)
{
    if(isFull())
    {
        return;
	}
    else
    {
        end=(end+1)%maxSize;
        queue[end]=key;
    }
}

void delete_queue(int key)
{
    if(isEmpty())
    {
        return;
	}
    else
    {
        front=(front+1)%maxSize;
        
    }
    
}

int isFull()
{
    if((end+1)%maxSize==front)
    {
        return 1;
	}
    else
        return 0;
}

int isEmpty()
{
    if(end==front)
    {
        return 1;
	}
    else
        return 0;
}

双向队列

允许从一边进一边出

注：先选定一边进，再选定一边出，之后只能遵循这个操作（根据选择成为栈和单向队列）

数组

#include<stdio.h>
#include<stdlib.h>
#define SIZE 5
int *queue;
int left;
int right;
int maxSize;
int size;

void Init()
{
    queue=(int *)malloc(sizeof(int)*SIZE);
    size=0;
    maxSize=SIZE:
    
}

int isFull()
{
    if(size==maxSize)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isEmpty()
{
    if(size==0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
void left_insert(int key)
{
    if(isFull())
    {
        
    }
    else
    {
        if(isEmpty())
        {
            left=right=maxSize-1;
            queue[--left]=key;
        }
        else
        {
            if(left==0)
            {
                left=maxSize;
            }
            queue[--left]=key;
            
        }
    }
}
void right_insert(int key)
{
    if(isFull())
    {
        
    }
    else
    {
        if(isEmpty())
        {
            left=right=0;
            queue[++right]=key;
        }
        else
        {
            if(right==maxSize-1)
            {
                right=-1;
            }
            queue[++right]=key;
            
        }
        size++;
    }
}
void left_delete()
{
    if(isEmpty())
    {
        
    }
    else
    {
        if(left==maxSize-1)
        {
            left=0;
        }
        else
        {
            left++;
        }
        size--;
    }
}
void right_delete()
{
    if(isEmpty())
    {
        
    }
    else
    {
        if(right==0)
        {
            right=maxSize-1;
        }
        else
        {
            right--;
        }
        size--;
    }
}

链表

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

typedef struct Queue{
    struct Queue* next;
    struct Queue * front;
    int element;
}queue;

queue * left;
queue * right;
int size;

void InitQueue()
{
    left=(queue*)malloc(sizeof(queue));
    right=(queue*)malloc(sizeof(queue));
    left->next=right;
    right->front=left;
    left->front=NULL;
    right->next=NULL;
    size=0;
}

void left_insert(int key)
{
    queue* temp=(queue*)malloc(sizeof(queue));
    temp->next=left->next;
    temp->front=left;
    left->next=temp;
    temp->next->front=temp;
    size++;
}

void right_insert(int key)
{
    queue* temp=(queue*)malloc(sizeof(queue));
    temp->next=right;
    temp->front=right->front;
    right->front=temp;
    temp->front->next=temp;
    size++;
}

void left_delete()
{
    if(size==0)
    {
        
    }
    else
    {
        queue* temp=left->next;
        temp->next->front=left;
        left->next=temp->next;
        size--;
        free(temp);
    }
}

void left_delete()
{
    if(size==0)
    {
        
    }
    else
    {
        queue* temp=right->front;
        temp->front->next=right;
        right->front=temp->front;
        size--;
        free(temp);
    }
}

发布于 2024-11-10