二、實驗預習

1、順序棧：順序棧是棧的順序實現。順序棧是指利用順序存儲結構實現的棧。采用地址連續的存儲空間（數組)依次存儲棧中數據元素，由于入棧和出棧運算都是在棧頂進行，而棧底位置是固定不變的，可以將棧底位置設置在數組空間的起始處；棧頂位置是隨入棧和出棧操作而變化的，故需用一個整型變量top來記錄當前棧頂元素在數組中的位置。

2、鏈棧:鏈棧，即用鏈表實現棧存儲結構。鏈棧的實現思路同順序棧類似，順序棧是將數順序表（數組）的一端作為棧底，另一端為棧頂；鏈棧也如此，通常我們將鏈表的頭部作為棧頂，尾部作為棧底。

3、循環隊列：存儲在其中的隊列稱為循環隊列。循環隊列是把順序隊列首尾相連，把存儲隊列元素的表從邏輯上看成一個環，成為循環隊列。

4、鏈隊:鏈隊是采用鏈式存儲結構存儲隊列，鏈隊的特點就是不存在隊列滿上溢的情況。

三、實驗內容和要求

1、閱讀下面程序，將函數Push和函數Pop補充完整。要求輸入元素序列1 2 3 4 5 e，運行結果如下所示。

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10  /*存儲空間初始分配量*/
#define STACKINCREMENT 5  /*存儲空間分配增量*/
typedef  int ElemType; /*定義元素的類型*/
typedef struct{
    ElemType *base;
    ElemType *top;
    int stacksize;     /*當前已分配的存儲空間*/
}SqStack;

int InitStack(SqStack *S);   /*構造空棧*/
int push(SqStack *S,ElemType e); /*入棧*/
int Pop(SqStack *S,ElemType *e);  /*出棧*/
int CreateStack(SqStack *S);     /*創建棧*/
void PrintStack(SqStack *S);   /*出棧并輸出棧中元素*/

int InitStack(SqStack *S){
    S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
    if(!S->base) return ERROR;
    S->top=S->base;
    S->stacksize=STACK_INT_SIZE;
    return OK;
}/*InitStack*/

int Push(SqStack *S,ElemType e){
    
}/*Push*/

int Pop(SqStack *S,ElemType *e){
   
}/*Pop*/

int CreateStack(SqStack *S){
    int e;
    if(InitStack(S))
        printf("Init Success!\n");
    else{
        printf("Init Fail!\n");
        return ERROR;
    }
    printf("input data:(Terminated by inputing a character)\n");
    while(scanf("%d",&e))
        Push(S,e);
    return OK;
}/*CreateStack*/

void PrintStack(SqStack *S){
    ElemType e;
    while(Pop(S,&e))
        printf("%3d",e);
}/*Pop_and_Print*/

int main(){
    SqStack ss;
    printf("\n1-createStack\n");
    CreateStack(&ss);
    printf("\n2-Pop&Print\n");
    PrintStack(&ss);
    return 0;
}  

算法分析：因為當main函數調用PrintStack(&ss)時，程序轉到函數體中，而在該函數體內，又調用了intPop(SqStackS,ElemTypee)，此函數的功能是棧S的棧頂元素退棧并返回其值。所以輸入元素序列12345，輸出序列為54321。而這則體現了棧是只允許在表的一端進行操作的線性表并且具有先進后出的特性。

2、在第1題的程序中，編寫一個十進制轉換為二進制的數制轉換算法函數（要求利用棧來實現），并驗證其正確性。

實現代碼:

void conveshen(SqStack *S){
	ElemType n,h;
	int m=0,k=0;
	InitStack(S);
	printf("Input element\n");
	scanf("%d",&n);
	while(n){
		m++;
		Push(S,n%2);
		n=n/2;
	}
	while(k<m){
		k++;
		Pop(S,&h);
		printf("%d",h);
	}
}

int main(){
	SqStack S;
	conveshen(&S);
	printf("\n");
	return ERROR;
}

驗證

Input element
12
1100

3、閱讀并運行程序，并分析程序功能。

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define M 20
#define  elemtype  char
typedef struct
{
    elemtype stack[M];
    int top;
}
stacknode;
void init(stacknode *st);
void push(stacknode *st,elemtype x);
void pop(stacknode *st);

void init(stacknode *st)
{
    st->top=0;
}

void push(stacknode *st,elemtype x)
{
    if(st->top==M)
        printf("the stack is overflow!\n");
    else
    {
        st->top=st->top+1;
        st->stack[st->top]=x;
    }
}

void pop(stacknode *st)
{
if(st->top>0)  st->top--;
    else  printf(“Stack is Empty!\n”);
}

int main()
{
    char s[M];
    int i;
    stacknode *sp;
    printf("create a empty stack!\n");
    sp=malloc(sizeof(stacknode));
    init(sp);
    printf("input a expression:\n");
    gets(s);
    for(i=0;i<strlen(s);i++)
    {
        if(s[i]=='(')
            push(sp,s[i]);
        if(s[i]==')')
            pop(sp);
    }
    if(sp->top==0)
        printf("'('match')'!\n");
    else
        printf("'('not match')'!\n");
    return 0;
}

輸入：2+((c-d)6-(f-7)a)/6
運行結果：'('match')'!
輸入：a-((c-d)*6-(s/3-x)/2
運行結果：'('not match')'!
程序的基本功能：
判斷所輸入多項式的左右括號是否配對。

四、實驗小結

熟練掌握了棧的結構特性及其入棧，出棧操作,掌握了隊列的結構特性及其入隊、出隊的操作，掌握循環隊列的特點及其操作，收獲頗豐。