栈与队列的简单实现(stack and queue)

一 - 栈的概念

        栈，又名堆栈，属于运算受限制的线性表，讲究先进先出。

        举个例子，我们经常乘坐的电梯，先进去的人往往会被挤到最里面，而最后进来的人刚好到了门口。那么出电梯的时候最后进来的人肯定是先出去的。

        再举个例子，手枪的弹夹，先按入弹夹的子弹肯定是最后一个打出去的，而最后按入弹夹的子弹肯定是第一个打出去的。

☟手枪弹夹的填弹与射击图☟

 这两个例子描述的都是栈，现在对栈的性质有所了解了吧。

        栈的性质：栈是一种先进先出的线性表。

        栈的分类：

                Ⅰ 顺序存储结构：单栈和共享栈

                Ⅱ 链式存储结构

        共享栈：即两个顺序栈共享存储空间。

        栈的顺序结构与链式结构的区别：顺序结构适合数据元素不大的情况，而链式结构适合数据元素变化比较大的情况。这是为什么呢？是因为顺序结构需要事先估计存储大小，而链式结构无需事先估计存储大小。

二 - 栈的相关操作

☟栈的操作☟

定义

queue <数据类型> a;//定义一个名叫a的栈。

压入

a.push(item);//在栈a的栈顶压入新成员

弹出

a.pop()//将a的栈顶元素弹出

判断是否为空

a.empty();//判断a是否为空，如果是，则返回true，否则返回false。

 返回栈顶值

a.top();//返回栈a的栈顶值

返回栈的元素个数

a.size();//返回栈a的元素个数

☟样例操作代码☟

#include 
#include 
using namespace std;
int main()
{
	stack <int> a;//定义一个int型的栈a
	a.push(1);//将1压入栈a
	a.pop();//将a的栈顶弹出
	int tmp=a.top();//将a的栈顶的值返回给tmp
	bool flag=a.empty();//如果a是空的，flag就时true，否则flag就是false。
	int len=a.size();//将栈a里的元素个数反馈给len
	return 0;
}

三 - 顺序存储栈

        顺序存储栈，也是用数组完成的。

        先开辟一片内存，每push一个新元素，top值就加1。

下面我们开始吧！

定义

#define STACK_SIZE 10
typedef struct stack
{
	ElemType data[STACK_SIZE];//data 栈数据空间
	int top;//栈顶指针
}stack;*pstack

初始化

void init(pstack pst)
{
	if(pst!=NULL)
	{
	    pst->top = 0;
	}
}

压栈

        首先，需要先判断栈是否满了。

int full(pstack pst)
{
	rerurn pst->top == STACK_SIZE ?1:0;
}

        然后再压栈

int push(pstack pst ,ElemType val)
{
	if(full(pst))
	{
	    return 0;
	}
	pst->data[pst->top] = val;
	pst->top++;
	return 1;
}

出栈

        首先要判断栈是否为空。

int empty(pstack pst)
{
	return pst->top == 0 ? 1: 0;
}

        然后，在出栈

int pop(pstack pst)//只删除元素，不获取元素
{
	if(empty(pst))
	{
	    return 0;
	}
	pst->top--;//data[top - 1]是无法将元素删除的。我们只需要将top--，就可以删除元素。
	return 1;
}

获取栈顶元素

//返回值返回状态  形参把栈顶元素带出
int gettop(pstack pst,ElemType* prt)//拿到栈顶元素，不删除元素
{
	if(empty(pst))//栈空
	{
	return 0;
	}
	*prt = pst->data[pst->top-1];
	return 1;
}

四 - 链式存储栈

我们都知道栈有栈顶指针，链表有头指针，这两者是缺一不可的，所以在进行链栈的设计的时候，我们就把栈顶放在单链表的头部。从而方便我们的插入和删除的操作。那么链栈的基本结构如下所示：

 现在我们写一下代码吧。

定义

typedef int ElemType;
typedef struct Node
{
	ElemType data;
	struct Node* next;
}Node,stack,*pstack;

 初始化

void init(pstack pst)
{
	if(pst!=NULL)
	{
	    pst->next = NULL;
	}
}

压栈

由于是链式结构，所以我们不需要判断栈是否满了。插入新节点需要插入一个新节点，所以我们写一个购买节点的函数。

Node* buyNode(ElemType val)
{
	Node* pnewnode = (Node*)malloc(sizeof(Node));
	pnewnode->data = val;
	pnewnode->next = NULL;
}

图1是本来的栈，现在来了一个新节点，我们把新节点和a[n]连接起来，再修改栈顶即可（如图2所示）。

          

图1-原来的栈的样子                                  图2-插入新节点的操作。 

现在我们可以添加元素了

void push(pstack pst,ElemType val)//元素做一个链表的头插
{
	Node* pnewnode = buyNode(val);
	pnewnode->next = pst->next;
	pst->next = pnewnode;
}

出栈

我们要先判断栈是否为空

int empty(pstack pst)
{
	return pst->next == NULL ?  1 : 0;
}

把上面的图1和图2反过来就是pop的过程。

int pop(pstack pst)
{
	if(empty(pst))
	{
	    return 0;
	}
	Node* pcur = pst->next;//第一个数据结点
	pst->next = pcur->next;
	free(pcur);
	return 1;
}

获取栈顶元素

int gettop(patsck pst,ElemType* prt)
{
	if(empty(pst))
	{
	    return 0;
	}
	*prt = pst->next->data;//第一个数据结点的数据
	return 1；
}

摧毁函数

由于是链式结构，所以我们要摧毁栈。

void destory(pstack pst)
{
	Node* pcur = pst->next;
	Node* pnext = NULL;
	while(pcur !=NULL)
	{
	    pnext = pcur->next;
	    free(pcur);
	    pcur = pnext;
	}
	pst->next = NULL;
}

好啦，这就是栈的全部内容啦，有没有觉得对栈更了解了呢？感谢大家的阅读。