棧的基本概念及其順序棧的基本運算

//main.cpp
#include"seqstack.h"
int main(void)
{
	int i = 0;

	int k = 0;

	int a[10] = { 1,2,3,4,5,6,7,8,9,10 };

	seqstack* stack = (seqstack*)malloc(sizeof(seqstack));//申請記憶體空間

	element* element_value= (element*)malloc(sizeof(element));//申請記憶體空間

	initseqstack(stack);//棧初始化

	for (i = 0; i <5; i++)
	{
		pushstack(stack,a+i);//入棧

		printf("目前入棧元素：%d\n", *(a + i));

	}

	printf("\n");

	for (i = 0; i <4; i++)
	{
		popstack(stack, element_value);//出棧

		printf("目前出棧元素：%d\n", element_value->ment[i]);

	}

	printf("\n");
	
	printf("目前棧内元素：%d\n", stack->stack[stack->top]);

    free(stack);//釋放棧

	system("pause");

	return 0;

}
//seqstack.cpp
#include"seqstack.h"
/*
 * @file      seqstack.cpp
 * @function  棧初始化函數
 * @author    酸菜。
 * @date      2019-09-16
*/
int initseqstack(seqstack* stack)
{
	stack->length = 0;

	stack->top = -1;

	return 1;

}
/*
 * @file      seqstack.cpp
 * @function  入棧函數
 * @author    酸菜。
 * @date      2019-09-16
*/
int pushstack(seqstack* stack, int* value)
{
	if (stack->top == MAX - 1 || stack->length == MAX)
	{

		printf("棧以滿，無法入棧：！\n");

		return 0;

	}
	stack->top++;

	stack->stack[stack->top]=*value;

	stack->length++;

	return 1;
}
/*
 * @file      seqstack.cpp
 * @function  出棧函數
 * @author    酸菜。
 * @date      2019-09-16
*/
int popstack(seqstack* stack, element* ment)
{
	static int p = 0;

	if (stack->top ==  - 1 || stack->length == 0)
	{

		printf("棧空，無法出棧：！\n");

		return 0;

	}	
	ment->ment[p++] = stack->stack[stack->top];

	stack->top--;

	stack->length--;

	return 1;
}
/*
 * @file      seqstack.cpp
 * @function  清空棧
 * @author    酸菜。
 * @date      2019-09-16
*/
void clear(seqstack* stack)
{
	stack->length = 0;

	stack->top = -1;
}
/*
 * @file      seqstack.cpp
 * @function  判斷棧是否為空
 * @author    酸菜。
 * @date      2019-09-16
*/
int seqstack_is_empty(seqstack* stack)
{
	if (stack->top == -1 || stack->length == 0)
	{

		printf("棧空，無法出棧：！\n");

		return 1;

	}
	return 0;
}
/*
 * @file      seqstack.cpp
 * @function  判斷棧是否滿
 * @author    酸菜。
 * @date      2019-09-16
*/
int seqstack_is_full(seqstack* stack)
{
	if (stack->top == MAX-1 || stack->length == MAX)
	{

		printf("棧以滿，無法入棧：！\n");

		return 1;

	}
	return 0;
}
/*
 * @file      seqstack.cpp
 * @function  擷取棧頂元素
 * @author    酸菜。
 * @date      2019-09-16
*/
int getseqstack_value(seqstack* stack)
{

	return stack->stack[stack->top];

}

//seqstack.h
#ifndef   _seqstack_h
#define   _seqstack_h

#include<stdio.h>
#include<stdlib.h>
#include<iostream>

typedef int datatype;
#define MAX  100
typedef struct element
{
	datatype ment[MAX];
}element;
typedef struct seqstack
{
	datatype stack[MAX];//存放棧元素
	datatype top;//棧元素下标
	datatype length;//棧長度
}seqstack;

extern int initseqstack(seqstack* stack);//初始化棧
extern int pushstack(seqstack* stack, int* value);//進棧
extern int popstack(seqstack* stack ,element* ment);//出棧
extern void clear(seqstack* stack);//清空棧
extern int seqstack_is_empty(seqstack* stack);//判斷棧是否空
extern int seqstack_is_full(seqstack* stack);//判斷棧是否滿
extern int getseqstack_value(seqstack* stack);//擷取棧頂元素的值

#endif 
           

棧是線性表的特例，是以棧的順序存儲其實也是線性表順序存儲的簡化，簡稱順序棧。

那麼我們是用數組的那一端作為棧底比較好呢？答案是下标為0的那一端。讓它作為棧低。

棧的順序存儲結構還可以用以下結構：

#define  MAXSIZE  5

typedef int SElemTYpe;
typedef struct stack
{
  SElemTYpe data[MAXSIZE];//棧的大小
  int top;//棧頂指針
}seqstack;
           

這裡top作為訓示棧頂元素在數組中的位置，top可以來回移動，當棧中沒有元素時，top等于-1，當然top也不可以超過棧的空間大小。

就像我們生活當中的遊标卡尺一樣，隻能在一定的範圍内來回移動。

//進棧

int push(seqstack* s,int value)
{
   if(s->top==MAXSIZE-1)
   {
      return 0;
  }

  s->top++;
  s->data[s->top]=value;

  return 1;
}
           

//出棧

int pop(seqstack* s)
{
   int i=0;
   if(s->top==-1)
   {
      return 0;
  }
  i=s->data[s->top];
  s->top--;
  return i;
}
           

無論是進棧還是出棧，兩者沒有涉及到任何循環語句，它們的時間複雜度均為O(1)。