data structure——栈和队列

栈和队列的特点是：栈(stack)是先进后出，而队列是先进先出。

栈的不同形式的定义：

  • 顺序栈的定义：
    1
    2
    3
    4
    5
    typedef struct
    {
    	int data[maxsize];  //存放栈中元素
    	int top;  //注意这是栈顶指针，这个指针是用来指数组中的元素的，不是在结点中的指针域
    }
  • 链栈结点定义：(即用链表来存储栈)
    1
    2
    3
    4
    5
    typedef struct LNode
    {
    	int data;  //数据域
    	struct LNode *next;  //指针域
    }LNode;

顺序栈的一些操作：

  • 初始化栈

    1
    2
    3
    4
    void initStack(SqStack &st)
    {
    	st.top=-1;  //栈顶指针设置为-1
    }

    或者可以简写：int stack[maxsize-1];int top==-1;

  • 判断栈空

    1
    2
    3
    4
    5
    6
    7
    int isEmpty(SqStack st)
    {
    	if(st.top==maxsize-1)
    		return 1;
    	else
    		return 0;
    }

  • 进栈

    1
    2
    3
    4
    5
    6
    7
    8
    int push(SqStack &st,int x)
    {
    	if(st.top==-1)
    		return 0;
    	++(st.top);
    	st.data[st.top]=x;
    		return 1;
    }

    或者也可以简写：stack[++top]=x;

  • 出栈

    1
    2
    3
    4
    5
    6
    7
    8
    int pop(SqStack &st, int x)
    {
    	if(st.top==-1)
    		return 0;
    	x=st.data[st.top];
    	--(st.top);
    	return 1;
    }

    或者也可以简写：x=stack[top--];

链栈的一些操作:

  • 初始化链栈
    1
    2
    3
    4
    5
    void initStack(LNode *&lst)
    {
    	lst=(LNode* )malloc(sizeof(LNode));  //制造一个头结点
    	lst->next=NULL;
    }
  • 判断栈空
    1
    2
    3
    4
    5
    6
    7
    int isEmpty(LNode *lst)
    {
    	if(lst->next=NULL)
    		return 0;
    	else
    		return 1;
    }
  • 进栈操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void push(LNode *lst,int x)
    {
    	LNode *p;
    	p=(LNode *)malloc(sizeof(LNode));
    	p->next=NULL;
    	p->data=x;
    	p->next=lst->next;
    	lst->next=p;
    }
  • 出栈操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void pop(LNode *lst, int &x)
    {
    	LNode *p;
    	if(lst->next==NULL)
    		return 0;
    	p->next=lst->next;
    	p->data=x;
    	lst->next=p->next;
    	free(p);
    	return 1;
    }

队列的不同形式的定义：

  • 顺序队列的定义：
    1
    2
    3
    4
    5
    6
    typedef struct
    {
    	int data[maxsize];  //用一个数组存储数据
    	int front;  //队首指针
    	int rear;  //队尾指针
    }sqQueue;
  • 链队定义：
    队结点类型定义：
    1
    2
    3
    4
    5
    typedef struct QNode
    {
    	int data;  //数据域
    	struct QNode *next;  //指针域
    }QNode;
    链队类型定义：
    1
    2
    3
    4
    5
    typedef struct
    {
    	QNode *front;  //队头指针
    	QNode *rear;  //队尾指针
    }LiQueue;

循环队列的一些操作:

  • 初始化
    1
    2
    3
    4
    void initQueue(SqQueue &qu)
    {
    	qu.front=qu.rear=0;
    }
  • 判断队空：
    1
    2
    3
    4
    5
    6
    7
    void isQueueEmpty(sqQueue qu)
    {
    	if(qu.rear=qu.front)
    		return 1;
    	else
    		return 0;
    }
  • 进队：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void enQueue(sqQueue &qu,int x)
    {
    	if((qu.rear+1)%maxsize==qu.front)
    		return 0;
    	else
    	{
    		qu.rear=(qu.rear+1)%maxsize;
    		qu.data[qu.rear]=x;
    		return 1;
    	}
    }
  • 出队：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void deQueue(sqQueue &qu,int x)
    {
    	if(qu.front==qu.rear)
    		return 0;
    	else
    	{
    		qu.front=(qu.front+1)%maxsize;
    		x=qu.data[qu.front];
    		return 1;
    	}
    }

链队的一些操作：

  • 初始化
    1
    2
    3
    4
    5
    void initQueue(LiQueue *&lqu)
    {
    	lqu=(LiQueue *)malloc(sizeof(LiQueue));
    	lqu->front=lqu->rear=NULL;
    }
  • 判断队空
    1
    2
    3
    4
    5
    6
    7
    int isQueueEmpty(LiQueue *lqu)
    {
     	if(lqu->front==NULL||lqu->rear==NULL)
     		return 1;
     	else
     		return 0;
    }
  • 入队
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void enQueue(LiQueue *lqu,int x)
    {
    	QNode *p;  //指针p是另一个结构体而来的
    	p=(QNode *)malloc(sizeof(QNode));
    	p->data=x;
    	p->next=NULL;
    	if(lqu->rear==NULL)
    		lqu->front=lqu->rear=p;
    	else
    	{
    		lqu->rear->next=p;  //将新节点连接至队尾，rear指向它
    		lqu->rear=p;
    	}

    }
  • 出队
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void deQueue(LiQueue *lqu ,int &x)
    {
    	QNode *p;
    	if(lst->rear=NULL)
    		return 0;
    	else
    		p=lst->front;
    	if (lqu->front==lqu->rear)
    		lqu->front=lqu->rear==NULL;
    	else
    		lqu->front=lqu->front->next;
    	x=p->data;
    	free(p);
    	return 1;
    }

应用

  • 顺序栈的应用

1.设计一个算法，判断一个表达式中的括号是否正确的配对，表达式已经存入字符数组exp[]中，表达式中的字符个数是n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int match(char exp[],int n)
{
	char stack[maxsize-1];
	int top==-1;
	int i;
	for(i=0;i<n;++i)
	{
		if(exp[i]=='(')
			stack[++top]='(';
		if(exp[i]==')')	
		{
			if(top==-1)
				return 0;
			else
				--top;
		}
	}
	if(top==-1)
		return 1;
	else
		return 0;
}

此列题很好的说明了栈是一种有效处理”先进后出”的一种数据类型，也就是说，当以后遇到一种问题，在处理问题的过程中如果出现了一个子问题，那么先解决了这个子问题再来处理这个问题的处理思路可以使用栈这个模型去解决问题。

2.编写一个函数，求后缀式的数值，其中后缀式存于一个字符数组exp中，exp中最后一个字符为\0，作为结束符，并假设后缀式中的数字都只有一位。（出现的除法的结果都按一位存储）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int jisuan(int a,char jisuan,int b)
{
	if('jisuan'='+') return a+b;
	if('jisuan'='-') return a-b;
	if('jisuan'='*') return a*b;
	if('jisuan'='/')
	{
		if(b==0)
		{
			cout<<"error"<<endl;
			return 0;
		}
		else
			return a/b;
	}
}

int houzhui(char exp[])
{
	int i,a,b,c;
	char yunsuanfu;
	int stack[maxsize-1];
	int top=-1;
	for(i=0;exp[i]!='\0;++i)
	{
		if(exp[i]>='0'&&exp[i]<='9')
			stack[++top]=exp[i]-'0';
		else
		{
			yunsuanfu=exp[i];
			b=stack[top--];
			a=stack[top--];
			c=jisuan(a,yuansuanfu,b);
			stack[++top]=c;
		}


	}
	return stack[top];  //这句话有点不能理解
}

3.用不带头结点的单链表存储链栈，设置初始化栈，判断栈是否为空，进栈和出栈等相应的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void initStack1(LNode *&lst)  //初始化栈
{
	lst=NULL;
}

int isEmpty1(LNode *lst)  //判断是否为空
{
	if (lst==NULL)
		return 1;
	else
		return 0;
}

void pop1(LNode *lst,int x)  //进栈
{
	LNode *p;
	p=(LNode *)malloc(sizeof(LNode));
	p->next=NULL;
	p->data=x;
	p->next=lst;
	lst=p;
}

void push1(LNode *lst,int x)  //出栈
{
	LNode *p;
	if (lst==NULL)
		return 0;
	x=p->data;
	lst=p->next;
	free(p);
	return 1;
}

下面是例题：
1.顺序栈s0和s1共享了一个存储区elem[0,1,..,maxsize-1]。是设计共享栈s0,s1以及有关共享栈的入栈和出栈操作的算法，假设元素为int型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
typedef struct  //结构体定义
{
	int elem[maxsize];
	int top[2];	
}sqstack;

int push(sqstack &st,int stNo,int x)
{
	if(st.top[0]+1<st.top[1])  //判断是否栈满
	{
		if(stNo==0)
		{
			++(st.top[0]);
			st.elem[st.top[0]]=x;
			return 1;
		}
		else if(stNo==1)
		{
			--(st.top[1]);
			st.elem[st.top[1]]=x;
			return 1;
		}
		return -1;  //如果栈的编号既不是0也不是1的话就返回-1
	}
	else return 0;
}

int pop(sqstack &st ,int x)
{
	if(stNo==0)
	{
		if(st.top[0]!=-1)
		{
			x=st.elem[st.top[0]];
			--(st.top[0]);
			return 1;
		}
		else return 0;
	}
	else if(stNo=1)
	{
		if(st.top[1]!=maxsize)
		{
			x=st.elem[st.top[1]];
			++(st.top[1]);
			return 1;
		}
		return 0;
	}
	else return -1;
}

2.利用两个站s1,s2来模拟一个队列，假设栈中的元素为int型，栈中元素最多为maxsize。已知栈的3个运算定义如下：
push(ST,x):元素x入st栈
pop(ST,&x):st栈顶元素出栈，赋给元素x
isEmpty(ST):判断st栈是否为空
如何利用栈的运算来实现队列的3个运算，（元素入队列）enQueue,（元素出队列）deQueue,（判断栈是否为空）isQueueEmpty。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
int enQueue(sqstack &s1,sqstack &s2,int x)
{
	int y;  //这里为什么还要一个y
	if(s1.top==maxsize-1)
	{
		if(!isEmpty(s2))
			return 0;
		else if(isEmpty(s2))
		{
			while(!isEmpty(s1))
			{
				pop(s1,y);
				push(s2,y);
			}
			push(s1,x);
			return 1;
		}
	}
	else
	{
		push(s1,x);
		return 1;
	}
}
int deQueue(SqStack &s2,sqstack &s1,int &x)
{
	int y;
	if(!isEmpty(s2))
	{
		pop(s2,y);
		return 1;
	}
	else
	{
		if(isEmpty(s1))
			return 0;
		else
		{
			while(!isEmpty(s1))
			{
				pop(s1,y);
				push(s1,y);
			}
			pop(s2,x);
			return 1;
		}
	}
}
int isQueueEmpty(sqstack s1,sqstack s2)
{
	if(isEmpty(s1)&&isEmpty(s2))
		return 1;
	else
		return 0;
}

其实本题其实主要的工作是将栈的”先进后出”的特性变为”先进先出”。

3.假设一I,O分别表示入栈和出栈的操作，写出一个算法，判定给出的操作序列是否合法，若合法则返回1否则返回0假定被判定的操作序列已经存入一维数组ch[]中，操作序列以“\0”为结束符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int judge(char[])
{
	int i=0;
	int I=0,O=0;
	while(ch[i]!='\0')
	{
		if(ch[i]='I')
			++I;
		if(ch[i]='O')
			++O;
		if(O>I)
			return 0;
		++i;
	}
	if(I!=O)  //判断入栈和出栈的操作次数是否相同，如果不同就不合法
		return 0;
	else
		return 1;
}

4.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队和出队的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void enQueue(LNode *&rear,int x)
{
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=x;
	s->next=rear->next; //有疑问。。。
	rear->next=s;  //有疑问。。。
	rear=s;
}	

void deQueue(LNode *&rear,int &x)
{
	LNode *s;
	if(rear->next==rear)
		return 0;
	else
	{
		s=rear->next->next;  //s指向开始结点
		rear->next->next=s->next;  //rear指向s指针指向的下一个结点
		x=s->data;
		if(s==rear)
			rear=rear->next;
		free(s);
		return 1;
	}
}

5.如果允许在循环队列的两端都可以进行插入和删除操作，要求：写出循环队列的类型定义，写出从队尾删除和从对头插入的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
typedef struct
{
	int data[maxsize];
	int front,rear;
}cycqueue;

int deQueue(cycqueue &Q,int &x)  //从队尾删除
{
	if(Q.front==Q.rear)
		return 0;
	else
	{	
		x=Q.data[Q.rear];
		Q.rear=(Q.rear-1+maxsize)%maxsize;  //这里要注意一下
		return 1;
	}
}

int enQueue(cycqueue &Q,int &x)  //从队头插入
{
	if(Q.rear==(Q.front-1+maxsize)%maxsize)
		return 0;
	else
	{
		Q.data[Q.front]=x;  //约定front指针是指向队头元素的前一个位置
		Q.front=(Q.front-1+maxsize)%maxsize;  //所以这里是先赋值后移动front指针
		return 1;
	}

}

6.设计一个循环队列，用front和rear分别作为队头和队尾指针，用一个标志tag表示队列是否为空当tag为1时队不空，为0时表示为空。这样就可以用front==rear来作为队满的条件。要求设计出队列的结构和相关的基本运算（队列元素为int型）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
typedef struct
{
	int data[maxsize];
	int front,rear;
	int tag;
}Queue;


void initQueue(Queue &qu)  //初始化
{
	qu.front=qu.rear=0;
	qu.tag=0;
}

int isQueueEmpty(Queue qu)  //判空
{
	if(qu.front==qu.rear&&qu.tag==0)
		return 1;
	else
		return 0;
}

int QueueFull(Queue qu)  //判满
{
	if(qu.tag==1&&qu.front==qu.rear)
		return 1;
	else
		return 0;
}

int enQueue(Queue &qu,int x)
{
	if(QueueFull(qu)==1)
		return 0;
	else
	{
		qu.rear=(qu.rear+1)%maxsize;
		qu.data[qu.rear]=x;
		qu.tag=1;
		return 1;
	}
}

int deQueue(Queue &qu,int &x)
{
	if(isQueueEmpty(qu)==1)
		return 0;
	else
	{
		qu.front=(qu.front+1)%maxsize;
		x=qu.data[qu.front];
		qu.tag=0;
		return 1;
	}
}

7.编写一个算法，将一个非负的十进制整数N转换为一个二进制数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int BaseTrans(int N)
{
	int i,result=0;
	int stack[maxsize],top=-1;
	while(N!=0)
	{
		i=N%2;
		i=N/2;
		stack[++top]=i;
	}
	while(top!=1)
	{
		i=stack[top];
		--top;
		result=result*10+i;
	}
	return result;
}

8.试编写一个算法，检查一个程序中的花括号，方括号，小括号是否匹配，若全部匹配则返回1，否则就返回0.对于程序中出现的单引号和双引号不进行括号匹配。39为单引号的ASCII值，34为双引号ASCII值，单双引号出现必定成双出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int pipeikuohao(char f[])
{
	stack S,char ch;
	char* p=f;
	while(p!='\0')
	{
		if(*p==39)
		{
			++p;  //跳过第一个单引号
			while(*p!=39)
				++p;  //跳过单引号中的元素
			++p;  //跳过第二个单引号
		}
		else if (*p==34)
		{
			++p;  //跳过第一个双引号
			while(*p!=34)
				++p;  //跳过双引号中的元素
			++p;  //跳过第二个双引号，这里要注意程序的执行流程。
		}
		else
		{
			switch(*p)
			{
				case '{':
				case '[':
				case '(': push(S,*p);  //如果是{，[,(这些左括号，就入栈
				break;
				case '}': getTop(S,ch);  //当遇到右括号了，读取此时的栈顶元素(getTop)，
					if(ch=='{')  //如果此时栈顶元素是相应的左括号，
						pop(S,ch);  //就出栈
					else
						return 0;
				break;
				case ']': getTop(S,ch);
					if(ch==']')
						pop(S.ch);
					else
						return 0;
				break;
				case ')': getTop(S,ch);
					if(ch==')')
						pop(S,ch);
					else
						return 0;
			}
			++p;
		}
	}
	if(isEmpty(S))
		return 1;
	else
		return 0;
}