Stack 的定义和结构
栈(Stack)是仅限于在表尾进行插入和删除的线性表
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何元素的栈称为空栈，栈也被称为先进后出(Last In First Out)的线性表，简称LIFO结构
栈的机构如下图所示：
栈的插入操作，称为进栈，也称为压栈，入栈。类似于子弹压入弹夹
栈的弹出操作，称为出栈，有的也叫做弹栈。类型于子弹从弹夹中弹出
Stack 的抽象数据类型
ADT Stack(队列)
Data:
同线性表, 元素具有相同的类型，相邻的元素具有前驱和后继关系
Operation:
InitStack(S*)
DestroySatck(S*)
isEmpty(S*)
Peek(Q*)// 获取栈顶的元素值，但是不弹出栈
Pop(Q*, *e)
Push(Q*, e)
StackSize(Q)
endADT
静态数组实现Stack
- 建立一个
MAX_SIZE的数组, 用于存放 Stack 中的元素 - 建立int类型
stack->top代表栈顶，当弹出元素时，取出stack->top位置的值，同时stack->top--指向下一个元素 - 当压入元素时，
stack->top++代表的index 存入新压入元素，并且stack->top指向新元素的位置
参考实现代码：
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
}Stack;
static void initStack(Stack* stack) {
stack->top = -1;
}
static int isEmpty(Stack* stack) {
return (stack->top == -1);
}
static int isFull(Stack* stack) {
return (stack->top == MAX_SIZE -1);
}
static void push(Stack* stack, int value) {
if(isFull(stack)) {
fprintf(stderr, "stack is full. \n");
return;
}
stack->top++;
stack->data[stack->top] = value;
//printf("stack top is %d.\n", stack->top);
}
static int pop(Stack* stack) {
if(isEmpty(stack)) {
printf("stack is empty. \n");
return -1;
}
int item = stack->data[stack->top];
stack->top--;
return item;
}
static int peek(Stack* stack) {
if(isEmpty(stack)) {
fprintf(stderr, "stack is empty. \n");
return -1;
}
return stack->data[stack->top];
}
static int modifyTop(Stack* stack, int value) {
if(isEmpty(stack)) {
fprintf(stderr, "stack is empty. \n");
}
stack->data[stack->top]= value;
}
static int stackSize(Stack* stack) {
return stack->top+1;
}
int testbasicStackStaticArray(int agrc, char *argv[]) {
{
Stack teststack;
initStack(&teststack);
push(&teststack,100);
push(&teststack,110);
push(&teststack,120);
printf("stack size is %d.\n",stackSize(&teststack));
int value = pop(&teststack);
printf("stack pop value is %d. size:%d\n",value,stackSize(&teststack));
value =pop(&teststack);
printf("stack pop value is %d. size:%d\n",value,stackSize(&teststack));
value = pop(&teststack);
printf("stack pop value is %d. size:%d\n",value,stackSize(&teststack));
printf("stack pop value is %d.\n",pop(&teststack));
}
{
Stack teststack;
initStack(&teststack);
push(&teststack,100);
printf("stack size:%d peek value:%d \n", stackSize(&teststack), peek(&teststack));
int value = pop(&teststack);
printf("stack size:%d peek value:%d \n", stackSize(&teststack), peek(&teststack));
}
}
单链表实现Stack
- 建立一个单链表，包含指向栈顶的指针
Stack->top - 当压入元素时，就是单链表的头部插入操作，先给新元素分配空间，然后将新元素的 next 指向 当前的
Stack->top，最后更新Stack->top的值 - 当弹出元素时，就是单链表的头部删除操作，首先释放当前
Stack->top节点，然后将Stack->top更新到之前元素的下一个位置
参考代码实现如下：
struct node {
int data;
struct node *next;
};
typedef struct {
struct node* top;
} Stack;
static int empty(Stack* stack) {
return(stack->top == NULL);
}
static void initStack(Stack* stack){
stack->top = NULL;
}
static void push(Stack* stack, int item) {
struct node *pnode;
pnode = (struct node *)malloc(sizeof(struct node));
if(pnode == NULL) {
printf("malloc node failed!.\n");
exit(1);
}
pnode->data = item;
pnode->next = stack->top;
stack->top = pnode;
}
static int pop(Stack* stack) {
int item;
struct node *pnode;
if(empty(stack)) {
printf("stack is empty.\n");
exit(1);
} else {
item = stack->top->data;
pnode = stack->top;
stack->top = stack->top->next;
free(pnode);
}
return item;
}
static int stackSize(Stack* stack) {
int count = 0;
struct node *pnode = stack->top;
if(empty(stack)) {
return 0;
} else {
do {
pnode = pnode->next;
count++;
}while(pnode != NULL);
}
return count;
}
int testbasicStackImplsingleLinkedList(int argc, char *argv[]) {
{
Stack teststack;
initStack(&teststack);
push(&teststack, 110);
push(&teststack, 111);
push(&teststack, 113);
push(&teststack, 223);
push(&teststack, 678);
int stacksize = stackSize(&teststack);
printf("stack size is %d.\n", stacksize);
printf("stack pop value is %d.\n",pop(&teststack));
printf("stack pop value is %d.\n",pop(&teststack));
printf("stack pop value is %d.\n",pop(&teststack));
// check failed
printf("stack pop value is %d.\n",pop(&teststack));
stacksize = stackSize(&teststack);
printf("stack size is %d.\n", stacksize);
}
return 1;
}
