首页 > 代码库 > 算法导论------------栈(stack)简单的数组实现

算法导论------------栈(stack)简单的数组实现

栈和队列都是动态集合,元素的出入是规定好的。栈规定元素是先进后出(FILO),队列规定元素是先进先出(FIFO)。栈和队列的实现可以采用数组和链表进行实现。在标准模块库STL中有具体的应用,可以参考http://www.cplusplus.com/reference/

栈的基本操作包括入栈push和出栈pop,栈有一个栈顶指针top,指向最新如栈的元素,入栈和出栈操作操作都是从栈顶端进行的。

队列的基本操作包括入队enqueue和出队dequeue,队列有队头head和队尾tail指针。元素总是从队头出,从队尾入。采用数组实现队列时候,为了合理利用空间,可以采用循环实现队列空间的有效利用。

         

栈的简单数组实现:

#include<iostream>

using namespace std;

struct stack
{
	int *s;
	int stackSize;
	int top;
};

//init stack
void init_stack(stack *s)
{
	s->stackSize = 100;
	s->s = (int*)malloc(sizeof(int)*s->stackSize);
	//s->s = new int();
	s->top = -1;
}

int stack_empty(stack s)
{
     return ((0 == s.stackSize) ? 1 : 0);
}

void push_stack(stack *s, int x)
{
	if (s->top == s->stackSize)
		cout << "up to overflow" << endl;
	else
	{
		s->top++;
		s->s[s->top] = x;
		s->stackSize++;
	}

}

void pop_stack(stack *s)
{
	if (0 == s->stackSize)
		cout << "down to overflow" << endl;
	else
	{
		s->top--;
		s->stackSize--;
	}
}

int top_stack(stack s)
{
	return s.s[s.top];
}


int main()
{
	stack s;
	init_stack(&s);

	for (int i = 0; i < 88; i++)
	{
		push_stack(&s, i);
	}

	for (int i = 0; i < 5; i++)
	{
		cout<<top_stack(s)<<" ";
		pop_stack(&s);
	}
	
}

队列的简单实现下次写。学习了一晚上,很累很累了.

算法导论------------栈(stack)简单的数组实现