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

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;
}