栈（一）——栈的基本操作

1.栈的简介

栈是一种后入先出的数据结构，一般包含两种最基本的操作：入栈（push）和出栈（pop）。

入栈操作：top指针上移，元素入栈。

出栈操作：top指针下移。

栈空的条件：top == bottom

栈满的条件：top == maxsize-1

2.有数据序列1 2 3一次存入一个栈stack中，则出栈顺序可以为以下四种：

1,2,3； 2,1,3； 3,2,1； 1,3,2.

3.任意输入一个十进制整数x(x<32768)，输出x的二进制值。

#include <stdio.h>

#define MAXSIZE	15

int main()
{
	int a[MAXSIZE];
	int bottom, top;
	int x;

	bottom = top = -1;
	printf("Please input x(0<=x<=32767):");
	scanf("%d", &x);
	while(x)
	{
		a[++top] = x%2;
		x /= 2;
	}
	while(-1 != top)
	{
		printf("%d ", a[top--]);
	}
	printf("\n");

	return 0;
}
           

4.判断一个C语言表达式的左右括号是否匹配，提示：将要判断的表达式用字符串输入。

#include <stdio.h>

#define MAXSIZE	100

int main()
{
	char a[MAXSIZE];
	int top = -1;
	int i;

	printf("Please input a expression:");
	gets(a);
	i = 0;
	while(a[i])
	{
		if('(' == a[i])
			top ++;
		else if(')' == a[i])
		{
			if(-1 == top)
				break;
			else
				top --;
		}
		i ++;
	}

	if('\0' == a[i] && -1 == top)
		printf("Match.\n");
	else
		printf("Not match.\n");
	return 0;
}
           

5.栈的基本操作——出栈和入栈

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

typedef struct st
{
	int maxsize;
	int top;
	int *pstack;
}stack;

void create_stack(stack *s, int ms);
void push(stack *s, int x);
int pop(stack *s);
void clear_stack(stack *s);

int main()
{
	stack s;
	int ms, i;
	int a[] = {13, 17, 15, 25};
	
	printf("Please input stack size:");
	scanf("%d", &ms);
	create_stack(&s, ms);
	for(i = 0; i < 4; i++)
		push(&s, a[i]);
	while(s.top != -1)
		printf("%d ", pop(&s));
	printf("\n");
	clear_stack(&s);

	return 0;
}

void create_stack(stack *s, int ms)
{
	s->maxsize = ms;
	s->top = -1;
	s->pstack = (int *)malloc(ms*sizeof(int));
}

void push(stack *s, int x)
{
	if(s->top < s->maxsize-1)
		s->pstack[++s->top] = x;
}

int pop(stack *s)
{
	if(s->top != -1)
		return s->pstack[s->top--];
}

void clear_stack(stack *s)
{
	s->maxsize = 0;
	s->top = -1;
	free(s->pstack);
	s->pstack = 0;
}