Belajar Komputer

Belajar komputer itu mudah dan gratis

The Stack


One of the most useful concepts in computer science is that of the stack. A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack.

Unlike that of the array, the definition of stack provides for the insertion and deletion of items, so that a stack is a dynamic, constantly changing object. The definition specifies that a single end of the stack is designated as the stack top. New items may be put on top of the stack (in which case the top of the stack moves upward to correspond to the new highest element), or items which are at the top of the stack may be removed (in which case the top of the stack moves downward to correspond to the new highest element). A stack is sometimes called a Last-In, First Out (LIFO) list.

Stack containing stack items :

The Stack

Primitive Operations

The two changes which can be made to a stack are given special names. When an item is added to a stack, it is pushed onto the stack. And when an item is removed, it popped from the stack.

Representing Stack in C
A stack in C may therefore be declared as a structure containing two objects : an array to hold the elements of the stack, and an integer to indicate the position of current stack top within the array.

#define STACKSIZE 100
struct stack
{
int top;
int items[STACKSIZE];
};

struct stack s;

The empty stack contains no elements and can therefore be indicated by top equalling to -1. To initialize a stack s to the empty state, we may initially execute : s.top = -1;

We may write a function that returns TRUE if the stack is empty and FALSE if it is not empty.

int empty(struct stack *ps)
{
if(ps->top == -1) return(TRUE);
else return(FALSE);
}

Implementing The Pop Operation

The possibility of underflow must be considered in implementing the pop operation, since the user may inadvertently attempt to pop an element from an empty stack. We therefore introduce a function pop that performs the following three actions :

  • If the stack is empty, print a warning message and halt execution
  • Remove the top element from the stack
  • Return this element to the calling program

int pop(struct stack *ps)
{
if(empty(ps)){
printf(“Stack underflow”);
exit(1);
}
return(ps->items[ps->top–]);
}

The use of pop function, the programmer can declared int x and write :

x = pop(&s);

x then contained the value poped from the stack.

Implementing The Push Operation

The possibility of overflow must be considered in implementing the push operation, since the user may inadvertently attempt to push an element onto a full stack.

void push(struct stack *ps, int x)
{
if(ps->top == STACKSIZE – 1){
printf(“Stack overflow”);
exit(1);
}
else ps->items[++(ps->top)] = x;
}

The use of push function, the programmer can write :

push(&s,x);

references : Data Structures using C and C++, Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum, Prentice Hall

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: