Stack的概念
想像有一個容器,我們依序放入東西進去,當要拿出東西時,一定是先取出最後放進去的那樣東西。
此即為先進後出之概念 -> first in last out FILO
函式介紹
push():將元素放入stack中。
pop():將最上面的元素取出。有時候我們可以依需要,回傳最上面的值再將其取出。
isEmpty():判斷stack是否為空。
isFull():判斷stack是否為滿。
print():列印出stack裡的所有元素,從下而上。(也可由上而下,視需要)
top:表示最上面元素之索引位置。
函式實作
陣列:利用陣列實作時,一定要宣告stack之容量(不然也無法malloc),也就是top的最大值( maxTop )。.陣列的第一個位置存放最先放入的元素。
#include <stdio.h>
#include <stdlib.h>
typedef struct stack{
int top;
int maxTop;
int *data;
}stack_t;
void create_stack(stack_t *st, int size){
st->top=-1;
st->maxTop=size-1;
st->data=(int *)malloc(sizeof(int)*size);
}
int isEmpty(stack_t *st){
if (st->top == -1)
return 1;
return 0;
}
int isFull(stack_t *st){
if (st->top == st->maxTop)
return 1;
return 0;
}
void push(stack_t *st, int num){
if (isFull(st) == 1)
printf("The stack is full.\n");
else
st->data[++st->top]=num;
}
int pop(stack_t *st){
if (isEmpty(st) == 1)
printf("The stack is empty.\n");
else
return (st->data[st->top--]);
}
void print(stack_t *st){
if (isEmpty(st) == 1)
printf("The stack is empty.\n");
else{
int i;
for (i=0; i<=st->top; i++)
printf("%d ", st->data[i]);
printf("\n");
}
}
int main(){
stack_t *s=(stack_t *)malloc(sizeof(stack_t));
printf("Create a stack which size is 5.\n");
create_stack(s, 5);
printf("Push:1,2,3,4,5:\n");
push(s, 1);
push(s, 2);
push(s, 3);
push(s, 4);
push(s, 5);
print(s);
printf("First time pop, the top is %d:\n", pop(s));
print(s);
printf("Second time pop, the top is %d:\n", pop(s));
print(s);
return 0;
}
鏈結串列:不須宣告 stack 大小。head 永遠指向 stack 最上方。
#include <stdio.h>
#include <stdlib.h>
typedef struct stack{
int data;
struct stack *next;
}stack_t;
stack_t *head;
void create_stack(){
head=NULL;
}
int isEmpty(){
if (head == NULL)
return 1;
return 0;
}
void push(int num){
stack_t *new_node=(stack_t *)malloc(sizeof(stack_t));
new_node->data=num;
new_node->next=NULL;
if (isEmpty() == 1)
head=new_node;
else{
new_node->next=head;
head=new_node;
}
}
int pop(){
if (isEmpty() == 1)
printf("The stack is empty.\n");
else{
stack_t *temp=head;
head=head->next;
return temp->data;
}
}
void print(){
if (isEmpty() == 1)
printf("The stack is empty.\n");
else{
stack_t *curr=head;
while (curr != NULL){
printf("%d ", curr->data);
curr=curr->next;
}
printf("\n");
}
}
int main(){
head=(stack_t *)malloc(sizeof(stack_t));
printf("Create a stack which size is 5.\n");
create_stack();
printf("Push:1,2,3,4,5:\n");
push(1);
push(2);
push(3);
push(4);
push(5);
print();
printf("First time pop, the top is %d:\n", pop());
print();
printf("Second time pop, the top is %d:\n", pop());
print();
return 0;
}
執行結果
Create a stack which size is 5.
Push:1,2,3,4,5:
1 2 3 4 5
First time pop, the top is 5:
1 2 3 4
Second time pop, the top is 4:
1 2 3