Computer Language/Data Structure

[Data Structure] basic idea of Stack

정우섭 2020. 8. 4. 20:57

Stack

LIFO(Last in First out) method

 

Stack in data structure literally means stacking data in memory following 'LIFO method'.

 

 

Top

 

As the picture shows, same size of data is structed in one way and to access the data you can access data from 'top'.

('top' points the last data input)

 

Data in 

 

 

Operators

 

Input new data with operator 'push'.

 

Extract data and return with operator 'pop'.

 

And there's also 'peek' operator which returns the last input character, without extracting it.

 

In abstract data type, stack is declared like this.

 

 

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

#define MaxStackSize 100
typedef int element;
element stack[MaxStackSize];
int top = -1;

// Check if stack is empty
int isEmpty() {
	return(top == -1 ? 1 : 0);
}

// Check if stack is full
int isFull() {
	return (top == (MaxStackSize - 1));
}

// Input new data in stack
void push(element item) {
	if(isFull() == 1) {
		printf("stack is full.\n");
	}
	else {
		stack[++top] = item;
	}
}

// Extract data from stack and returns
element pop() {
    if (isEmpty() == 1) {
        printf("Stack is empty.\n");

	}
    else {
		printf("%c\n",stack[top]);
		return stack[top--];
	}
}

// Return 'top' data.
element peek()
{
	if(is_empty()){
		fprintf(stderr, "stack is empty.");
		exit(1);
	}
	else return stack[top];
}

int main () {
	push('A');
	push('B');
	push('C');
	push('D');
	push('E');
	printf("isFull : %d\n", isFull());
	pop();
	pop();
	pop();
	pop();
	pop();
	printf("isEmpty : %d", isEmpty());
	return 0;
}